HashMap原理详解

一、hashmap简介
hashmap是Java当中一种数据结构，是一个用于存储Key-Value键值对的集合，每一个键值对也叫作Entry。

二、JDK7的HashMap
1、JDK7时HashMap的数据结构
1、在JDK7之前，hashmap底层采用数组+链表的数据结构来存储数据
2、插入数据采用头插法，头插法效率更高，不需要去遍历链表。插入结点后将头结点移到数组下标的位置

什么是头插法？咱们看一副图你就了解了

 

 

每次都在头结点插入，其余的节点依次往下挪。那么这样就会造成一个问题，当扩容的时候，对每个节点重新rehash。假设重新计算hash后孙悟空和孙尚香依然还是在一条链上，但可能顺序变了，变成孙尚香—>孙悟空。而原来的孙悟空—>孙尚香这个指针又没有断开，这样就会形成环，最终会导致死锁
2、相关问题解答
为什么hashmap的容量是2的幂次方？
1、&运算速度快，至少比%取模运算块
2、(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n
3、采用(n - 1) & hash来计算索引，当n为2的幂次方的时候，（n-1）转换成为二进制保证低位全是1

为什么JDK7中hashmap源码计算hashcode要右移？
求索引位置时保证高位也能参与位运算。为了保证求出来的散列值均匀。如果计算出来的索引扎堆，那么这就不算一个好的哈希算法

JDK7hashmap如何判断是否需要扩容？
有两个条件。第一个是当前元素个数大于或等于阈值。第二个是当前数组table[i]!=null

Hashmap是线程不安全的？
1.多线程环境下，如果有多个线程同时对一个数据进行操作，很有可能出现数据覆盖的情况。
2.扩容有可能发生死锁情况

hashMap允许key为null。如果key为null，则默认把这个数据放在索引为0的位置处

三、JDK8的HashMap部分源码
1、jdk8中hashMap数据结构
1、JDK8以后hashmap的底层数据结构由数据+链表+红黑树实现
2、jdk8以后插入数据采用尾插法。因为引入了树形结构，总是要遍历的

 

当进行put操作的时候，当链表的长度大于或等于8时，会将链表转化为红黑树
在进行remove操作的时候，当红黑树的节点个数小于或者等于6时，会将红黑树转化为链表
2、相关问题解答
为什么使用红黑树而不使用其他的树形结构？
hashMmap中不仅存在查询，还存在修改的操作。红黑树的查询和修改效率处在链表和完全平衡二叉树之间

hashMap怎么设置初始值的大小
如果你在创建的时候没有设置初始值大小，那么它的默认容量是16。
如果你设置了一个初始容量，它会先进行一个判断，判断这个值是不是2的次幂，如果不是将会把容量转化成为2的次幂大小。比如说你设置的容量是27，那么创建的HashMap实际容量是32。

jdk7和jdk8中HashMap的区别
1、jdk8中当链表长度大于8时会将链表转化成为红黑树
2、节点插入顺序不同，jdk7采用头插法，而jdk8采用尾插法
3、hash算法的简化
在jdk7中hash算法为   

final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String)  k);}h ^= k.hashCode();// This function ensures that hashCodes that  differ only by// constant multiples at each bit position have a  bounded// number of collisions (approximately 8 at  default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

在jdk8中的hash算法为

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h =  key.hashCode()) ^ (h >>> 16);}

为什么在jdk8中要简化hash算法：jdk8之前之所以hash方法写的比较复杂，主要是为了提高散列行，进而提高遍历速度，但是jdk8以后引入红黑树后大大提高了遍历速度，继续采用复杂的hash算法也就没太大意义，反而还要消耗性能，因为不管是put()还是get()都需要调用hash()

4、扩容不同，在jdk7中，发生扩容，它会把原来所有的元素重新计算hash。再插入到新的位置。而jdk8中则是直接copy过去，要么位置不变，要么位置更改为索引+原数组长度