当前位置：首页 > news >正文

HashMap的数据结构是怎样的？为什么JDK8中要将其转换为红黑树？

news 来源：原创 2024/9/22 1:32:50

HashMap是Java中常用的一种数据结构，它是基于哈希表实现的，用于存储键值对。在JDK8之前，HashMap的数据结构是数组链表的组合。而在JDK8中，当链表的长度超过一定阈值时，会将链表转换为红黑树，这是因为红黑树的查找、插入、删除等操作具有更高的效率。

在本篇博文中，我们将详细介绍HashMap的数据结构、哈希函数的计算方式、数组链表的缺点以及红黑树的优势，同时提供代码块进行分析。

一、HashMap的数据结构

HashMap的底层数据结构是数组，每个数组元素称为桶(bucket)。当插入一个键值对时，首先根据键的哈希值计算出数组的索引，然后将键值对存储在对应的桶中。

public class HashMap<K, V> {// 桶数组transient Node<K,V>[] table;// 静态内部类，用于保存键值对static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;// ...}// ...
}

在JDK8之前，每个桶中存储的是一个链表，通过next指针将键值对连接起来。当多个键的哈希值相同时，它们会被放置在同一个桶中，形成链表。这样，通过遍历链表就可以找到指定键对应的值。

二、哈希函数的计算方式

哈希函数的作用是将任意长度的输入（键）映射为固定长度的输出（数组索引）。在HashMap中，默认的哈希函数是根据键对象的hashCode()方法返回的哈希码进行计算的。

public final int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char[] val = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;
}

在计算哈希值之后，HashMap会对哈希值进行扰动处理，以减少哈希冲突。具体做法是通过对哈希值进行位运算，使得低位的信息也能参与到哈希值的计算过程中。

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

三、数组链表的缺点

在JDK8之前的HashMap实现中，每个桶中存储的是一个链表。这种数据结构在插入、查找、删除等操作上具有一定的局限性。

1. 查找效率低

链表需要按顺序遍历元素来查找指定键对应的值，即使是最优情况下，也需要遍历链表的所有元素，时间复杂度为O(n)。

2. 插入效率低

当插入一个键值对时，需要遍历链表来判断键是否已经存在，如果存在则更新对应的值，如果不存在则在链表末尾插入新节点。同样，插入操作的时间复杂度也为O(n)。

3. 删除效率低

删除操作需要先遍历链表找到指定键对应的节点，然后将该节点从链表中删除。同样，删除操作的时间复杂度也为O(n)。

综上所述，当链表的长度过长时，HashMap的性能会变得极其低下。在JDK8中，为了提高HashMap在极端情况下的性能，引入了红黑树的概念。

四、红黑树的优势

红黑树是一种自平衡的二叉查找树，具有以下特点：

树的节点可以是红色或黑色。
根节点和叶子节点（null节点）都是黑色。
如果一个节点是红色，则它的子节点必须是黑色。
从根节点到叶子节点的任意路径上，黑色节点的数量是相等的。

红黑树比链表具有更高的查找、插入、删除效率，时间复杂度为O(log n)。

在JDK8中，当链表的长度超过8时，HashMap会将链表转换为红黑树。这样，在大部分情况下，HashMap的性能将得到大幅提升。

五、HashMap在JDK8中的实现逻辑

在JDK8中，当链表的长度超过8时，会触发链表转换为红黑树的操作。

转换过程分为两个步骤：

1. 首先，将链表转换为红黑树

首先，HashMap会将链表中的节点复制到新的红黑树中，并且按照哈希值进行排序。这一步骤的时间复杂度为O(n log n)。

/*** Replaces all linked nodes in bin at index for given hash with* a tree containing all those nodes.*/
final void treeifyBin(Node<K,V>[] tab, int hash) {// ...TreeMap<K,V> newTree = null;for (Node<K,V> e = first; e != null; e = next) {K key = e.key;V value = e.value;if (newTree == null) {newTree = new TreeMap<>(hash, key, value, null);} else {newTree.put(key, value);}}if (newTree != null) {tab[index] = newTree;}
}

2. 然后，将红黑树转换为链表

当红黑树的节点数量小于6时，会触发将红黑树转换为链表的操作。这一步骤的时间复杂度为O(n)。

/*** Returns a list of non-TreeNodes replacing those linked from* this node.*/
final Node<K,V> untreeify(Node<K,V> map) {// ...Node<K,V> hd = null, tl = null;for (Node<K,V> q = map; q != null; q = q.next) {Node<K,V> p = new Node<>(q.hash, q.key, q.value, null);if (tl == null) {hd = tl = p;} else {tl.next = p;p.prev = tl;tl = p;}}return hd;
}