HashMap源码阅读笔记

基于jdk1.8 的HashMap 源码阅读

HashMap的存储结构是数组+链表的形式，在jdk1.8中这样说也不完全准确，应该是数组+链表（红黑树）

附上一张丑丑的图 put的源码是

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

在HashMap中用于计算hash的方法是

static final int hash(Object key) { int h;//key 的hash值异或 h无符号右移16位（保留高位） 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; //table 就是我们对象的属性存储node 的数组 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; 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); if (binCount >= TREEIFY_THRESHOLD - 1) //TREEIFY_THRESHOLD 这个是个常量8 treeifyBin(tab, hash);//树化，加到第八个的时候binCount=7 break; } 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; } } ++modCount; if (++size > threshold)//判断是否需要扩容，threshold 一般是容量*负载因子（DEFAULT_LOAD_FACTOR） resize(); afterNodeInsertion(evict); return null; }

扩容的方法

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) { //MAXIMUM_CAPACITY=1 << 30 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //DEFAULT_INITIAL_CAPACITY=1 << 4 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults 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);//分割，红黑树，如果节点数量小于等于6会解除树化 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) { 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; }

有几个可以稍微注意一下 下标的计算方式是(n - 1) & hash ----n 是数组的长度，hash 值是用hash方法计算出来的 当插入后长度大于容量负载因子的时候进行扩容，扩容后变大2倍,当容量大于等于1<<30,不在扩容，计算出来的 容量负载因子 赋值为int的最大值

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; 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; }

注意重点来了，移除树节点代码

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; if (pred == null) tab[index] = first = succ; else pred.next = succ; if (succ != null) succ.prev = pred; if (first == null) return; if (root.parent != null) root = root.root(); if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { tab[index] = first.untreeify(map); // 这段代码是解除树化，条件是树的节点数小于4就开始解除树化 return; } TreeNode<K,V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { TreeNode<K,V> s = pr, sl; while ((sl = s.left) != null) // find successor s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode<K,V> sr = s.right; TreeNode<K,V> pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<K,V> sp = s.parent; if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) != null) pr.parent = s; } p.left = null; if ((p.right = sr) != null) sr.parent = p; if ((s.left = pl) != null) pl.parent = s; if ((s.parent = pp) == null) root = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr != null) replacement = sr; else replacement = p; } else if (pl != null) replacement = pl; else if (pr != null) replacement = pr; else replacement = p; if (replacement != p) { TreeNode<K,V> pp = replacement.parent = p.parent; if (pp == null) root = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); if (replacement == p) { // detach TreeNode<K,V> pp = p.parent; p.parent = null; if (pp != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } if (movable) moveRootToFront(tab, r); }

总结：解除树化的两个时机扩容（树的大小小于等于6）和remove （树的大小小于4）

重点注意：为什么HashMap 会线程不安全，具体表现在什么情况下 jdk 1.7 ：在这个版本中，就是单纯的使用数组+链表的结构来保存数据

在进行扩容的时候，会重新将就的旧的数组的结节一个个插入到新的数组中，这个时候使用头插法（新来的数据放在链表的前面），多线程进行修改的时候，修改节点的引用容易造成循环节点，然后进入死循环。在put 的时候计算完数组的存储，容易造成数据的丢失，保存下来的数据全看天意

jdk 1.8 ：在这个版本中进行了优化，使用尾插发，并且在扩容的时候基本保留顺序

多线程操作put 还是容易造成数据丢失

额外的问题： 为什么HashMap 最好是2的倍数和为什么默认负载因子是0.75 因为计算存储数据的下标的计算方式是(n - 1) & hash，2的倍数容易使这些节点均匀分布在数组的各个部分上（和泊松分布有关）

处理hash 冲突的几种方式

开放定址法： 当冲突发生时，使用某种探测算法在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到符合要求的地址再哈希法 ：准备几个不同Hash函数，当发生冲突时，使用第二个，第三个，….，等Hash函数 计算地址，直到无冲突。链地址放：把冲突的地方直接变成链表，一个个往下插入就好，Java中的HashMap就是使用这种方式

HashSet 的实现是怎样的

//构造方法 想不到吧 public HashSet() { map = new HashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT)==null;//PRESENT = new Object() 一个常量 }

为什么equals 相等 hashcode 也要相等？ 其实我感觉如果你不适用集合之类的东西应该没啥所谓，如果用了，考虑HashSet，是将对象当做key 存到Map中，而存储Map的过程又是先计算hash值，这个时候如果hashcode 不等，那么你的Set 里面就会出现equals 相等的值。类似如果你存Map的时候，按道理来说key的equals相等应该替换，但是由于你的hashcode 计算的是不一样的，就可能会出现…

最重要的一点后面才发现的，想要开始转化为红黑树，node 数组的长度大小要大于64

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();//MIN_TREEIFY_CAPACITY =64 准备开始树化的时候如果判断容量小于64 去扩容 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { 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); } }