hashmap底层原理
文章目录
- 1、底层数据结构
- 2、为什么不用二叉树/平衡树呢？
- 3、hashmap的put方法
- 4、神奇的地方
- 1、扰动函数
- 2、为什么 hash 值要与length-1相与
- 3、HashMap数组的长度为什么是 2 的幂次方？
1、底层数据结构
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
- 当链表超过 8 且数据总量超过 64 才会转红黑树。
- 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
jdk1.8中的数据结构示意图如下：
其中，数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。
那为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?
- 因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。
2、为什么不用二叉树/平衡树呢？
红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
为什么不用二叉树：
红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。
之所以不用平衡二叉树：
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。
3、hashmap的put方法
以JDK 8为例，简要流程如下：
- 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}bucketIndex = indexFor(hash, table.length);static int indexFor(int h, int length) {return h & (length-1);
}
- 如果数组是空的，则调用 resize 进行初始化；
if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
- 如果数组不是空,并且没有哈希冲突直接放在对应的数组下标里；
if ((p = tab[i = (n - 1) & hash]) == null)// 创建一个新的结点存入到数组中tab[i] = newNode(hash, key, value, null);
- 如果冲突了，先判断该位置上原来的key的hash值和插入的key的hash值是否相等&&两个key是否是同一个对象，如果成立，则覆盖掉之前的value
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))/*说明：两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录*/ e = p;
- 如果步骤4不成立，发现该节点是红黑树，就将这个节点挂在树上；
// hash值不相等或者key不相等；判断p是否为红黑树结点else if (p instanceof TreeNode)// 放入树中e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
- 如果冲突后是链表，遍历链表的每个节点，如果遍历到了链表尾部，则创建链表节点，向后添加新的元素。插入后，判断该链表的长度是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于等于 64，则将这个结构转换为红黑树；
if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//这里只体现了链表长度是否大于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 转换为红黑树treeifyBin(tab, hash);// 跳出循环break;
}--------
final void treeifyBin(Node[] tab, int hash) {int n, index; Node e;/*如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64)，就去扩容。而不是将结点变为红黑树。目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。*/if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//扩容方法resize();.....
}
如果没有遍历到链表末尾，则继续判断链表中结点的key值与插入的元素的key值是否相等。若key相等，就覆盖掉 value。
if (e != null) { // 记录e的valueV oldValue = e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)// 用新值替换旧值// e.value 表示旧值 value表示新值 e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}
4、神奇的地方
1、扰动函数
相关代码：
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。如图
右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
这样设计降低了哈希碰撞的概率。
2、为什么 hash 值要与length-1相与
当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。
bucketIndex = indexFor(hash, table.length);static int indexFor(int h, int length) {return h & (length-1);
}
HashMap 的数组长度是2 的整数幂，这样（数组长度 - 1）正好相当于一个 “低位掩码”。与 操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和前面的散列值做 与 操作如下，结果就是截取了最低的四位值。
3、HashMap数组的长度为什么是 2 的幂次方？
2 的 N 次幂有助于减少碰撞的几率。如果 length 为2的幂次方，则 length-1 转化为二进制必定是11111……的形式，在和hash的二进制与操作效率会非常的快，而且空间不浪费。
当 length =15时，6 和 7 的结果一样，这样表示他们在 table 存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，4和5的结果也是一样，这样就会导致查询速度降低。
如果我们进一步分析，还会发现空间浪费非常大，以 length=15 为例，在 1、3、5、7、9、11、13、15 这八处没有存放数据。因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。