jdk源码解析二之HashMap

这里写自定义目录标题

HashMapputremovereplaceget扩容resize迭代器总结什么时候采用红黑树?为什么每次扩容后,是2的幂次方?为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存?为啥用尾插法?为什么线程不安全?

HashMap

HashMap的loadFactor为什么是0.75？ 主要涉及到泊松分布的概念,猝!!!

一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，得到这个loadfactor的值为log（2），约等于0.693. 同回答者所说，可能小于0.75 大于等于log（2）的factor都能提供更好的性能，0.75这个数说不定是 pulled out of a hat。

put

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; //当key为null,默认存在0索引线性表 //（因为hashCode是一个int类型的变量，是4字节，32位，所以这里会将hashCode的低16位与高16位进行一个异或运算，来保留高位的特征，以便于得到的hash值更加均匀分布） return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 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) //初始化容量 n = (tab = resize()).length; //桶未占用 if ((p = tab[i = (n - 1) & hash]) == null) //线性表+链表 tab[i] = newNode(hash, key, value, null); else { //桶占用的处理 Node<K, V> e; K k; //如果key相等,且不为null 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 { //链表处理 //先存A,在存B,接着存C，则数组存的是A,A.next=B,B.next=C,C.next=null 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; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //更新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; }

remove

public V remove(Object key) { Node<K, V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K, V>[] tab; Node<K, V> p; int n, index; //非空判断 if ((tab = table) != null && (n = tab.length) > 0 && //匹配 (p = tab[index = (n - 1) & hash]) != null) { Node<K, V> node = null, e; K k; V v; //第一个node的处理 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { //红黑树的处理 if (p instanceof TreeNode) node = ((TreeNode<K, V>) p).getTreeNode(hash, key); else { //遍历查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //红黑树处理 if (node instanceof TreeNode) ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable); //第一个节点的处理 else if (node == p) tab[index] = node.next; //其他节点的处理 else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }

replace

@Override public V replace(K key, V value) { Node<K, V> e; if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; } final Node<K, V> getNode(int hash, Object key) { Node<K, V>[] tab; Node<K, V> first, e; int n; K k; //非空判断 if ((tab = table) != null && (n = tab.length) > 0 && //根据hash映射数组 (first = tab[(n - 1) & hash]) != null) { //如果是first,则直接返回 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //红黑树查找 if (first instanceof TreeNode) return ((TreeNode<K, V>) first).getTreeNode(hash, key); //遍历查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

get

public V get(Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

扩容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) //如果扩容后的大小<MAXIMUM_CAPACITY且不是第一次初始化容量,则扩充一倍Thr newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults //默认16容量 newCap = DEFAULT_INITIAL_CAPACITY; //默认12,超过12限制容量,则重新扩容 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为空 table = newTab; //以下执行扩容操作 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K, V> e; if ((e = oldTab[j]) != null) { //提前释放GC 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; //注意,此种情况为0,说明hash<当前容量,哪怕扩容后,进行&操作也是一样的索引值 //扩容后,按照之前的数组索引原位保存就行了 //尾部插入 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //这种情况,说明扩容后的hasn进行&操作时,索引落在扩容的那一半部分 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存? //因为这里的扩容都是扩容一倍,也就是01000扩容后变成10000 // 当e.hash & oldCap == 0,说明hash<当前容量,也就是落在0~1000范围内,哪怕扩容后,进行&操作也是一样的索引值 //!=0,则说明第一e.hash落在0~1000范围内,第二包含1000这个位置.而1000是之前扩容前的容量,所以最新的地址为扩容前容量+当前索引 //原位置保存 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //存储索引在扩容的那部分 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

迭代器

final Node<K, V> nextNode() { Node<K, V>[] t; Node<K, V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //遍历当前entry的下一个节点,如果没有则遍历数组,查找下一个链表节点 if ((next = (current = e).next) == null && (t = table) != null) { do { } while (index < t.length && (next = t[index++]) == null); } return e; }

总结

JDK8中,改变了底层数据结构,为线性表+链表+红黑树 产生hash值碰撞后,用链表存储碰撞的值

什么时候采用红黑树?

当桶里面存的链表个数>8,同时数组长度>64,的时候采用红黑树 默认加载因子0.75 默认容量16,加载扩容的大小12 key一样时,覆盖旧的value 可以存null,索引0

为什么每次扩容后,是2的幂次方?

是因为在使用2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。 只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。 这是为了实现均匀分布。

为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存?

//因为这里的扩容都是扩容一倍,也就是01000扩容后变成10000 // 当e.hash & oldCap == 0,说明hash<当前容量,也就是落在0~1000范围内,哪怕扩容后,进行&操作也是一样的索引值 //!=0,则说明第一e.hash落在0~1000范围内,第二包含1000这个位置.而1000是之前扩容前的容量,所以最新的地址为扩容前容量+当前索引 //原位置保存 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //存储索引在扩容的那部分 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

为啥用尾插法?

jdk7因为头插法存在环形问题 而jdk8,使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

为什么线程不安全?

在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。

在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。