三、 HashMap 从链表到红黑树的转变
如果链表的长度（冲突的节点数）已经达到8个，此时会调用 treeifyBin() ，treeifyBin() 首先判断当前hashMap 的 table的长度，如果不足64，只进行resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树。在源码还有这样的一个字段。
static final int UNTREEIFY_THRESHOLD = 6; // 这样表明了从红黑树转化为链表的阈值为 6，为何同样不是 8 那？ //如果插入和删除都在 8 附近，将多二者相互转化将浪费大量的时间，对其性能影响。 //如果是的二者转化的操作不平衡，偏向一方，则可以避免此类影响。
3.1 红黑树的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // 删除后需要取消链接，指向前一个节点（原链表中的前一个节点） boolean red; }
因为 继承了 LinkedHashMap.Entry<K,V> ，所以存储的数据还是在Entry 中：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }
3.2 承上启下的 treeifyBin()
treeifyBin() 决定了一个链表何时转化为一个红黑树。treeifyBin() 有两种格式：
final void treeifyBin(Node<K,V>[] tab, int hash); final void treeify(Node<K,V>[] tab);
final void treeifyBin(Node<K,V>[] tab, int hash) { // 简单的 Node 修改为 TreeNode，同时维护了 prev 属性。 int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); 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); // 真正生成红黑树的 } }
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); } // 实现 Node 链表节点到 TreeNode 节点的转化。
下面函数真正实现了链表的红黑树的转变。首先构建一个标准查询二叉树，然后在标准查询二叉树然后调整为一个红黑树。而 balanceInsertion() 实现了调整。
/** * Forms tree of the nodes linked from this node. */ final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { // 第一次转化过程，将链表的头节点作为根节点。 x.parent = null; x.red = false; // 红黑树的定义 根节点必须为黑色 root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) 通过 Hash 的大小来确定插入顺序 dir = -1; // dir 大小顺序的标识 else if (ph < h) dir = 1; else if ((kc == null && //当 两个 Hash 的值相同，进行特殊的方法，确定大小。 (kc = comparableClassFor(k)) == null) || // Returns x's Class if it is of the form "class C implements Comparable ", else null. 如果 key类的 源码书写格式为 C implement Comparable<C> 那么返回该类类型 C, 如果间接实现也不行。 如果是 String 类型，直接返回 String.class (dir = compareComparables(kc, k, pk)) == 0) // ((Comparable)k).compareTo(pk)); 强制转换后进行对比，若 dir == 0,则 tieBreakOrder()，继续仲裁 dir = tieBreakOrder(k, pk); // 首先通过二者的类类型进行比较，如果相等的话，使用 (System.identityHashCode(a) <= System.identityHashCode(b) 使用原始的 hashcode，不是重写的在对比。 TreeNode<K,V> xp = p; // 遍历的，上一个节点 if ((p = (dir <= 0) ? p.left : p.right) == null) { //通过 dir，将 p 向下查找，直到 p 为 null，找到一个插入时机 x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); //进行二叉树的调整 break; } } } } moveRootToFront(tab, root); }
3.3 将一个二叉树转化为红黑树的操作-balanceInsertion()
当红黑树中新增节点的时候需要调用balanceInsertion方法来保证红黑树的特性。
如果想要了解红黑树的插入过程那么必须对红黑树的性质有一个较为清晰的了解。
红黑树的性质：
每个结点或是红色的，或是黑色的
根节点是黑色的
每个叶结点（NIL）是黑色的
如果一个节点是红色的，则它的两个儿子都是黑色的。
对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; // 插入的子节点必须为 red for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { x 当前处理节点 xp父节点 xpp祖父节点 xppl祖父左节点 xppr 祖父右节点 if ((xp = x.parent) == null) { // 如果 当前处理节点为根节点，满足红黑树的性质，结束循环 x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) return root; if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }
TreeNode 红黑树总结
TreeNode 完整的实现了一套红黑树的增删改查的规则。实现参考了《算法导论》
/* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR
这里推荐一个红黑树动画演示网站 https://rbtree.phpisfuture.com/ 红黑树是一个不严格的平衡二叉查找树，高度近似 log(N)。
四、HashMap 的扩展
Map中 key 有一个性质，就是 key 不能重复，而 Java Set 的含义：集合中不能有重复的元素。HashMap 的实现已经足够的优秀。那么我们是否可以用 key 的性质来实现 Set ？的确 JDK 中的 HashSet 就是这样做的。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); }
PRESENT 就是存进 Map 中的 value，而 key 正是 Set 语义的实现。而且可以判断出 HashSet 中是允许存入 Null 值的。
