最通俗易懂的HashMap原理详解（JDK 1.8）

一、HashMap的数据结构

 HashMap是存储键值对的集合，当然HashMap也是线程不安全的，每一个键值对存储在一个Node<K,V>（JDK1.7中是Entry<K,V>。HashMap的主干是一个名为table的Node数组。

 每个键值对Key的hash值就对应数组的下标，当遇到hash冲突时，HashMap采用的策略是链地址法。在JDK1.7中通过键值对Entry<K,V>中的next属性来把hash冲突的所有Entry连接起来，因此每次都要遍历链表才能得到所要找的键值对，增删改查操作的时间复杂度为O（n）。而在JDK1.8中，当链表长度大于8时，会将链表转化为一棵红黑树，增删改查操作的时间复杂度为O（log（n））。

 注意，HashMap运行Key为null，并且存储在table[0]的位置，table[0]的位置只能存储一个Key为null的键值对。（Hashtable不允许key为null）。

 

二、源码分析

1、Node<K,V>键值对。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//hash值
        final K key;//键值
        V value;
        Node<K,V> next;
        ……
}

 key和hash属性为final的原因：在Java中，如果一个对象的属性值在业务逻辑上不需要改变，就将其声明为final，这样保证了安全性。而且在这里若是让key或者hash发生改变，会导致该键值对无法被查找到。

2、重要属性

transient int size;//实际键值对个数
int threshold;//阈值，超过到这个值后就要进行扩容
transient int modCount;//修改计数器，用于快速失败
final float loadFactor;//加载因子

 注意threshold = table.length （默认值为16）* loadFactor（默认值为0.75）这两个值可以在构造时自行输入。length值需要自己根据业务需求输入，输入合适的值能显著减少扩容次数 。而loadFactor值在一般情况下0.75都是有不错的效率的。但是若是对时间效率要求很高，对空间效率要求很低，可以减小loadFactor值，反之增大loadFactor值，可以大于1。modCount用于记录对象的改变结构的次数（不包含修改value的值的操作），这是用于在多线程情况下，当多个线程并发修改HashMap的结构时，多个线程都会去修改modCount这个成员变量，而每个线程内部维护着一个局部变量的修改技术器，当线程做完修改操作后发现成员变量的modCount与局部变量不一致时，就抛出ConcurrentModificationException，这是fail-fast机制，Java中如ArrayList等线程不安全的集合都有这个机制。

3、如何求key的hash值

 在HashMap中，计算key的hash值，也就是在table数组中的下标位置算法很巧妙，用到了许多位运算。

主要分为三步：

 （1）计算对象自己的hashCode()值

 （2）计算上步得到的值高16位于低16位相与。否则在容器length较小时，无法发挥高位的作用，这样能使 得hash分布更加均匀，减少冲突。

 （3）定位操作，对上步计算得到hash值进行取模操作（这里用的是位运算，有个小技巧）。

第一步与第二步：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//第一步与第二步
    }

 第三步是取模定位，在JDK1.7中是一个indexFor函数，而JDK1.8取消了这个函数，但是JDK吧把这个index操作整合到put操作和get操作中去了，当然其代码原理都是一样的。

核心代码：

index = (n - 1) & hash//在这里等价于hash%n

 这里你一定想问，为什么这个位运算能够与取模运算相等了，这里就要归功于HashMap对容量的一个巧妙设计。HashMap规定length一定是2^N，N可为任意整数，如果自定义的length长度不为2的整数次幂，那么就会自动取成大于设定值的最接近的2^N的值。在这个前提下，我们再来看这个二进制与运算。如在n=16的情况下，15的二进制码为 1111，不管是什么数，和11111做&操作，低五位不会变，而高位全部为0，即与hash%n的结果是一样的。而且在计算机中，位运算的效率是最高的，因此这样会大大提升查询效率。

4、扩容操作（resize()）

需要扩容的情况：

if (++size > threshold)//当完成put操作后，发现新的size大于了阈值
            resize();

每次扩容为之前的两倍：

newThr = oldThr << 1; // double threshold

在扩容之后就要把具体键值对搬迁到新的table数组中。

5、put方法具体流程

（图片来自网络）