【数据结构】Map、Set与哈希表底层原理

文章目录

• 一、二叉搜索树
• • 1.1 二叉搜索树的定义
  • 1.2 核心操作
  • • （1）查找
    • （2）插入
    • （3）删除
  • 1.3 性能瓶颈与改进方向
• 二、Map接口：Key-Value键值对容器
• • 2.1 Map的特性
  • 2.2 内部类：Map.Entry<K,V>
  • 2.3 Map的常用方法
  • 2.4 TreeMap与HashMap的区别
• 三、Set接口：无重复元素的集合
• • 3.1 Set的特性
  • 3.2 Set的常用方法
  • 3.3 TreeSet与HashSet的区别
• 四、哈希表：HashMap与HashSet的底层
• • 4.1 哈希表的核心思想
  • 4.2 哈希冲突（Hash Collision）
  • • （1）冲突的定义
    • （2）冲突的避免
    • • ① 哈希函数设计原则
      • • 常用哈希函数
      • ② 负载因子调节（重点）
    • （3）冲突的解决
    • • ① 闭散列（开放定址法）
      • ② 开散列（链地址法，重点）
  • 4.3 哈希表的实现（简化版HashMap）
  • 4.4 哈希表与Java类集的关联

一、二叉搜索树

1.1 二叉搜索树的定义

二叉搜索树是一种具有排序特性的二叉树，满足以下规则：

• 若左子树不为空，左子树上所有节点的值均小于根节点的值；
• 若右子树不为空，右子树上所有节点的值均大于根节点的值；
• 左右子树也分别为二叉搜索树。

对于数组{5,3,4,1,7,8,2,6,0,9}，构建的二叉搜索树如下：

5
/ \\
3 7
/ \\ / \\
1 4 6 8
/ \\ \\
0 2 9

1.2 核心操作

（1）查找

查找逻辑遵循左小右大原则：

public TreeNode search(int key){
TreeNode cur = root;
while(cur!=null){
if(cur.val< key)
cur=cur.right;
else if(cur.val> key)
cur=cur.left;
else
return cur;
}
return null;
}

时间复杂度：取决于树的高度，最优为完全二叉树的O(log₂N)，最差为单支树的O(N)。

（2）插入

public void insert(int key) {
if (root == null) {
root = new TreeNode(key);
return;
}
TreeNode cur = root;
TreeNode parent = root;
while (cur != null) {
if (cur.val > key) {
parent = cur;
cur = cur.left;
} else if (cur.val < key) {
parent = cur;
cur = cur.right;
}else {
return;
}
}
if (parent.val > key)
parent.left = new TreeNode(key);
else
parent.right = new TreeNode(key);
}

（3）删除

删除需分三种情况处理，保证删除后树的结构仍满足二叉搜索树规则：

• 情况1：待删除节点（cur）无左子树 若cur是根节点，根节点更新为cur的右子树；否则，将父节点（parent）的对应指针（左/右）指向cur的右子树。

• 情况2：待删除节点（cur）无右子树 逻辑与情况1对称，将父节点的对应指针指向cur的左子树。

• 情况3：待删除节点（cur）左右子树均存在 采用“替换法”：在cur的右子树中找到中序遍历的第一个节点（即右子树中最小节点，称为后继节点），用该节点的值覆盖cur的值，再删除后继节点（后继节点必满足情况1或情况2）。

public void remove(int key) {
TreeNode cur = root;
TreeNode parent = null;

while (cur != null) {
if (cur.val < key) {
parent = cur;
cur = cur.right;
}else if(cur.val > key){
parent = cur;
cur = cur.left;
}
else {
removeNode(parent, cur);
break;
}
}

}

private void removeNode(TreeNode parent, TreeNode cur) {
//情况1
if(cur.left==null){
if(cur==root)
root=cur.right;
else if(cur==parent.left)
parent.left=cur.right;
else if(cur==parent.right)
parent.right = cur.right;
}

//情况2
else if(cur.right==null){
if(cur==root)
root=cur.left;
else if(cur==parent.left)
parent.left=cur.left;
else if(cur==parent.right)
parent.right = cur.left;
}

//情况3
else{
TreeNode tmpParent = cur;
TreeNode tmp = cur.right;
//找到右树的最小节点
while(tmp.left!=null){
tmpParent = tmp;
tmp=tmp.left;
}
cur.val = tmp.val;

//删除右树最小节点
if(tmpParent.left==tmp)
tmpParent.left = tmp.right;
else if(tmpParent.right == tmp)
tmpParent.right = tmp.right;
}
}

1.3 性能瓶颈与改进方向

二叉搜索树的性能依赖于树的结构：若插入顺序有序（如1,2,3,4），会退化为单支树，此时查找/插入/删除的时间复杂度变为O(N)，完全失去优势。

改进方案：使用平衡二叉搜索树（如红黑树），通过颜色规则和旋转操作维持树的平衡，确保最坏情况下的时间复杂度仍为O(log₂N)。这也是TreeMap和TreeSet的底层实现。

二、Map接口：Key-Value键值对容器

Map是Java中存储键值对（Key-Value）的核心接口，其设计目标是支持高效的键查找、插入和删除。

2.1 Map的特性

• 不继承自Collection接口，独立成为顶层接口；
• Key唯一（不可重复），Value可重复；
• 支持Key的快速查找，底层实现决定查找效率；
• 常用实现类：TreeMap（红黑树实现）、HashMap（哈希表实现）。
• Map没有实现Iterable，实现的类不可以通过迭代器进行遍历。如果需要遍历，可以先调用entrySet()返回到Set中，再遍历：

Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
for(Map.Entry<String,Integer> entry : entrySet){
System.out.println("key: "+entry.getKey()+" value: "+ entry.getValue());
}

2.2 内部类：Map.Entry<K,V>

Map通过内部类Map.Entry存储单个键值对，提供了键值对的访问方法：

注意：Map.Entry不提供修改Key的方法，若需修改Key，需先删除原键值对，再重新插入。

2.3 Map的常用方法

2.4 TreeMap与HashMap的区别

三、Set接口：无重复元素的集合

Set接口继承自Collection，核心特性是“存储无重复的Key”，底层实现依赖于Map（将Key作为Map的Key，Value使用一个默认空对象填充）。

3.1 Set的特性

• 仅存储Key，不存储Value；
• Key唯一（重复元素插入失败）；
• Set实现了Iterable，实现的类可以通过迭代器进行遍历。
• TreeSet不可以插入null的key，而HashSet可以。
• 常用实现类：TreeSet（红黑树实现）、HashSet（哈希表实现）、LinkedHashSet（哈希表+双向链表，保留插入顺序）。

3.2 Set的常用方法

3.3 TreeSet与HashSet的区别

四、哈希表：HashMap与HashSet的底层

哈希表（Hash Table）是一种“键值对映射”的数据结构，通过哈希函数将Key映射到存储地址，实现O(1)级别的高效读写，是HashMap和HashSet的底层实现。

4.1 哈希表的核心思想

理想的搜索场景是“无需比较，直接定位”。哈希表通过以下逻辑实现：

示例：对于数据集合{1,4,5,6,7,9}，哈希函数为hash(key) = key % 10（数组长度为10），存储结果如下：

4.2 哈希冲突（Hash Collision）

（1）冲突的定义

当两个不同的Key通过哈希函数计算出相同的存储地址时，称为哈希冲突。

例如“”Key=4和Key=44，4%10=4，44%10=4，会映射到同一地址）。

冲突是必然存在的——因为哈希表的数组长度有限，而Key的范围可能无限，无法避免不同Key映射到同一地址。我们能做的是“尽量降低冲突率”。

（2）冲突的避免

冲突避免的核心是“优化哈希函数”和“调节负载因子”。

① 哈希函数设计原则

• 定义域覆盖所有Key，值域在[0, 数组长度-1]之间；
• 计算结果均匀分布（减少冲突）；
• 计算效率高（简单易实现）。

常用哈希函数

② 负载因子调节（重点）

负载因子（Load Factor）定义：负载因子 = 已存储元素个数 / 数组长度。

• 负载因子越大，数组越满，冲突率越高；
• 负载因子越小，数组越空，空间利用率越低。

结论：负载因子需控制在合理范围（java中HashMap默认0.75）。当负载因子超过阈值时，会触发数组扩容（通常扩容为原来的2倍），从而降低负载因子，减少冲突。

（3）冲突的解决

当冲突发生时，需通过特定方式处理，常用方案有“闭散列”和“开散列”。

① 闭散列（开放定址法）

逻辑：当地址冲突时，在数组中寻找下一个空位置存储元素。

• 线性探测：从冲突地址开始，依次向后查找空位置（如Key=44冲突后，查找索引5、6、7、8，找到空位置8存储）；
• 缺陷：容易导致“数据堆积”（冲突元素集中在某一区域），降低查找效率；
• 二次探测：改进线性探测，查找逻辑为H i = (H0 ± i²) % 数组长度（i=1,2,3…），分散冲突元素，但空间利用率较低（负载因子需≤0.5）。

② 开散列（链地址法，重点）

逻辑：数组的每个位置（称为“桶”）存储一个链表（数组长度超过64且链表长度超过8，转为红黑树），冲突的元素被加入同一个桶的链表中。

示例：Key=4和Key=44冲突后，都存入索引4的桶中，形成链表：

开散列的优势：

• 空间利用率高（无需预留空位置）；
• 冲突处理简单（仅在桶内链表操作）；
• 性能稳定（HashMap采用此方案，当链表长度超过8时，转为红黑树，进一步优化查找效率）。

4.3 哈希表的实现（简化版HashMap）

以下是基于开散列（链地址法）的简化版哈希表实现，包含put（插入）、get（查找）和resize（扩容）操作：

public class HashBuck {
//键值对
static class Node{
public int key;
public int val;
public Node next;

public Node(int key,int val){
this.key = key;
this.val = val;
}
}
//哈希数组
public Node[] arr = new Node[10];
//已存节点个数
public int usedSize;
//负载因子阈值
public static final double DEFAULT_LOAD_FACTOR = 0.75f;

//插入
public void put(int key, int val){
int index = key% arr.length;
Node cur = arr[index];
while(cur!=null){
//key存在则替换val
if(cur.key==key){
cur.val=val;
return;
}
cur=cur.next;
}
//key不存在,新建节点
Node newNode = new Node(key,val);
//头插法
newNode.next = arr[index];
arr[index]=newNode;
usedSize++;

//检查负载因子
if(doLoadFactor() >= DEFAULT_LOAD_FACTOR){
resize();
}

}

//扩容
private void resize() {
Node[] newArr = new Node[arr.length*2];
for (int i = 0; i < arr.length; i++) {
Node cur = arr[i];
while(cur!=null){
int index = cur.key % newArr.length;
//记录cur的下一个节点，防止后面修改cur.next后找不到原来的节点
Node curNext = cur.next;

//头插法
cur.next = newArr[index];
newArr[index]=cur;
cur = curNext;
}
}
arr = newArr;
}

//计算负载因子
private double doLoadFactor(){
return usedSize*1.0/ arr.length;
}

//根据key获取val
public int getValue(int key){
int index = key % arr.length;
Node cur = arr[index];
while(cur!=null){
if(cur.key==key)
return cur.val;
cur=cur.next;
}
return –1;
}
}

注意： 扩容不可以直接把原来的数组复制到新数组中，因为哈希地址会随着数组长度改变，必须遍历每一个元素，重新分配地址。

对于引用类型的数据：

例如：

import java.util.Objects;

public class Student {
int id;
String name;

@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id == student.id && Objects.equals(name, student.name);
}

@Override
public int hashCode() {
//当id和name相等时，hashcode也相等
return Objects.hash(id, name);
}
}

4.4 哈希表与Java类集的关联