欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JAVA笔记 —— JDK1.8中 HashMap 的变化

程序员文章站 2022-06-07 13:22:05
...

HashMap(1.8)

1、数据结构的变化:红黑树

  JDK1.8之前,HashMap的数据结构:数组 + 链表(单链表)

  JDK1.8之后,HashMap的数据结构:数组 + 链表 + 红黑树

什么是红黑树?

  红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。红黑树的特点:

  1、 任何一个节点都是有颜色的,黑色或者红色;

  2、根节点是黑色;

  3、每个叶子节点(NIL节点,空节点)是黑色的;

  4、从每个叶子到根的所有路径上不存在两个连续的红色节点;(每个红色节点的两个子节点都是黑色)

  5、从任一节点到每个叶子的所有路径都包含相同数目的黑色节点;

  6、左子树的节点一定比父节点的值小,右子树的节点一定比父节点的值大;

  JDK1.8之前,HashMap采用数组+链表实现,即使用单链表处理冲突,同一hash值的元素都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。因此,在JDK1.8之中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

 

2、table数组的类型:由Entry改成了Node

  Entry是HashMap中在JDK1.8之前的一个静态内部类,在1.8改成了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;
        }

     ......
    }

 

3、hash()函数算法修改:简化

  在JDK1.8之前,

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

  在JDK1.8之后,简化:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

  若key为null,则返回 0 ,若key不为null,则计算key的hashCode值,右移16位之后,做异或运算高位参与运算。Hash算法计算得到的值越分散,则发生碰撞的概率就越小,map的存取效率就会越高!