# HashMap ![image-20220303195122934](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-ee672d41b4731f57032415cfca0ef666e8f02044%2Fimage-20220303195122934.png?alt=media) ![image-20220303195144762](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-dd1c1da44678d79d9fadcb2a79bb30c8b3c26fee%2Fimage-20220303195144762.png?alt=media) ![image-20220303204913944](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-02770fee1eab8f70b5a42ee10f2d1b2fb1c15fc9%2Fimage-20220303204913944.png?alt=media) HashMap采用Hash表存储数据，由数组+链表的结构生成。数组的位置由key的hashcode的方法生成，每个数组位置存储一个`Entry`对象。因为数组的位置是由hashcode通过特定的算法生成的，所以会发生hash冲突。 当发生hash冲突时，将会把新的元素对象通过链表的方式连接到目标数组元素的首部/尾部（jdk1.7采用头插法，jdk1.8采用尾插法），当链表的长度大于8时，链表将会转换为红黑树。 ## 源码解析 ### 主要的属性 使用hash表存储，容器是一个数组： ![image-20220303205821623](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-ff039fcc1979f8115e06da25532a4d6497f3f158%2Fimage-20220303205821623.png?alt=media) 实际添加的元素数量由size属性记录： ![image-20220303212020870](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-1b82589fb7730033517378688804a1e9d251af2b%2Fimage-20220303212020870.png?alt=media) 数组的默认容量： ![image-20220303212151067](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-b9c5b7d4e93c1df069c5482ec4dff0317a656230%2Fimage-20220303212151067.png?alt=media) 数组的最大容量： ![image-20220303212233878](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-33cb1450eda9cf4f8727b0a4077ca43f828e0cb9%2Fimage-20220303212233878.png?alt=media) 当向数组中不断的添加元素时，超过`threshold`扩容边界，就会发生扩容： ![image-20220303212554036](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-70ecb19c0cee77c2980158c99b43be24559946e7%2Fimage-20220303212554036.png?alt=media) 而扩容边界是由扩容因子决定，`threshold = 当前数组的容量 * loadFactor` ： ![image-20220303212800177](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-3e8d90b2dc3c9ed28f70216f487af2c3c9d4ca31%2Fimage-20220303212800177.png?alt=media) 默认的扩容因子值为 `0.75`，如果是一个`16`容量的数组，当用了`12`个容量位置时（`16 * 0.75 = 12`），就会触发扩容操作。 ![image-20220303212835564](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-eea48bfe9c28aafded45b177aea3b054ac022e84%2Fimage-20220303212835564.png?alt=media) **实际扩容时，将会按照二倍扩容的方式对数组进行扩容。** ### 构造器 ![image-20220303211421278](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-0102a7b2e968718f15c1454ea8e47f3ba0006be8%2Fimage-20220303211421278.png?alt=media) 分别指定`初始容量`以及`扩容因子`，如果不传则使用默认值`16`以及`0.75`。 其中边界值`threshold`的大小生成是通过如下方法决定的，他始终会返回一个`2^n`的数： ![image-20220303214347562](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-19ca4f1e94f616064fd55a8bedc86fa8e0716f1b%2Fimage-20220303214347562.png?alt=media) ### put方法 ![image-20220303214453686](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-22fe17d0848d0fe72c278da3213512d3b0f3aed7%2Fimage-20220303214453686.png?alt=media) 其中，使用key计算目标的hash值（使用key的hashCode右移16位）： ![image-20220303215322600](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-c5fba3a01bb60a5342a5943a592470a4099e1cc8%2Fimage-20220303215322600.png?alt=media) 然后调用putVal方法，其中，`putVal`方法的具体逻辑如下： ```java final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 如果hash表（也就是数组table）为空，先初始化hash表 // resize方法会对 table 成员变量进行初始化 // 最后获取新的hash表的容量n if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 计算目标key在数组中的位置索引 i 变量， (n - 1) & hash，等效于 hash % length // 取出 i 位置的元素 p // 如果 p == null，说明没有发生hash冲突 // 则创建一个Node对象，并放入到数组中 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 否则发生了hash冲突 else { Node e; K k; // 如果原位置的p，这个节点的key与新添加的key的值相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果原位置的p，这个节点类型是 TreeNode，说明p处在红黑树中，将目标元素放入到红黑树中 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 如果原位置的p，这个节点类型是链表 else { // 从头至尾遍历链表 // 如果遍历到尾部没有发现key相同的情况，就创建一个Node，将其添加到链表的最后（尾插法） // 插入完成后，判断当前链表的长度，如果当前链表的长度大于 TREEIFY_THRESHOLD - 1 // 则触发链表转换红黑树的操作 // 因为到达了链表结尾，所以e对象一定为null // 但如果这个过程中发现了目标key与当前key相同的情况 // 结束循环，获取与之相同的这个节点e // 此时e一定不为null for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } } // 如果e不为空，就代表存在相同key的情况 // 将这个对象的值替换为新的value，并返回旧的value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } ``` ### resize 数组的扩容 ```java final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; 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 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { 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; } ``` ## 加载因子为什么是 0.75 如果扩容因子为1： 只有到16位置都满了之后才会发生扩容。虽然这时候空间利用率极大，但是会很容易发生hash碰撞，特别是剩余的空间不多时，这时候查询效率就会越低。 如果扩容因子为0.5：这时碰撞的概率极低，所以产生链表的概率也低，查询效率极高，但是空间利用率极低。 0.75是对时间与空间的成本上的折中。 ## 主数组的长度为什么必须为2的n次方？ 1. 确定目标key在数组的位置上是使用 `(length - 1) & hash`的方式产生的，等效于`length % hash`，而如果length的长度不是2的次幂，则这个等效就不会成立 2. 为了防止hash冲突 ![image-20220303225229365](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-b999c52e9ccf08e137571f075ff04c9cf66055ba%2Fimage-20220303225229365.png?alt=media)