# HashMap笔记 ## Node类 Node类有hash、key、value、下一个节点地址等4个属性，可以构成一个单项链表，为HashMap中存储数据的基本类型 ```java static class Node implements Map.Entry { // 经过计算之后的hash值 final int hash; final K key; V value; // 链表中下一个节点的地址 Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } ``` ## TreeNode类 TreeNode类可以构成一个红黑数，为HashMap中链表树化之后的类型； ```java static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } } ``` ## HashMap属性 ### hash表 HashMap中有个table属性，用于存储键值对数据，即是hash表。 其类型为Node数组，数组中每个位置称为桶，桶中保存链表或者红黑树的头节点地址，组成了一个二维的数据结构， 数组的长度即为HashMap的表容量 ``` transient Node[] table; ``` ### 默认初始容量 默认为16，即不指定初始容量的情况下，hash表数组长度为16 ``` static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; ``` ### 最大初始容量 ``` static final int MAXIMUM_CAPACITY = 1 << 30; ``` ### 默认负载因子 负载因子用于计算hash表扩容值，当hash表桶数量大于 **负载因子与表容量的乘积** 时，需要对hash表进行扩容 ``` static final float DEFAULT_LOAD_FACTOR = 0.75f; ``` ###链表树化阈值 当hash表某个桶中的链表元素大于树化阈值的时候，且桶个树大于树化最小表容量的时候，就要将这个链表转化为红黑树。 这个值必须大于2，并且应该至少为8， ``` static final int TREEIFY_THRESHOLD = 8; ``` ### 非树化阈值 hash表某个桶中保存的是红黑树且树的节点个数小于非树化阈值的时候，红黑树将转化为链表 这个值应小于链表树化阈值，且最多为6 ``` static final int UNTREEIFY_THRESHOLD = 6; ``` ### 树化最小表容量 链表树化前需要判断是否达到了最小表容量，即判断hash表的大小是否大于这个值， 这个值应该大于等于4倍链表树化阈值，以避免调整大小和树化阈值之间的冲突 ``` static final int MIN_TREEIFY_CAPACITY = 64; ``` ### 负载因子 HashMap中空值扩容阈值的属性 ``` final float loadFactor; ``` ### 扩容阈值 控制hash表扩容的阈值，该值通过 负载因子 * hash表容量计算得到。 初始化的时候不指定表容量，这个值为0，初始化时指定表容量，这个值等于计算后的表容量， 但是第一次put的时候会将表容量与负载因子相乘计算并给这个树形重新赋值 ``` int threshold; ``` ### hash表操作次数 put、remove、merge、clear等操作都会使得该值增加， 在foreach、replaceAll等会影响hash表结构的操作期间，会判断这个值是否变化 ，如果变化了，会快速失败 ``` transient int modCount; ``` ## hash表索引计算&表容量为2的幂次方原因 元素在放入hash表中某个桶的时候，需要通过hash算法计算出桶位置，即hash表索引（数组下标）。 计算公式为 **hash & (table.length - 1)**。 如果hash表容量为2的幂次方，即table.length = 2^n，那么该公式即为计算hash值除以表容量后的余数。 通过%同样可以获取到余数，但是位运算更加高效，所以这里需要限定hash表容量必须是2的幂次方。 通过表索引公式，可以将任意hash值转变为0到表容量范围的整数，可以通过该整数直接为元素分配存储的桶。 通过简单的代码对公式可以进行验算： ```java public class Test { public static void main(String[] args) { int length = 16; for (int i = 0; i < 50; i++) { int hash = i & (length - 1); System.out.println(i + " -> " + hash); } } } ``` ## hash计算 HashMap中用于索引计算的hash值不是key的hash值，而是通过hash计算方法得到的。 算法为hash值异或hash值无符号右移16位后的值。 hash无符号右移16位之后，高16位会变为0，异或计算不会改变原hash值的高16位，但是会改变低16位， 将高16位与低16的特征将结合，使得hash值的低16位更加散列 当两个hash值高位不同，但是低位相同的时候，通过hash索引算法，高位会被屏蔽，得到的结果是相同的， 容易造成hash冲突，将低位特征与高位特征相结合可以减少hash冲突提高效率 ``` static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` ## 扩容 在HashMap添加数据的时候会做扩容判断，如**HashMap#putVal**方法中： ``` // size：hash表容量，即table数组的长度 // threshold：扩容阈值，一般为0.75倍表容量 if (++size > threshold){ resize(); } ``` HashMap的扩容逻辑在 **HashMap#resize** 方法中。 ``` // oldCap：旧表容量 // newCap：新表容量 // newThr 、oldThr：新旧扩容阈值 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { //扩容，新表容量*2 ，新阈值*2 newThr = oldThr << 1; } } ``` hash表容量限定都是2的幂次方，扩容时直接按位左移一位，即表容量乘以2. 但是在扩容之后，表容量变化了，表索引的计算结果也会改变。此时需要重新hash，并移动元素保存位置。 对于同一个链表的节点来说，索引计算结果也会改变，所以链表的节点也会移动位置。 但是容量以及索引计算公式都与2的幂次方有关，所以节点移动只有两种结果： 1是位置不变，2是移动到 **当前索引 + 旧容量值** 的桶上。 ``` if (oldTab != null) { //oldCap：旧表容量，遍历旧表数组，移动元素到新表上 for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null){ // 重新hash newTab[e.hash & (newCap - 1)] = e; }else if (e instanceof TreeNode){ //移动红黑树节点 ((TreeNode)e).split(this, newTab, j, oldCap); }else { Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 如果hash按位与旧容量值为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; } } } } } ``` ## 链表树化 当hash表中某个桶内的链表节点过多时，需要将链表转换为红黑树以提高查询效率，如在**HashMap#putVal**方法中： ``` //该循环体逻辑为：插入节点数据时，在hash表某个桶上的链表知道key值相同的节点或者找到节点末尾空位 //binCount：当前链表节点数量 //TREEIFY_THRESHOLD：链表树化阈值 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //在链表末尾添加节点 p.next = newNode(hash, key, value, null); //链表中节点数量大于树化阈值， if (binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); } break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){ break; } p = e; } ``` 在向hash表中插入数据的时候，如果插入位置是同一个桶的链表，那么会根据链表树化阈值，判断是否需要进行树化， 树化方法为**HashMap#treeifyBin**，在树化方法中还要先判断hash表容量是否大于最小树化表容量（默认为64）， 否则不会进行树化，而是进行表扩容。 ``` final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; // 如果表容量小于最小树化表容量，那么会先扩容，不会进行树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //重新hash扩容 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode hd = null, tl = null; do { TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } } ```