Java8 中的 HashMap


红黑树(red black tree)

特点
  • 一个节点是红色或黑色
  • 根节点是黑色
  • 如果一个节点是红色,那么它的子节点必须是黑色
  • 一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点(红色节点不影响)
两种旋转方式和一种颜色变换
  • 单旋转方式
  • 双旋转方式(需要两次反方向的单旋转)
  • 当两个子节点均为红色的时候,执行颜色变换,因为插入的是红色节点,会产生冲突。例如根节点的子节点是红色,两个叶子节点变成黑色,根节点变成红色,再变成黑色。
问题
  1. 为什么插入的总是红色节点?

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

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

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

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

HashMap特性

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

HashMap与HashTable区别

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

HashMap内部类

内部类简介
  1. Node (static class):基于 hash 的链表节点,由 LinkedHashMap.Entry 、 TreeNode 继承实现
    • TreeNode (static final class)
  2. Values (final Class):HashMap中的 value 集合
  3. KeySet (final Class):HashMap中的 key 集合
  4. EntrySet (final Class):HashMap中的 Entry 集合
  5. HashIterator (abstract class):抽象迭代器
    • KeyIterator (final Class): HashMap中的 Key 集合的迭代器
    • ValueIterator (final class):HashMap中的 Value 集合的迭代器
    • EntryIterator (final class):HashMap中的 Entry 集合的迭代器
  6. 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<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;
        }

        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<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; // needed to unlink next upon deletion
        boolean red;

        TreeNode(int hash, K key, V val, Node<K, V> next)
        {
            super(hash, key, val, next);
        }

        final void treeify(Node<K,V>[] tab)
        {
            // ......
        }

        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
        {
            // ......
        }

        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p)
        {
            // ......
        }

        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p)
        {
            // ......
        }

        // ......其余方法省略
    }
HashMap中内部变量
   /**
     * 默认桶的数量 为 16 必须是 2 的幂次方
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 桶的最大数量为 2 的 30 幂次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 桶的负载因子,当存有数据的桶的数量超过 75% ,就会扩容为 2 倍桶数量,并自动进行再散列(rehashed)
     * 可以查看构造函数
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 桶内数据量超过这个阈值就会将桶内数据结构从链表转为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 桶内数据量小于这个阈值就会将桶内数据结构从红黑树退化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 如果桶的数量小于 64 ,会先扩容,直至桶的数量超过 64
     * 这样是为了减少形成很满的桶,因为桶的数量越多,越不容易造成桶满
     * 借鉴了 <see>https://stackoverflow.com/questions/43911369/hashmap-java-8-implementation</see>
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

HashMap插入

put()方法

使用内部 putval()方法

putval()方法
  • putval方法参数说明
    ```java
  • @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)
    ```
  • 代码逻辑执行过程
  1. 表是否为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)
  2. treeifyBin()

    • 2.1 如果表为null或者表长度小于 64 ,则进行表长度扩容
    • 2.2 如果表长度大于 64 且表最后一个桶内数据不为null,则将桶内链表的节点结构转换为TreeNode,并连成一个链表
    • 2.3 进化红黑树(treeify)
  3. 转换红黑树代码解析

  • treeify()

    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 {
                    // 存在根节点后,根据外层的for循环,知晓当前节点 x 的信息
                    // 开始从上往下进行红黑树节点添加,以下的 for 循环是核心循环,进行节点添加
                      K k = x.key;
                      int h = x.hash;
                      Class<?> kc = null;
                      // for 循环是为了寻找一个空的节点位置,将元素放入
                      for (TreeNode<K,V> 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<K,V> 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 <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                      TreeNode<K,V> x) {
            // 印证了之前说的新加入节点都是红色的
            x.red = true;
            // xp x 的父节点
            // xpp x 的祖父节点
            // xppl x 的祖父的左节点
            // xppr x 的祖父的右节点
              for (TreeNode<K,V> 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 <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                                TreeNode<K,V> p) {
            // root 表示根节点
            // p 表示 x 的父节点 xp
            // pp 表示 父节点的父节点 祖父节点
            // rl 表示 右节点的左节点
            // r 表示 右节点
            // 左旋就是将某个节点旋转为其右节点的左节点
            TreeNode<K,V> 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 <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                                 TreeNode<K,V> p) {
            // l 左节点
            // pp 祖父节点
            // lr 左节点的右节点
            // 右旋就是将某个节点旋转为其左节点(孩子)的右节点(孩子)
            TreeNode<K,V> 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;
      // 向右旋 (图示的单旋转方式)
    }
    
  • 图示右旋过程

    // 执行完图示代码,形成图示结构
    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; ```
  • 左旋和右旋结合起来的旋转过程

问题:

  1. 为什么右旋前,需要将 x 节点变成黑色?

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

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


文章作者: Huowy
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Huowy !
评论
  目录