hashmap怎么解决哈希冲突问题？红黑树和AVL树有何区别？

柔情只为你懂 2023-10-10 21:21 6阅读 0赞

## 链地址法 ##

hashmap是一种基于数组和链表（或红黑树）的数据结构，它可以通过hash函数将任意长度的键映射到一个固定长度的索引，从而实现快速的存取操作。但是，由于hash函数的结果是有限的，而键的数量是无限的，所以可能存在不同的键映射到同一个索引的情况，这就叫做**哈希冲突**。为了解决哈希冲突，hashmap采用了**链地址法**，也就是把发生冲突的键值对以单向链表的形式存储在数组的同一个位置上，这样就形成了一个“拉链式”的结构。  
在JDK1.8中，为了提高查找效率，当链表的长度达到一定阈值（默认为8）时，会把链表转换为红黑树，这是一种自平衡的二叉查找树，它可以保证查找时间复杂度为O(logn)。所以，hashmap解决哈希冲突的方法有两种：**链表**和**红黑树**。

## 红黑树的特点 ##

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

*  节点分为红色或者黑色。
 *  根节点必为黑色。
 *  叶子节点都为黑色，且为 null。
 *  连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）。
 *  从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
 *  新加入到红黑树的节点为红色。这些特点保证了红黑树的查找、插入、删除操作的时间复杂度都是 O(logn)。另外，红黑树还有一个特点是，从根节点到叶子节点的最长路径不大于最短路径的 2 倍。这是因为红黑树不会出现相连的红色节点，而且从任意节点到叶子节点的黑色节点数量是一样的，所以最长路径就是由红色和黑色节点交替组成的，而最短路径就是由纯黑色节点组成的。

## 红黑树和AVL树的区别 ##

红黑树和AVL树都是自平衡的二叉查找树，它们有以下几个区别：

*  AVL树是严格的平衡二叉树，它要求每个节点的左右子树高度差的绝对值不超过1，因此它的高度大约是log(n)。红黑树是弱平衡二叉树，它要求每个节点到其所有叶子节点的最长路径不超过最短路径的两倍，因此它的高度大约是2log(n)。
 *  AVL树在插入和删除时需要进行更多的旋转操作来维持平衡，而红黑树只需要少量的旋转和变色操作。因此，红黑树在插入和删除时更快，而AVL树在查找时更快。
 *  AVL树需要额外的两位来存储每个节点的平衡因子，而红黑树只需要额外的一位来存储每个节点的颜色。因此，红黑树在空间上更节省。
 *  AVL树和红黑树都有广泛的应用场景。AVL树适合用于查找频繁而插入删除少的情况，比如Windows内核中对进程地址空间的管理。红黑树适合用于插入删除频繁而查找较少的情况，比如C++ STL中的map和set，Java中的TreeMap，Linux中的进程调度器和epoll机制等。