一 HashMap介绍
- HashMap存储key-value键值对；
- 关键参数
- capacity：哈希表中桶的个数
- loadFactor：加载因子，表示哈希表可以多满。数目大于
capacity*loadFactor时，2倍扩容rehash；
- 实现
- jdk1.7：数组+链表
-
jdk1.8：数组+链表/红黑树（链表长于8时变为红黑树,红黑树小时变为链表）
二 HashMap主要函数实现
1）put
- jdk1.7 添加节点时，插入链表头部；
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } - jdk1.8 链表添加节点时，插入链表尾部；
Node<K,V> 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) //判断该链为红黑树 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); //链表长度大于8转换为红黑树进行处理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key已经存在直接覆盖value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //新节点插入最后 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }
2）扩容
- jdk1.7：对于每个key-value重新哈希计算位置，注意插入链表头部，链表被反转；
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
jdk1.7扩容例图.png
-
JDK1.8：计算哈希位置优化
由于是2倍扩容，只需要考虑对应增长的这一位是0还是1,如果是0桶的位置不变化，如果是1桶的位置+oldCapcity；
因此不需要每一个重新计算哈希值
final Node<K,V>[] resize() { ... 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; do { next = e.next; if ((e.hash & oldCap) == 0) { // 桶index不变化 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 桶index变化 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; }
3）安全性问题
-
JDK1.7实现，多线程重哈希会导致循环链表问题。 疫苗：JAVA HASHMAP的死循环
原因在于：rehash时，node节点会插入链表头部do { Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null);线程2执行完毕后效果：
线程1恢复继续执行，产生循环链表；
-
JDK1.8实现，我认为不会出现循环链表的问题，多线程不安全是肯定的；
JDK1.8桶中链表的顺序会维持，因此不会出现1.7中后节点移到前节点的前边，循环链表的风险。//某个桶里的链表处理过程： 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; }
@梦工厂 2018.3.20
