HashMap 源码浅析

1. JDK 1.7

在JDK1.7中，HashMap的数据结构是由数组+链表Entry 实现；

get() 方法：

public V get(Object key) {
        // 如果key为null，调用getForNullKey()找key为null的元素
        if (key == null)
            return getForNullKey();
        // 获取Key为key的键值对
        Entry<K,V> entry = getEntry(key);
        
        return null == entry ? null : entry.getValue();
    }
 
 
final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
 
        int hash = (key == null) ? 0 : hash(key);
        // 直接遍历下标所在链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }
 
private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

判断key是否为null，如果为null调用 getForNullKey() 从头开始遍历table数组，找到key为null的元素并返回value，如果没有就返回null；
如果不为null，调用 getEntry(key)，使用 indexfor() 方法使 key的哈希值和长度-1相与；
获取table[e] 即头节点，遍历链表，返回哈希值和key都相同的节点的value；
（和JDK1.8 基本一样，多了个 indexfor 方法）

put() 方法：

public V put(K key, V value) {
        //当第一次调用put方法时才对table进行初始化
        if (table == EMPTY_TABLE) {
            //创建table
            inflateTable(threshold);
        }
        // 如果要put元素的key为null，则直接将该元素存储到table[0]链表中
        if (key == null)
            return putForNullKey(value);
        // 根据key散列出hash值，里面使用了位运算
        int hash = hash(key);
        // 计算下标
        int i = indexFor(hash, table.length);
        //如果table[i]不等于null
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
          	// 如果 hashCode相等，并且key相等，或者key.equals(k)
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 记录e的value
                V oldValue = e.value;
                // value的替换
                e.value = value;
                e.recordAccess(this);
                // 返回记录的value
                return oldValue;
            }
        }
	    //方法执行到此处时，说明原链表中不存在与插入元素key相同的元素，那么，就需要创建一个Entry并插入
        //向HashMap添加一个元素时，modCount需要自增
        modCount++;
        //添加Entry
        addEntry(hash, key, value, i);
        return null;
    }

这里没有调用putVal()方法，在put()内，如果key为null，则直接将该元素存储到 table[0] 链表中；
indexFor 计算下标，得到头节点，如果头节点的哈希值和key相等，则直接覆盖；
否则遍历链表，找是否有元素的哈希值和key与put的相等，有则覆盖，没有则在链表头部插入新的节点。（头插法—-多线程下扩容导致循环链表）

resize() 方法：

void resize(int newCapacity) {  
    Entry[] oldTable = table;//老的数据  
    int oldCapacity = oldTable.length;//获取老的容量值  
    if (oldCapacity == MAXIMUM_CAPACITY) {//老的容量值已经到了最大容量值  
        threshold = Integer.MAX_VALUE;//修改扩容阀值  
        return;  
    }  
    //新的结构  
    Entry[] newTable = new Entry[newCapacity];  
    transfer(newTable, initHashSeedAsNeeded(newCapacity));//将老的数据拷贝到新的结构中。initHashSeedAsNeeded为是否使用hash总值，与虚拟机配置有关，默认为false
    table = newTable;//修改HashMap的底层数组  
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阀值  
} 
//将老的数据拷贝到新的结构中  
void transfer(Entry[] newTable, boolean rehash) {  
    int newCapacity = newTable.length;//新的容量  
    for (Entry<K,V> e : table) {  
        while(null != e) {  
            Entry<K,V> next = e.next;  
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);  
            }  
            int i = indexFor(e.hash, newCapacity);//定位Hash桶，计算的结果可能为：初始位置 或者 初始位置 + 扩容量
            e.next = newTable[i];//扩容插入也会采用头插法，与旧的hash桶相比链表的顺序可能会被颠倒，并且分散到 初始位置 和 初始位置 + 扩容量两个位置中
            newTable[i] = e;  
            e = next;  
        }  
    }  
}

resize() 创建2倍容量的新数组；
transfer() 进行拷贝：
① rehash() 计算旧数组中元素在新数组中的下标
② 使用头插法，链表顺序颠倒——-【多线程扩容时】可能导致循环链表；
把新数组赋值给table属性；

2. JDK 1.8

get() 方法：

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
 
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //tab：内部数组  first: 索引位首节点 n: 数组长度 k: 索引位首节点的key
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { //JDK1.8之前的indexfor()
            //如果索引位首节点的hash值与需要寻找的hash值相等，并且key的内容也相同，则返回该节点
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    //如果是首结点p属于TreeNode，则到红黑树中去查找并返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //遍历单链表寻找节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e; // 链表中节点key.equals为true则返回
                } while ((e = e.next) != null);
            }
        }
        return null; // 如果链表中节点key.equals全为false则返回null
    }

先使用 indexfor 方法，不需要封装Node，用Key的哈希值和（数组长度-1）做与运算，算出数组的下表 i 以定位，得到i索引处的数组元素首位节点first，如果first的key和哈希码等于要查找的key和哈希码，则直接返回first节点；
如果查询的key、哈希码和first的不等，则判断：
①如果首位结点first为空，返回null
②如果first属于TreeNode类型，则到红黑树中去查找并返回
③遍历单链表，若链表中节点的哈希码和要查找的哈希码相同，且key.equals为true则返回，如果链表中节点key.equals全为false则返回null

put () 方法：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 //HashMap.put的具体实现
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判定table不为空并且table长度不可为0,否则将从resize函数中获取
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         //JDK1.7之前的indexfor() 方法，也是扩容必须2^n的原因
        if ((p = tab[i = (n - 1) & hash]) == null) //令table数组索引处的首位节点为p
            //如果p为null则直接放入新节点Node
            tab[i] = newNode(hash, key, value, null);
        else {  //如果p不为空
            Node<K,V> e; K k;
             //对这个元素进行Hash和key值匹配
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;  // 如果索引首位节点p的key值与新节点key相同，则直接覆盖
            else if (p instanceof TreeNode) //如果数组中的这个元素p是TreeNode类型
                //判定成功则在红黑树中查找符合的条件的节点并返回此节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //若以上条件均判断失败，则执行以下代码
                //向Node单向链表中添加数据，遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) { //如过链表的每个节点key.equals都返回false，则直接添加到末尾（尾插法！）
                        p.next = newNode(hash, key, value, null);
                         //若节点数大于等于8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break; //如果链表中有节点key.equals返回true，则后续用新节点覆盖该节点
                    p = e; //更新节点p以记录下一个节点
                }
            }
            if (e != null) { // break之后，使用新节点覆盖key.equals为true的节点
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) //判断是否需要扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

HashMap默认有一个Node数组table；调用putval()，将K、V以及K的哈希码传到putval() 方法；
判断键值对数组table[i]是否为空，否则执行resize()扩容；
使用indexfor方法，用哈希值和（数组长度-1）做与运算算出数组的索引值 i 以定位，得到i索引处的数组元素首位节点p （JDK1.7之后没有indexfor方法），
如果p为null则直接new Node 创建新节点；
如果p不为null，需要判断：
①先调用equals方法，如果索引首位节点p的key和新节点的Key相同（不同的key也可能会哈希冲突！）且哈希码也相同，则新节点直接覆盖 p，不用看p后面的节点；
②key和首结点的key不同时，如果p节点属于TreeNode，则在红黑树中查找符合的条件的节点并返回此节点
③如果p不属于红黑树则是单向链表，遍历单向链表，调用每个节点的key.equals() 方法，返回true则覆盖，全都false则new Node创建新节点并添加到末尾（尾插法！）
（过程中会判断节点数是否＞8，是则转换为红黑树）
判断size是否达到threshold，是则 resize() 扩容；

总结：
综上所述，hashmap计算元素所处位置的方式，以及扩容原理，其本质就是保证数据均匀的落在数组上。在巧妙的异或、按位与运算及扩容机制，最终尽可能得保证了数据落在数组的每个位置的概率是一样的。

resize() 方法：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
     	//oldCap:旧数组长度，oldThr:旧扩容阈值,newCap:新数组长度,newThr:新扩容阈值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
     	//旧数组非空时，若旧数组长度已经达到上限（2的30次方）则将扩容阈值设成2的31次方-1(Integer类型最大长度)并直接返回
   		//否则，当新数组长度小于上限且旧数组长度大于等于默认值(16)时，令新的扩容阈值=旧扩容阈值*2
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
     	//旧数组为空而旧扩容阈值大于0时，令新数组长度等于旧扩容阈值
     	//这里要注意，当new出来一个空HashMap并自定义数组长度时，扩容阈值为大于自定义长度的2的最小次幂
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
     	//旧数组为空且旧扩容阈值为空，则新数组长度为默认值16，新扩容阈值为16*0.75=12
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
     	//新扩容阈值为空时重新计算新扩容阈值：若新数组长度小于上限且新数组长度*负载因子小于上限，则令新扩容阈值=新数组长度*负载因子，否则为Integer最大长度
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
     	//将新扩容阈值赋予HashMap
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
     	//初始化新数组，从这里开始正式执行将旧数组中的数据放进新数组的过程
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //遍历旧数组的每个Entry节点
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //节点中有数据则继续，没数据直接continue
                //这里分了三种情况：1.节点e只有一条数据 2.节点e是红黑树 3.节点e是节点数大于1的链表
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //该节点的下一跳为空，即该节点只有一条数据：重新计算该节点的index(即key的hash值与上新长度-1)
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //该节点为红黑树：把树拆成一个低位树和一个高位树，低位树放在原来的下标处，高位树放在下标为旧下标+旧数组长度的下标出
                    //判定高低位的逻辑可以参考第三种情况：节点e是节点数大于1的链表
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //该节点为节点数大于1的链表：遍历链表，同样把链表拆分成高位和低位两个链表，分别放在下标为j+oldCap和j处(oldCap:旧数组长度)
                    else { // preserve order
                        //这里定义了四个节点，实际是两个链表
                        //lohead、lotail分别是lo链表的头节点和尾节点，hihead、hitail同理
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            //这里区分高位低位的逻辑：如果e的hash值与上就数组长度等于0则是低位，否则为高位
                            //这里打个比方，比如e的hash值是101111，旧数组长度是16即100000,结果就是100000，这里需要判断结果是否等于0，即只需要判断
                            //e.hash的第6位数组是否是0就可以了，即不论oldCap值是多少，只需要关注e.hash某一位的值是0还是1，就可以以此判定高低位
                            next = e.next;
                            // 判断扩容后的下标是否与扩容前的相等
                            if ((e.hash & oldCap) == 0) {
                                //尾插法
                                //这里可以这么理解：loHead指向头节点，loTail指向尾节点，loTail是随着节点增加不断向后移动的
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                //尾插法
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //把高低位的头节点分别放进对应下标处
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;

大概流程：

生成2倍容量的新数组；
遍历哈希表，依次拿到头节点
①如果头节点没有下一个元素，重新计算哈希值；
②如果是红黑树，那么对树进行拆分再拷贝
③如果都不是，用 e.hash & oldCap) == 0 进行判断，是则索引不变，不是则索引=旧索引+原数组长度，尾插法拷贝；

(e.hash & oldCap) == 0

HashMap在扩容时，需要先创建一个新数组,然后再将旧数组中的数据转移到新数组上来
此时，旧数组上的数据就会根据(e.hash & oldCap) 是否等于0这个算法,被很巧妙地分为2类:

等于0时，则将该头节点放到新数组时的索引位置 = 其在旧数组时的索引位置；
不等于0时,则将该头节点放到新数组时的索引位置 = 其在旧数组时的索引位置 + 旧数组长度；

作用：
优化计算效率；
为了满足该节点的数据在新旧数组中的下标相同；

3. JDK 1.7 和 1.8 hashmap区别

结构，JDK1.8 多了红黑树，为了防止退化成链表并且提升检索时的效率；
put() 时JDK1.7 为头插法，JDK1.8为尾插法；
扩容时，JDK1.7的链表会颠倒，由于采用头插法，故可能导致循环链表；
而JDK1.8会保持原链表的顺序；
扩容策略：1.7中是只要达到 threshold 就直接扩容2倍；
在JDK1.8中，当链表中元素达到8，会尝试转换为红黑树，转化之前先判断数组长度是否大于64，如果说没有则扩容，因为扩容也能使得链表长度减半，当数组长度＞64 ，则将链表转换成红黑树，但如果红黑树中的元素个数小于6就会还原为链表；

4. 常见问题：

为什么HashMap扩容一定要是2的n次方？

因为计算数组下标时是 i = (n - 1) & hash即将( 数组长度-1 ) 和Key的哈希值进行与运算，只有当数组的长度是2的n次方，则（数组长度-1）的二进制才能保持后面全是1，全是1才能保证数组中的任意一位置都能取到；
如数组长度5 ，则5-1=4 ，4的二进制为00000100 ，那么索引 1 2 3都无法获取到！（与运算中真真才能为真）；

为什么默认负载因子是0.75？

如果负载因子太大，则扩容发生的频率比较低，利用率高，但是容易导致哈希冲突；
如果负载因子太小，则扩容发生的频率比较高，数组数据分散，利用率低；
0.75 符合数学泊松分布。

哈希冲突

由于在Java中两个不同的对象可能有一样的哈希值，因为不同的键可能有一样hashCode，从而导致冲突的产生；
HashMap使用链式地址法应对哈希冲突；
在JDK1.8 之前，如果发生碰撞往往是将该value直接链接到该位置的其他所有value的末尾，即相互碰撞的所有value形成一个链表。因此，在最坏情况下，HashMap的查找时间复杂度将退化到O（n）.
JDK1.8后，当一个位置所在的冲突过多时（元素>8），存储的value将形成一个红黑树，目的是提高检索效率，在最坏情况下，HashMap的查找时间复杂度将从O（1）退化到O（logn）；

参考：
https://blog.csdn.net/xadasss/article/details/116793267
https://blog.csdn.net/m0_51212267/article/details/124144767
https://blog.csdn.net/weixin_44827844/article/details/122244897
https://blog.csdn.net/weixin_43608392/article/details/121136613

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89244.html