为什么要分高低位链表?，试想若是全部都使用index =（hash & (newTab.length - 1)）计算，此时因为是基于下标存储，从而导致在index冲突的情况下，多元素链表的追加出现额外的时间（寻址等）或空间（辅助参数、结构等）上的开销。分高低位链表，相比先保存好数据再寻找追加效率更好，也是极好的优化技巧。
5.4 get实现 public 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 ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 直接命中 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; } 5.5 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; } 5.6 containsKey实现 public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } 5.7 containsValue实现 public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { // table遍历 for (int i = 0; i < tab.length; ++i) { // 多元素链表遍历 for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; } 六、总结 6.1 为什么需要负载因子？