JAVA笔记-容器篇-HashMap详解
在讲技术前有必要讲一下这篇文章的由来。写java的朋友,无论是客户端还是服务端,HashMap基本上都最常用的java容器了,正因为最常用,所以我们需要去了解的更深,对代码优化和规范都有好处。
前言
在讲技术前有必要讲一下这篇文章的由来。写java的朋友,无论是客户端还是服务端,HashMap基本上都最常用的java容器了,正因为最常用,所以我们需要去了解的更深,对代码优化和规范都有好处。网上关于 hashmap 的讲解也铺天盖地多的是,那为什么我还要写一篇这个呢。原因主要在于你可以看网上任何的一篇讲 hashmap 的文章,远远没有这篇文章带给你的清晰和完整,甚至可以让你靠近人家在开发 hashmap 时用到的思维模式。
说明:以下汇总下jdk1.8以及之后版本中的 HashMap 实现。
简介
首先用一句话说明 HashMap 的结构:
数组+链表,即数组中存放的是指向链表的指针,当链表中数据大于阈值(默认为8),用红黑树代替链表。
上面出现了3个结构:数组、链表和红黑树。那么下面依次说明各个结构在 HashMap 中的具体应用。
数组
HashMap 中的数组也被叫做哈希桶,本质上是一个 Node 类型的数组。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}
可以看到 Node 中存放着 key,value 以及一个 hash 值。这个 hash 值的作用就是为了确定指定的 key 存放在数组中的哪个桶,它的具体实现:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从这个 hash 函数中我们可以看到2点:
- key 允许为null,为 null 时存放在数组的第一个桶(下标为0)中。
- 用到了 key 对象的 hashCode 方法获取对象的 hash 值,然后运用了一些位运算计算下标。
java 中 int 4个字节,h>>>16
相当于获取 h 的高位部分,之后的位运算是将 key 的 hashCode 与其高位异或操作,相当于将高位和低位综合一下,为了减少 hash 碰撞的记录。最终这个扰动函数计算出来的 hash 值会跟数组长度进行求余操作来获取 key 存放的桶下标:
// & 可以用来取余,i 就是计算出的数组的下标
i = (n-1) & hash
为什么需要将高低位异或?因为hashCode()是int类型,取值范围是40多亿,只要哈希函数映射的比较均匀松散,碰撞几率是很小的。但是由于HashMap的哈希桶的长度远比hash取值范围小,默认是16,所以当对hash值以桶的长度取余,以找到存放该key的桶的下标时,由于取余是通过与操作完成的,会忽略hash值的高位。因此只有hashCode()的低位参加运算,发生不同的hash值,但是得到的index相同的情况的几率会大大增加。
链表
hash 函数总是有可能会存在冲突的,当两个不同的 key 计算的 hash 值相等时,此时它们对应数组的下标也就相等了。因此我们就需要将数组中的元素以链表的方式串联起来,这就是 Node 结构存在一个指向下一个节点的 next 字段的原因。其中新建的 Node 会插入到链表的尾部。
// 取一段 put 方法中插入到链表尾的代码
Node<K,V> e; K k;
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;
}
思考一下为什么要插入到链表尾部,而不是头插法(插入到头部)呢?
让我们来算下时间复杂度,尾插法需要遍历整个链表,时间复杂度为O(N),头插法只需要将数组下标中值存放成新 Node,然后将新 Node 的 next 指向旧的头,复杂度为O(1),明明头插更快啊,为什么会变成尾插呢?答案请看扩容章节。
红黑树
上面的代码中我们还能看到一个常量 TREEIFY_THRESHOLD
,它指代的是链表的最大长度,超过这个长度后链表需要被转化为红黑树,默认这个变量为 8。
static final int TREEIFY_THRESHOLD = 8;
什么是红黑树?请看我之后的数据结构篇。
为什么要把长的链表转换成红黑树呢,因为你们可以看到上面的插入操作在查找的过程中用了一个 for 循环找到尾部,时间复杂度是O(n),而红黑树可以让搜索的复杂度降到O(logn),对于数据量大的情况,效率下降的比链表慢。
下面是链表转换为红黑树的过程:
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 将链表 Node 替换成 TreeNode
TreeNode<K,V> 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);
}
}
扩容
当我们不断的往hash桶放数据,整个桶会变得越来越臃肿,操作效率大幅降低,这时候我们需要去给 hashmap 扩容。
假定 hashmap 的容量是 capacity,目前存放着 size 个元素,当 size > threshold 时,hashmap 需要扩容,threshold = capacity * load factor
。load factor 是负载因子,默认是 0.75。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 很多地方通过如下判断进入 resize 流程
if(size > threshold) resize();
关于容量,大家都知道 hashmap 的默认容量是 16。你有想过为什么是16吗?这其实还是要回过头看到我们计算数组下标的代码 (n-1) & hash
, n 指代容量,只要n是2的幂,那么 n-1肯定是一个二进制值全为1的数字.例如 n = 16,那么 15 的二进制就是 1111,1111 与其他数 & 操作后的值就是后4位本身的值,所以达到最终目的,均匀的 hash(你可以对比下用 5,7等数跟别的数 & 的结果,碰撞几率明显上升)。而 16 恰巧是那个合适的默认值,不大不小。这个道理跟负载因子是 0.75一样,为啥是 0.75 呢,也是折中过后取的值,如果因子为1,那么允许不扩容的大小就越大,hash 碰撞发生几率高,如果小了,动不动就扩容也不行,内存消耗大了(我猜测 0.75 应该是专家实验统计出来的结果)。
hashmap 中还存在一个最大容量的常量,值是 2^30 次方,当容量到了这个级别就不会在扩容了。正常情况下,扩容时会先创建一个长度为原来2倍的数组,然后经过rehash 把原先的Node放进新数组中。
下面看下 resize 的具体过程:
final Node<K,V>[] resize() {
Node<K,V>[] 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
// 如果之前的容量是0,初始化为默认的容量
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// rehash到新的数组
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;
}
大家可以看到 rehash 的部分也是尾插的形式重新生成链表,由此它保证了 Node 的顺序依然是之前链表的顺序,如果是头插呢,顺序就变了。顺序变了会产生什么样的问题呢:可能会导致 resize 死循环。
尾插法:
原链表 1->2->3->4
rehash后链表可能是
1->2->3
4
头插法:
原链表
1->2->3->4
rehash后链表可能是
3->2->1
4
头插法中死循环是怎么发生的?
假设现在是头插法有2个线程,线程A resize 执行遍历到了1,然后线程B执行,执行完了整个 resize,链表变成了 3->2->1。然后线程A回来继续执行,那么它在rehash 1后继续rehash 2,这时候发现2的next是1,这就形成了一个环,所以会一直循环下去直到资源耗尽。而尾插法很好的避免的这个问题,所以即使牺牲了一点点搜索的性能(也没有差很多),解决了这个多线程的问题。
由此你也能看到,hashmap 是线程不安全的。想要用线程安全的 hashmap 就用 ConcurrentHashMap,它给很多操作都加了同步锁,具体细节之后请关注多线程篇。