HashMap的实现原理详解(看这篇就够了)

　　一线资深java工程师明确需要精通集合容器，尤其是我今天谈到的Hashmap。

　　Java集合Hashmap的重要性不亚于Volatile并发编程的重要性(可见性和有序性)。

　　我将重点介绍以下9点：

　　1.Hashmap的数据结构

　　2.Hashmap核心成员

　　3.HashmapdNode数组

　　4.Hashmap的数据存储

　　5.哈希函数Hashmap

　　6.哈希冲突:链式哈希表

　　7.Hashmap的get方法：哈希函数

　　8.Hashmapput方法

　　9.为什么必须使用2个槽位数?^n?Hashmap的数据结构

　　首先，从数据结构的角度来看：Hashmap是:数组+链表+红黑树.8增加了红黑树部分的数据结构，如下所示:

　　这里有两个问题需要理解： 数据底层的具体存储是什么? 这种存储方式的优点是什么? 1.核心成员 默认初始容量(数组默认大小):16，方staticcc的整数次 final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static最大容量 final int MAXIMUM_CAPACITY = 1 << 30; 默认负载因子staticc. final float DEFAULT_LOAD_FACTOR = 0.75f;用于测量Hashmap满度的装载因子，当Map集合中存储的数据达到当前数组大小的75%时，需要扩展 链表转红黑树边界statictic final int TREEIFY_THRESHOLD = 8; 红黑树转离链表边界static final int UNTREEIFY_THRESHOLD = 6; transient哈希桶数 Node[] table; 实际存储的元素数transient int size; 当map中的数据大于此threshold时，它将扩展intt threshold 阈值 = table.length * loadFactor 2.Node数组

　　从源代码可以看出，Hashmap类中有一个非常重要的字段，即 Node[] table，也就是说，哈希桶数组显然是Node数组。 static class Node implements Map.Entry { final int hash;///用来定位数组索引的位置 final K key; V value; Node next;///链表的下一个Node节点 Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}

　　Node是Hashmap的内部类，实现了Map.Entry接口的本质是映射(键值对)。Hashmap数据存储1.哈希表来存储

　　Hashmap使用哈希表存储数据。

　　哈希表(Hash table，根据关键码值，又称散列表)(Key value)对于直接访问的数据结构，只要输入要找到的值即key，就可以找到相应的值。

　　哈希表实际上是由数组演变而来的数组扩展。可以说，如果没有数组，就没有散列表。2.哈希函数

　　哈希表中的元素是由哈希函数确定的。通过一定的函数关系(称为哈希函数)计算的值是该元素的存储地址。表示为：Addr = H(key),如下图所示：

　　哈希函数在哈希表中的设计非常重要，这也是哈希表建设过程中的关键问题之一。3.核心问题

　　在建立哈希表之前，有两个主要问题需要解决：

　　1)构建合适的哈希函数，均匀性 H(key)哈希表中均匀分布的值

　　2)处理冲突

　　冲突：在哈希表中，不同的关键字值对应于相同的存储位置。4.哈希冲突:链式哈希表

　　为了解决冲突，哈希表可以采用地址法和链地址法来解决问题，Java中的Hashmap采用链地址法。

　　简单地说，链地址法是数组加链表的组合，如下图所示：

哈希函数Hashmap /*** 重新计算哈希值*//static final int hash(Object key) { int h; // h = key.hashCode() 为第一步 hashCode值 // h ^ (h >>> 16) 为第二步 参与高水平的运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

　　//计算数组槽位 (n - 1) & hash

　　hashCode操作key，获得32位int值h，然后使用hashCode 异或 h>>>16位。在JDK1.8的实现中，通过hashCode()高16位异或低16位实现了高位运算算法的优化：(h = k.hashCode()) ^ (h >>> 16)。

　　这样做的好处是可以将hashcode的高低值混合做异或操作，混合后在低信息中加入高信息，使高信息变相保留。

　　也就是说，在计算下标时，也参与了hash的16位高度，掺杂了更多的元素，因此生成hash值的随机性会增加，减少hash的碰撞。

　　备注： ^异或：不同为1，相同为0 >>> ：无符号右移:右补0 &运算：两人同时为“1”，结果为“1”，否则为0

　　h & (table.length -1)获得对象的保存位置，而HashMap底层数组的长度始终为2的n次方。为什么槽位数必须使用2^n?1.为了使哈希后的结果更加均匀

　　如果槽位数不是16，而是17，则槽位计算公式为:(17 – 1) & 从上面可以看出，计算结果将大大趋同，hashcode将参与&操作结束后，它被更多的0屏蔽，只剩下两个0和16个计算结果，这对hashmap来说是一场灾难。2.等同于length取模

　　当length总是2的n次方时，h& (length-1)计算等同于length取模，即h%length，但是&比%效率更高。

　　由于算术运算仍将转化为位运算，位运算的运算效率高于算术运算。

　　最终目的是使哈希结果分布更加均匀，减少哈希碰撞，提高hashmap的运行效率。分析Hashmapput方法： final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 目前对象的数组是nulll 或者当数组长度为0时，数组需要初始化 if ((tab = table) == null || (n = tab.length) == 0) { n = (tab = resize()).length; } // 使用hash与数组长度减一的值进行差异或分散的数组下标，预示着现在的计算是按照计算的 // key将存储在这个位置，如果这个位置没有值，那么直接建立一个新的k-v节点存储 // 其中，长度n是2的幂次数 if ((p = tab[i = (n - 1) & hash]) == null) { tab[i] = newNode(hash, key, value, null); } // 假如走到else这一步，就意味着key索引到的数组位置已经存在内容，即发生碰撞 // 此时，处理碰撞需要更复杂的方法，如链表和树木 else { Node e; K k; ///节点key存在，直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { e = p; } // 判断链条是红黑树 else if (p instanceof TreeNode) { // this表示，目前的Hashmap， tab是map中的数组 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); } else { // 判断链是链表 for (int binCount = 0; ; ++binCount) { // 若当前碰撞节点没有后续节点，直接新建节点并添加节点 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD = 8 // 从0开始，如果到了7，说明满8，这个时候需要转 // 重新确定是扩容还是转用红黑树。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 在发现碰撞节点时，key完全相等的节点用新节点代替旧节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 此时e是保存的碰撞节点，即旧节点 if (e != null) { // existing mapping for key V oldValue = e.value; // onlyIfabsent是该方法的调用参数，表示是否替换现有值， // 这个值在默认的put方法中是false，因此这里将用新值替换旧值。 if (!onlyIfAbsent || oldValue == null) e.value = value; // Callbacks to allow LinkedHashMap post-actions afterNodeAccess(e); return oldValue; } } // map变性操作计数器 // 例如，map结构化的变化就像内容增减或rehash，这将直接导致外部map并发 // 迭代导致fail-fast问题，这个值是比较的基础 ++modCount; // size即map中k-v的数量是多少? // 超过最大容量 就扩容 if (++size > threshold) resize(); // Callbacks to allow LinkedHashMap post-actions afterNodeInsertion(evict); return null;}

　　Hashmapput方法的整体实施过程如下：

　　①.判断键值对数组table[i]是空还是null，否则实施resize()扩容;

　　②.如果tabley根据键值key计算hash值得到的数组索引i[i]==null，直接添加新节点

　　③.判断table[i]如果直接覆盖value，第一个元素是否与key相同

　　④.判断table[i] 是否为trenode，即table[i] 是红黑树吗?如果是红黑树，直接将键值插入树中

　　⑤.table遍历[i]，判断链表长度是否大于8。如果大于8，将链表转换为红黑树，插入红黑树，否则插入链表;如果在整个过程中发现key已经直接覆盖value;

　　⑥.插入成功后，判断实际键值是否超过最大容量threshold，如果超过，则扩大容量。Hashmap总结

　　HashMap底层结构?数组+链表的结构是基于Map接口的实现，JDK 1.8后加入红黑树，链表长度>8变红黑树,<6变链表

　　两个对象的hashcode会发生什么? Hash冲突，Hashmap通过链表解决hash冲突

　　HashMap 中 equals() 和 hashCode() 它有什么作用?HashMap 添加和获取需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的相同位置。冲突(碰撞)发生时使用 key.equals() 方法去链表或树找到相应的节点

　　HashMap 什么时候扩容?当put元素达到容量乘载因子时，默认为16*0.75

　　hash 的实现吗?h = key.hashCode()) ^ (h >>> 16)， hashCode 右移无符号 16 位，然后按位异或得到这个键的哈希值，因为哈希表的容量是 2 的 N 次方，在当前，元素 hashCode() 在很多情况下，低位是一样的，这会导致冲突(碰撞)，因此 1.8 以后做了一个移位操作:元素 hashCode() 和自己右移 16 位后结果求异或

　　Hashmap线程安全吗?Hashmap读写效率高，但由于不同步，即读写操作无锁保护，在多线程场景下不安全，容易出现数据不一致的问题，强烈建议在单线程场景下使用。

　　以上是Hashmap的介绍，希望对你有所收获!