Java 8 中的 HashMap

红黑树(red black tree) 特点

一个节点是红色或黑色
根节点是黑色
如果一个节点是红色，那么它的子节点必须是黑色
一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点(红色节点不影响)

两种旋转方式和一种颜色变换

单旋转方式
双旋转方式(需要两次反方向的单旋转)
当两个子节点均为红色的时候，执行颜色变换，因为插入的是红色节点，会产生冲突。例如根节点的子节点是红色，两个叶子节点变成黑色，根节点变成红色，再变成黑色。

问题

为什么插入的总是红色节点?

因为插入前，树都是构建好的，如果插入的是黑色节点，就破坏了每一条路径必须包含相同数目的黑色节点这一特性
为什么进行旋转？

因为插入时总是红色节点，如果不旋转的话，违背了一个节点是红色，那么它的子节点必须是黑色这一特性
为什么进行颜色变换？

图示的第一种旋转，红色节点 X 的插入破坏了红黑树结构，所以进行旋转，旋转后的结构如图所示，旋转后，P 和 G 点如果维持本来的颜色，就会违背第三、四条特性，所以，进行颜色变换。
与 AVL(Adelson-Velsky and Landis Tree) 树（平衡二叉查找树）比较?

红黑树不是通过递归方式，而是通过循环的方式来实现，不需要保存节点高度字段，节省内存
两者最坏操作时间复杂度都是O(logN)

HashMap特性

允许 key 、 value 任一值或同时为 null
HashMap 的元素时无序，不稳定
HashMap 写操作线程不安全，读操作线程安全
支持已任何形式创建的迭代器
不支持除迭代本身方法(remove())改变集合元素，否则会抛出 ConcurrentModificationException 异常

HashMap与HashTable区别

HashTable 读写操作是线程安全
HashTable 不允许 key 、 value 任一值或同时为 null

HashMap内部类内部类简介

Node (static class):基于 hash 的链表节点，由 LinkedHashMap.Entry 、 TreeNode 继承实现
- TreeNode (static final class)
Values (final Class)：HashMap中的 value 集合
KeySet (final Class)：HashMap中的 key 集合
EntrySet (final Class)：HashMap中的 Entry 集合
HashIterator (abstract class)：抽象迭代器
- KeyIterator (final Class): HashMap中的 Key 集合的迭代器
- ValueIterator (final class)：HashMap中的 Value 集合的迭代器
- EntryIterator (final class)：HashMap中的 Entry 集合的迭代器
HashMapSpliterator (static class):抽象的并行迭代器
- KeySpliterator (static final class):HashMap中的 Key 集合的并行迭代器
- ValueSpliterator (static final class):HashMap中的 Value 集合的并行迭代器
- EntrySpliterator (static final class)：HashMap中的 Entry 集合的并行迭代器

Node 内部类

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;

            return o instanceof Map.Entry e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }

TreeNode 内部类

static final class TreeNode extends LinkedHashMap.Entry
    {
        TreeNode parent; // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev; // needed to unlink next upon deletion
        boolean red;

        TreeNode(int hash, K key, V val, Node next)
        {
            super(hash, key, val, next);
        }
        
        final void treeify(Node[] tab)
        {
            // ......
        }
        
        static  TreeNode balanceInsertion(TreeNode root, TreeNode x)
        {
            // ......
        }
        
        static  TreeNode rotateLeft(TreeNode root, TreeNode p)
        {
            // ......
        }
        
        static  TreeNode rotateRight(TreeNode root, TreeNode p)
        {
            // ......
        }
        
        // ......其余方法省略
    }

HashMap中内部变量

   
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    
    static final int MAXIMUM_CAPACITY = 1 << 30;

    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    
    static final int TREEIFY_THRESHOLD = 8;

    
    static final int UNTREEIFY_THRESHOLD = 6;

    
    static final int MIN_TREEIFY_CAPACITY = 64;

HashMap插入 put()方法

使用内部 putval()方法

putval()方法

putval方法参数说明

* @param hash hash for key (key 的 Hash 值)
* @param key the key  
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value (如果键存在，是否需要更新 value值，true 更新 false 不更新)
* @param evict if false, the table is in creation mode.(如果为false，表示该表处于创建模式，jdk1.8版本里面使用该参数的方法是空实现，故暂没有作用)
* @return previous value, or null if none(返回之前的值，如果没有直接返回 null)

代码逻辑执行过程

表是否为null或表长度是否为零，决定了是否先进行初始化。
- 1.1 初始化表，调用方法resize()
- 1.2 Hash计算后，如果对应桶内为null，往桶内添加数据，此时桶内使用数据结构为链表
- 1.3 Hash计算后，如果对应桶内不为null，判断key的 Hash 值以及 key 值是否相等，
  - 1.3.1 相等，直接覆盖
  - 1.3.2 不相等，判断节点结构是否为红黑树结构(TreeNode)实例，是则直接使用 putTreeVal() 方法
  - 1.3.3 判断节点结构是否为红黑树节点结构(TreeNode)实例，不是则直接将数据插入链表末端，并判断链表长度是否大于等于 8 ，是则开始进行将链表进化为红黑树的操作(treeifyBin)
treeifyBin()
- 2.1 如果表为null或者表长度小于 64 ，则进行表长度扩容
- 2.2 如果表长度大于 64 且表最后一个桶内数据不为null，则将桶内链表的节点结构转换为TreeNode，并连成一个链表
- 2.3 进化红黑树(treeify)
转换红黑树代码解析

treeify()

final void treeify(Node[] tab) {
            TreeNode root = null;
            for (TreeNode x = this, next; x != null; x = next) {
                next = (TreeNode)x.next;
                x.left = x.right = null;
                if (root == null) {
                  // 配置红黑树根节点
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                  // 存在根节点后，根据外层的for循环，知晓当前节点 x 的信息
                  // 开始从上往下进行红黑树节点添加，以下的 for 循环是核心循环，进行节点添加
                    K k = x.key;
                    int h = x.hash;
                    Class kc = null;
                    // for 循环是为了寻找一个空的节点位置，将元素放入
                    for (TreeNode p = root;;) {
                      // for 循环中没有控制条件，需循环内部跳出
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                          // 节点的 Hash 值 大于 当前元素 Hash 值，放左节点
                            dir = -1;
                        else if (ph < h)
                          // 节点的 Hash 值 小于 当前元素 Hash 值，放右节点
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                          // 先尝试通过Comparable比较两个对象(当前pk的key对象和x的key对象)
                          // 1. 先通过 comparableClassFor 方法判断两者是否可以进行 Comparable
                          // 2. 如果可以，通过 compareComparables 方法进行比较
                          // 判断条件中的方法没有分出胜负则使用此方法分出胜负
                            dir = tieBreakOrder(k, pk);
                        TreeNode xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            // 维护红黑树添加节点后的结构
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
          //Ensures that the given root is the first node of its bin
          // 确保根节点在链表的第一个
            moveRootToFront(tab, root);
        }

需要被插入的元素的key对象是否实现了 Comparable 接口

static Class comparableClassFor(Object x) {
      // 当前元素key 是否实现了 Comparable 接口
        if (x instanceof Comparable) {
            Class c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
              // 如果 x 是字符串对象，直接返回，因为 String 实现了Comparable接口
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
              // 获取 x 实现了哪些接口，包含泛型接口(泛型信息)
                for (Type t : ts) {
                    if ((t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                  // 如果当前接口t是个泛型接口
                  // 如果该泛型接口t的原始类型p 是 Comparable 接口
                  // 如果该Comparable接口p只定义了一个泛型参数
                  // 如果这一个泛型参数的类型就是c，那么返回c
                        return c;
                }
            }
        }
        return null;
    }

通过 Comparable 比较大小，确定节点位置

static int compareComparables(Class kc, Object k, Object x) {
      // 如果 x == null 或者 x 的实现类不是 comparableClassFor 获取的类，直接返回 0
      // 如果 x != null 或者 x 的实现类是 comparableClassFor 获取的类
      // 通过 Comparable 比较大小，返回比较结果
        return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
    }

插入节点后，平衡红黑树结构

static  TreeNode balanceInsertion(TreeNode root,
                                                    TreeNode x) {
          // 印证了之前说的新加入节点都是红色的
          x.red = true;
          // xp x 的父节点
          // xpp x 的祖父节点
          // xppl x 的祖父的左节点
          // xppr x 的祖父的右节点
            for (TreeNode xp, xpp, xppl, xppr;;) {
              if ((xp = x.parent) == null) {
                // 如果 x 的父节点是 null 说明 x 节点为 根节点
                // 红黑树特性 根节点必须黑色
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                  // 进入 else 说明 x 不是根节点，
                  // x 的父节点为黑色，可以在下面直接添加红色节点，直接返回根，
                  // x 的祖父节点为空，表示 x 的父节点是根节点，且调用该方法前，节点已经添加完成，所以直接返回根节点
                  return root;
              // 进入下面的执行逻辑表示
              // 1. x 的父节点xp是红色的，
              // 2. x 的祖父节点xpp不为空
              // 这样就遇到两个红色节点相连的问题，所以必须经过颜色变换和双旋转
                if (xp == (xppl = xpp.left)) {
                  // x 的父节点是 x 祖父节点的左节点
                    if ((xppr = xpp.right) != null && xppr.red) {
                      // x 的祖父节点的右节点不是 null 且右节点是红色，则证明祖父节点的左节点也是红色
                      // 因为红色节点下面不能再挂红色节点，所以需要将祖父节点的左右节点全部变成黑色，祖父节点变成红色(就是前面说的颜色变换)
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                      // 为什么让 x = xpp ？因为 xpp 变成红色节点后可能与 xpp 的父节点发生冲突(两个红色节点相连)，
                      // 就此形成了图示的第二种旋转，所以需要从下往上旋转
                        x = xpp;
                    }
                    else {
                      // x 的祖父节点的右节点是 null 且右节点是黑色
                      // 那么此时的结构位置就有两种情况
                      // 1. xpp->xp(xxp的左节点)->x(xp的右节点)
                        if (x == xp.right) {
                          // 向左旋（图示的单旋转方式）注意进行左旋的节点是 x 的父节点 
                            root = rotateLeft(root, x = xp);
                          // 将xp 的父节点执向 x 的祖父节点
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 2. xpp->xp(xxp的左节点)->x(xp的左节点) 或者上面旋转后，也会形成这种结构
                        if (xp != null) {
                          // x 的父节点变为黑色
                            xp.red = false;
                            if (xpp != null) {
                              // x 的祖父节点变为红色
                                xpp.red = true;
                                // 向右旋 （图示的单旋转方式）
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                  // x 的父节点是祖父节点的右节点
                    if (xppl != null && xppl.red) {
                      // x 的祖父节点的左节点不是 null 且是红色节点
                      // 那么 x 的父节点 肯定也是红色节点，这样就符合图示的第三种旋转
                      // x 的祖父节点的左节点变成黑色节点，x 的父节点也变成黑色节点 ，x 的祖父节点变成红色节点
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        // 为什么 x = xpp ? 因为 x 的祖父节点变成红色节点后，可能产生两个红色节点相连的冲突，即图示的第二种旋转
                      // 所以将x = xpp ，进行从下而上的旋转
                        x = xpp;
                    }
                    else {
                      // x 的祖父节点的左节点是 null 且是黑色节点，那么 x 的父节点肯定是黑色
                      // 此时结构肯定有两种
                      // 1. xpp右->xp左->x
                        if (x == xp.left) {
                          // 向右旋
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 2. xpp右->xp右->x 或上述旋转后形成的该结构
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                // 向左旋
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

rotateLeft

static  TreeNode rotateLeft(TreeNode root,
                                              TreeNode p) {
          // root 表示根节点
          // p 表示 x 的父节点 xp
          // pp 表示 父节点的父节点 祖父节点
          // rl 表示 右节点的左节点
          // r 表示 右节点
          // 左旋就是将某个节点旋转为其右节点的左节点
          TreeNode r, pp, rl;
            if (p != null && (r = p.right) != null) {
              // 如果符合的话，p 的右节点指向 rl 否则指向 null
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                // 如果pp 为空，实际剩下三个节点
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                // 如果pp 不为为空
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }

图示左旋过程

// 执行完该代码，形成图示结构
if (p != null && (r = p.right) != null) {
    if ((rl = p.right = r.left) != null)
       rl.parent = p;

```java // (图示 PP != null) 执行完该代码，形成图示结构 if ((pp = r.parent = p.parent) == null) (root = r).red = false; ``` ```java // (图示 PP != null) 执行完该代码，形成图示结构(图示 pp.left == p 成立) else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; ``` ```java // (图示 PP == null) 执行完该代码，形成图示结构 if ((pp = r.parent = p.parent) == null) (root = r).red = false; ``` ```java // (图示 PP == null) 执行完该代码，形成图示结构 r.left = p; p.parent = r; ```

rotateRight

static  TreeNode rotateRight(TreeNode root,
                                               TreeNode p) {
          // l 左节点
          // pp 祖父节点
          // lr 左节点的右节点
          // 右旋就是将某个节点旋转为其左节点(孩子)的右节点(孩子)
          TreeNode l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

// 执行完图示代码，形成右旋开始前的红黑树结构
// x 的父节点变为黑色
xp.red = false;
if (xpp != null) {
    // x 的祖父节点变为红色
    xpp.red = true;
    // 向右旋 （图示的单旋转方式）
}

- 图示右旋过程 ```java // 执行完图示代码，形成图示结构 if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; ``` ```java // ( 图示 pp != null )执行完图示代码，形成图示结构 if ((pp = l.parent = p.parent) == null) (root = l).red = false; ``` ```java // ( 图示 pp != null )执行完图示代码，形成图示结构 else pp.left = l; l.right = p; p.parent = l; ``` ```java // ( 图示 pp == null )执行完图示代码，形成图示结构 if ((pp = l.parent = p.parent) == null) (root = l).red = false; ``` ```java // ( 图示 pp == null )执行完图示代码，形成图示结构 l.right = p; p.parent = l; ```

左旋和右旋结合起来的旋转过程

问题：

为什么右旋前，需要将 x 节点变成黑色？

因为这样就可以不考虑 xppp 节点的颜色，即使 xppp 节点颜色是红色，可以进行再次平衡旋转

以上都是拿 x 的父节点是祖父节点的左节点的情况，x 的父节点是祖父节点的右节点的情况，与之相反。

Java 8 中的 HashMap

Java相关栏目本月热门文章