HashMap是Java里使用频率非常高的集合类型,基本的组成元素为Bin
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
先看签名,HashMap继承自AbstractMap,实现Map接口,可被序列/反序列化。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
-
DEFAULT_INITIAL_CAPACITY:
默认初始化大小是16 -
MAXIMUM_CAPACITY:
最大容量是2的30次幂 -
DEFAULT_LOAD_FACTOR:
默认负载因子是0.75,代表如果容量如果超过最大容量的百分之75就会进行resize,对当前HashMap实例进行扩容 -
TREEIFY_THRESHOLD:
顾名思义,在一个桶中大于8个Bin后从List类型转变为Tree类型,推测为自动平衡二叉树,即,红黑树 -
UNTREEIFY_THRESHOLD:
这里考虑到在8这个临界点之间来回变动会有很大的性能开销,所以设置了这个参数,默认为6,在小于这个值的时候才会将Tree转为List -
MIN_TREEIFY_CAPACITY:
桶中最小Bin容量,如果大于这个值会进行扩容,这个值最少为TREEIFY_THRESHOLD的4倍,即32
在初始化HashMap的时候,有两个因子对性能影响非常大,一个是初始化的大小,另一个是load factor,负载因子,其中0.75是一个权宜之值,即考虑了查找时间成本也照顾了空间成本。如果有很多不同的keys映射到了相同的hashcode上,那么java 1.8以前会讲这些entry全部放到同一个bucket桶下,按照链表结构来排序,1.8以后做了优化,会采用红黑树的结构在动态平衡查找效率,这里有个小知识点,就是如果这些keys是Comparable
的,那么在同一个bucket下会按照排序大小来进行排序。
絮叨完后,我们先简单总结下,HashMap有这么几个很重要的概念:
- Node:内部类,用于保存Entry的
- Entry:一个由
<key,value>
组成的对象,value就是具体的数据,可能是基础类型,也可能是一种对象 - Bucket/Bin:中文翻译过来叫桶,桶是用来存储具体Entry的容器,可以把它理解为一个List链表,具体实现在1.7以前就是单纯的以Node为节点的单向链表,1.8以后为了更好的查找性能引入了红黑树,如果链表的长度过长,如上文提到的
TREEIFY_THRESHOLD
就会自动把这个桶改变成红黑树结构,如果元素被删除过多比如低于UNTREEIFY_THRESHOLD
,那么就没有必要保留这种结构,因为红黑树带来的不好的地方是,除了查找效率高,插入删除有可能每次都会做左旋右旋等平衡操作,个数少的时候还是链表比较方便。 - Hashcode:哈希码,有两个哈希码,一定要区分,一个是要保存或插入对象本身的hashcode,还有一个是对象要插入到HashMap中计算后得到的hashcode,下面我们通过put,get,remove等增删查操作细细地说。
好,说完HashMap的元素及类型,现在说说它的常规操作:
put 添加记录操作
签名为:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用的putVal,倒数第二个false
代表着如果插入的key一样,则直接替换,最后一个true
代表如果是false,则开启创建模式。
在插入的时候,先根据key
计算出key的hash,计算方式是:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
把key的hashcode的低16位与自己的高16位做异或操作返回一个int值。
然后用长度下标和这个hash值做与(&
)操作,这样的话就相当于每次对桶做查找操作的时间复杂度始终是O(1)
,听我细细来讲,这里是HashMap的一个精髓的地方:
首先HashMap的长度永远都是2的指数倍,这么做的道理就来源于二进制,只有这样,在与key的hash结果做与操作的时候才可能立刻得到一个确定的数,这个数就是桶的编号,比如,长度为16,二进制表示为10000
,它再减一就是1111
,那么它在和一个int
类型的数字&
的时候,会把所有为0的位数置为0,1则不动,从而得到一个在0
~16
之间的数字。看代码:
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
tab
就是Node
组成的数组,n
就是数组的长度(永远为2的倍数),如果这里返回null
证明该Node还没被人使用,可以创建新Node。
如果这里p不为空,证明该桶已经被人占了,hashcode出现了冲突,注意这里是put的key的hash,而不是value的hash,那么如果有冲突我们怎么解决冲突呢?常见的做法就是把这个桶变成一个链表,我们看下Node
的结构就不难发现,它是内部类,并且有一个变量是next
,就是用来做链表指向下一个的。
我们接着看代码:
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
...
}
首先判断当前这个桶中第一个节点,即表头的hash和要插入的key的hash一样不一样,如果一样并且两个key相等,就先暂时保留为变量e
。
接下来如果发现这个桶是个红黑树结构,则进行红黑树的值插入操作,这里先暂不展开。
最后如果以上都不满足,那么会遍历这个链表,如果遇到相同的key的就做值替换,如果没有就在尾部插入一个新节点(如果超过TREEIFY_THRESHOLD
则把链表转变为红黑树)。
这里有个点需要提一下,就是
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
除了先判断两个hash相等外,还要判断这两个key到底是不是相等,这么做的目的应该就是先做粗略比较,两个key的摘要一样吗,如果一样说明要么哈希算法冲突,要么这俩就是一模一样,所以才有后续继续比较值的操作。
最后的最后:
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;
判断这个e
是不是不为null
,不为空那么就意味着key相等,那么就可以根据参数做替换value
的操作了。
++modCount
,如果这个值变了会导致对map做遍历的时候fast-fail,立刻抛出ConcurrentModificationException
异常
threshold
就是一个阈值,大于它则需要做resize操作,即扩容。关于扩容以及扩容导致的死锁我们在下文讲。
resize()
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
resize
用来初始化或者double表的大小,此处的table就是前文提到桶的引用,即那个Node数组。如果为空的话则按照指定的容量进行初始化,否则就扩容到之前的两倍,并且原有HashMap中的元素还要保留在原有的index,或者移动到2的指数倍的偏移位置。先上流程图,我们再细细讲里面的难点。
其中在对老的数据做迁移的时候有一些技术点需要注意,就是怎么迁移过去。
- 如果这个桶中只有一个元素,不是一个链表或者红黑树的话,最简单,用这个元素的hash值和新大小减一做与
&
操作,得到一个数据下标index,直接放入即可。 - 如果这个桶下面挂的是一个树,那么把树做拆分,由于这是1.8新引入的改进,是一个优化手段,所以这里先暂不讨论。
- 如果桶下面是一个链表,那么由于新的容量是老的容量的两倍,先把新HashMap的桶数据,分成两半,一个叫high,高位区,另一个叫low,低位区。再用循环遍历这个桶下的每个元素,如果遍历到的元素的
hash
哈希值对老的容量oldCap
做与&
操作得到0,则证明这个元素的哈希值不需要移位,直接放入低位区即可,否则放入高位区。这里需要举个例子,假如之前a
值是17,b
的值是1,这两个数在容量为16的HashMap
中的哈希值都是1,都会被安排到index为1的这个桶中,而在扩容到32的时候,则会把17放到高位区。
直接看核心代码:
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> 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;
}
最后有一个小知识点就是,HashMap在resize的时候可能会出现死循环,这个很好理解,比如之前桶1下的节点本来是A -> B -> C,一个并发的resize就很有可能导致死循环,比如可能会变为A -> B 而resize过程中B被移到了另一个桶并指向了C,而原来的C也做了resize操作并且指向了B,这样遍历的时候就变成了死循环。
get 查看记录
HashMap
的get返回是有可能为null
的,而这个null,可能代表这个key没有找到,也可能代表这个key对应的就是null
,为了区分这俩可以用containsKey
。
- 首先计算key的hash值,按照HashMap中的老办法,高位下移,与低位异或得到hash值。
- 做null值判断,如果匹配到了桶再做处理
(tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null
table,即HashMap内部桶数组不为空,并且长度大于0,并且tab[(n - 1) & hash]
是有值的,就是说这个hash对应的桶里是有货的,至于是一个还是多个,还得接着走。
- 这不接着就来了个是否为多个的判断
(e = first.next) != null
,如果多个就遍历,最后判断是否为要取的对象还是通过e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
,即要找的key的hash值和当前的hash值一样,到这步了,那么肯定是一样的,再判断key的值是一样或者一模一样的引用,比如都是"AAA"或指向同一个实例之类的。
remove() 删除节点
这里就不再赘述了,有了put和resize的功底,再理解remove就不再难了,无非就是找到这个节点,如果是单个,就直接删除,如果是链表或者树,就利用树的删除节点操作和链表的删除节点操作,干点这个节点即可。最后modCount
和size
都要相应的变化。如果找到并删除了则返回这个节点,如果没有则返回null
。
这里最后留几个问题给自己:
1. 为什么hash的算法是这样的,要对高位做移位操作然后XOR
异或?
2. 为什么再resize后,有些节点会被移到高位区,而有些节点会保留原有的位置?
下篇回答这个问题!
网友评论