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