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

骑猪看日落 2022-05-11 11:38 121阅读 0赞

# 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的存取效率就会越高！