数据结构算法 - HashMap 源码解析

短命女 2022-04-24 04:12 204阅读 0赞

思考题：  
equals 和 == 的区别，hashCode 与它们之间的联系？  
HashMap 的长度为什么是 2 的幂次？  
五个线程同时往 HashMap 中 put 数据会发生什么？  
Hashmap中的hash冲突到底指的是什么?  
Hashmap进行put操作的时候，**会对key值进行比较吗？**  
HashMap中是采用的键值对的方式存储，那么put操作的时候是直接比较key值，相等覆盖，不等新增，怎么会出现线程不安全的情况？  
HashMap什么情况下进行扩容？

## 一、初窥HashMap ##

HashMap是应用更广泛的哈希表实现，而且大部分情况下，都能在常数时间性能的情况下进行put和get操作。  
要掌握HashMap，主要从如下几点来把握：  
jdk1.7中底层是由**数组（也有叫做“位桶”的）+链表**实现；  
jdk1.8中底层是由**数组+链表/红黑树**实现可以存储null键和null值，  
线程不安全初始size为16，  
扩容：newsize = oldsize\*2，size一定为2的n次幂扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀.

**1.8中HashMap结构图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3cxMDE0MDc0Nzk0_size_16_color_FFFFFF_t_70]

**Hashmap中的hash冲突到底指的是什么?**

简单的说，我们向hashmap中put数据时，首先会根据key值的hashcode的值去bucket数组中进行快速选址找到对应的桶，当出现hashcode相等的情况，就是出现了hash冲突。

很多小朋友可能还是很迷惑，为什么叫Hash冲突呢，出现了hash冲突会导致什么问题？  
首先一点，**不同的key值会计算出相同的hashcode，这是产生hashcode根本的原因。**  
出现了hash冲突，就会导致，多个不同的key值，对应同一个桶。

**那么为什么不让每个key值都计算出唯一的hashcode呢？**  
如果这样，我向hashmap中存1万个值，我的bucket数组的长度就有1万，每次根据key去取值的时候，要从这1万个数组元素中去取，查询效率可想而知。  
这里的hashcode值，可以简单的想象成是根据key值和bucket数组的长度计算的模（可以理解成余数），根据这个模，找到存放entry的数组对应的index。（实际中更加复杂）  
如果当前桶中是空的，则直接添加。  
插入的时候，不会比较key值，只会比较key的hash值。

**那么hashMap中是怎么解决hash冲突的呢？**  
hashmap中通过链表和红黑树来解决hash冲突。

**为什么说HashMap是线程不安全的？**  
在接近临界点时，若此时两个或者多个线程进行put操作，都会进行resize（扩容）和reHash（为key重新计算所在位置），而reHash在并发的情况下可能会形成链表环。  
个人见解：  
在多个线程向hashmap中同一个空位插入数据时，刚好出现hash冲突，可能会出现相互覆盖的情况。

**什么时候会进行扩容，会导致什么问题？**

源码：

/**
         * The default initial capacity - MUST be a power of two.
         * 初始容积的大小16，必须是2的平方。这和操作系统的位移计算有关
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
      /**
         * The load factor used when none specified in constructor.
         * 负载因子，可以理解成扩容的阈值
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
       /**
         * The bin count threshold for using a tree rather than list for a
         * bin.  Bins are converted to trees when adding an element to a
         * bin with at least this many nodes. The value must be greater
         * than 2 and should be at least 8 to mesh with assumptions in
         * tree removal about conversion back to plain bins upon
         * shrinkage.
         *  当链表的长度大于这个值时，将链表转化为红黑树
         */
        static final int TREEIFY_THRESHOLD = 8;

核心put方法分析：

/**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }

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为空或者长度为0，先进行扩展resize
            if ((tab = table) == null || (n = tab.length) == 0)
               //初次扩容n等于8
                n = (tab = resize()).length;
            //如果链表数组尾部为空，则直接保存
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {//链表数组尾部不为空
                Node<K,V> e; K k;
                //如果链表尾部元素的hash值和插入元素的hash值相等，且key的内存地址相等或key值相等，则e = p;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                   //如果p为树节点，则向红黑树中添加新节点e
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {//如果p不是树节点
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            //尾部节点的next添加新节点
                            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;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            #当链表的长度，大于threshold = loadFactor * 容量  时，进行扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

如果存在Hash碰撞就会以链表的形式保存，把当前传进来的参数生成一个新的节点保存在链表的尾部（JDK1.7保存在首部）。而如果链表的长度大于8那么就会以红黑树的形式进行保存。

扩容机制核心方法Node<K,V>\[\] resize()：  
HashMap扩容可以分为三种情况：

第一种：使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT\_INITIAL\_CAPACITY也就是16。同时threshold = DEFAULT\_INITIAL\_CAPACITY \* DEFAULT\_LOAD\_FACTOR = 12。

第二种：指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着  
threshold = 当前的容量（threshold）\* DEFAULT\_LOAD\_FACTOR。

第三种：HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。

这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3cxMDE0MDc0Nzk0_size_16_color_FFFFFF_t_70]: /images/20220220/a6a953b3f3444e6884116ae1dc47c4de.png