1. 概述
平常我们开发中,可能用的最多的容器就是HashMap。我们来看下HashMap的结构如下图。
它是由一个Node数组,每个数组元素又是有一个链表构成。接下来我们结合源码来分析下put(),get(),resize()者三个常见的操作。
2. 类成员变量的认识
|
|
- 关于红黑树的介绍,参见我的下篇文章,红黑树的原理及常见的操作
3. put()函数的解析
put()添加操作的过程如下。 - 对key的hashCode()做hash,然后再计算index(求余);
- 如果没碰撞直接放到bucket里;
- 如果碰撞了,以链表的形式存在buckets后;
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity),就要resize。
其他的解释都在源码中标注。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556public V put(K key, V value) {//对key的hashcode做hashreturn putVal(hash(key), key, value, false, true);}//onlyIfAbsent为true时,相同的key不会改变替换值。这里的为false,会替换//evict表示模式,为fasle表示处于bucket处于创建阶段。这里用true指创建完了。final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)//若为null,则创建bucketn = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//若bucket那个位置为null,则创建新的Node节点tab[i] = newNode(hash, key, value, null);//表示bucket不为nullelse {Node<K,V> e; K k;//key存在if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//若原来为TreeNode,则插入到红黑树种中else if (p instanceof TreeNode)e = ((TreeNode<K,V>)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);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//写入,若原来有值,则替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//若超过当前容量大小超过capacity*0.75,则会引起扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
注意这里采用的二次hash()操作,不是直接对hashcode再hash。
- 之所以这样hash,是采用key的hashcode的低16位和高16位做异或操作。这样的好处在于避免hash冲突。否则,它只取低16位,与高位无关,那么它有可能会hash冲突严重。另外,如果还有更严重的冲突,那么可以采用红黑树来解决,事实上Jdk1.8 HashMap也是采用的这样的思想。
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
4. get()的解析
get()相对来说就非常简单了,过程如下。
- bucket里的第一个节点,直接命中;
- 如果有冲突,则通过key.equals(k)去查找对应的entry
- 若为树,则在树中通过key.equals(k)查找,O(logn);
- 若为链表,则在链表中通过key.equals(k)查找,O(n)。12345678910111213141516171819202122232425262728public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//这个if判断bucket是否存在if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//检查第一个Node(bucket中第一个节点)是否是要查找的。if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {//红黑树的查找keyif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//遍历链表,寻找key相同if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
(n - 1) & hash
就是一个求索引,即求Node数组中的下标。这样的操作是,当我们的n(表示capacity时)取2的幂的时候,例如n取16,那么n-1=15(二进制表示1111)与hash做与操作的时候相当于取余,这样做比直接取余更高效。
5. reSize()的解析
- 当put时,如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例,那么就会发生resize。在resize的过程,简单的说就是把bucket扩充为2倍,之后重新计算index,把节点再放到新的bucket中。
- 然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在(原位置+旧capacity)的位置。
怎么理解呢?例如我们从16扩展为32时,具体的变化如下所示: - 这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图:
|
|
参考文章: