3.1 树（上）
3.1 树（下）
3.2 堆（Heap）
3.3 哈希表（Hash Table）
3.3.1 哈希表的基本概念
哈希表（Hash Table）是一种基于键值对（key-value）的数据结构，它通过哈希函数将键映射到数组的索引，从而实现快速的插入、查找和删除操作。哈希表的平均时间复杂度为O(1)，这使它成为最高效的数据结构之一。
哈希表的生活例子
图书馆的索引系统：在图书馆中，每本书都有一个唯一的编号（ISBN），通过这个编号可以快速找到书的位置，而不需要逐一查找。
学生信息系统：学校使用学号作为键，可以快速查找到学生的所有信息，而不需要遍历所有学生记录。
字典：当你查找一个单词时，你不需要从头到尾翻阅整本字典，而是可以根据首字母快速定位到相应的页面。
哈希表的基本组成
- 键（Key）：用于标识和查找数据的唯一标识符。
- 值（Value）：与键关联的数据。
- 哈希函数（Hash Function）：将键转换为数组索引的函数。
- 桶（Bucket）：存储数据的数组单元。
3.3.2 哈希函数
哈希函数是哈希表的核心，它的作用是将键转换为数组索引。一个好的哈希函数应该具有以下特性：
- 计算简单：哈希函数的计算应该高效，不应该成为性能瓶颈。
- 分布均匀：哈希函数应该将键均匀地分布在整个数组中，避免聚集。
- 冲突少：不同的键被映射到相同索引的情况应该尽量少。
常见的哈希函数
整数哈希：对于整数键，可以使用简单的取模运算。
int hash(int key) {
return key % tableSize;
}
字符串哈希：对于字符串键，可以使用字符的ASCII值进行计算。
int hash(String key) {
int hash = 0;
for (int i = 0; i < key.length(); i++) {
hash = (hash * 31 + key.charAt(i)) % tableSize;
}
return hash;
}
Java中的hashCode方法：Java中的所有对象都有一个hashCode方法，可以用于计算哈希值。
3.3.3 冲突解决
当两个不同的键被哈希到同一个索引时，就会发生冲突（Collision）。冲突是不可避免的，因为键的数量通常远大于数组的大小。因此，我们需要有策略来解决冲突。
1. 链地址法（Chaining）
链地址法是最常用的冲突解决策略之一。它的基本思想是：
- 每个桶存储一个链表
- 当发生冲突时，将新元素添加到链表的末尾
- 查找时，遍历链表直到找到目标键
优点：
- 实现简单
- 不会浪费空间
- 支持无限数量的元素
缺点：
- 链表可能变得很长，导致查找效率下降
- 需要额外的空间来存储指针
生活例子：想象一个宿舍楼，每个房间都有一个编号。如果有多个学生被分配到同一个房间，那么这些学生会形成一个"室友链"，每个人都知道下一个室友是谁。
2. 开放寻址法（Open Addressing）
开放寻址法的基本思想是：当发生冲突时，尝试其他位置，直到找到一个空位置。常见的开放寻址策略包括：
线性探测（Linear Probing）：
- 如果位置i被占用，尝试位置i+1, i+2, …
- 简单但容易导致聚集问题
二次探测（Quadratic Probing）：
- 如果位置i被占用，尝试位置i+1², i+2², i+3², …
- 减少聚集问题
双重哈希（Double Hashing）：
- 使用第二个哈希函数计算步长
- 进一步减少聚集问题
优点：
- 不需要额外的空间来存储指针
- 缓存局部性更好
缺点：
- 当表变满时，性能会急剧下降
- 删除操作比较复杂
生活例子：想象你去停车场停车，发现你想停的位置已经被占用，于是你继续向前寻找下一个空位。
3.3.4 基于链地址法的哈希表实现
下面是一个基于链地址法的哈希表的Java实现：
// 哈希表节点类
class HashNode {
String key; // 键
int value; // 值
HashNode next; // 指向下一个节点的引用
// 构造函数
public HashNode(String key, int value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 哈希表类
class HashTable {
private HashNode[] buckets; // 桶数组
private int numBuckets; // 桶的数量
private int size; // 哈希表中的元素数量
// 构造函数
public HashTable(int capacity) {
this.numBuckets = capacity;
this.buckets = new HashNode[numBuckets];
this.size = 0;
}
// 返回哈希表中的元素数量
public int size() {
return size;
}
// 检查哈希表是否为空
public boolean isEmpty() {
return size() == 0;
}
// 计算键的桶索引
private int getBucketIndex(String key) {
int hashCode = key.hashCode();
// 确保索引为非负数，并取模以适应桶数组大小
return (hashCode & 0x7fffffff) % numBuckets;
}
// 插入键值对
public void put(String key, int value) {
// 计算桶索引
int bucketIndex = getBucketIndex(key);
HashNode head = buckets[bucketIndex];
// 检查键是否已存在
while (head != null) {
if (head.key.equals(key)) {
// 如果键已存在，更新值
head.value = value;
return;
}
head = head.next;
}
// 插入新节点到链表头部
size++;
head = buckets[bucketIndex];
HashNode newNode = new HashNode(key, value);
newNode.next = head;
buckets[bucketIndex] = newNode;
// 如果负载因子超过阈值，可以在这里调整哈希表大小
}
// 获取键对应的值
public int get(String key) {
// 计算桶索引
int bucketIndex = getBucketIndex(key);
HashNode head = buckets[bucketIndex];
// 在链表中查找键
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
// 键不存在
return -1;
}
// 删除键值对
public int remove(String key) {
// 计算桶索引
int bucketIndex = getBucketIndex(key);
HashNode head = buckets[bucketIndex];
HashNode prev = null;
// 在链表中查找键
while (head != null) {
if (head.key.equals(key)) {
break;
}
prev = head;
head = head.next;
}
// 键不存在
if (head == null) {
return -1;
}
// 减少元素数量
size--;
// 从链表中移除节点
if (prev != null) {
prev.next = head.next;
} else {
buckets[bucketIndex] = head.next;
}
return head.value;
}
// 打印哈希表内容（用于调试）
public void display() {
for (int i = 0; i < numBuckets; i++) {
System.out.print("Bucket " + i + ": ");
HashNode current = buckets[i];
while (current != null) {
System.out.print("(" + current.key + ", " + current.value + ") ");
current = current.next;
}
System.out.println();
}
}
// 主方法：测试哈希表
public static void main(String[] args) {
HashTable ht = new HashTable(10);
// 插入键值对
ht.put("apple", 10);
ht.put("banana", 20);
ht.put("cherry", 30);
ht.put("date", 40);
ht.put("elderberry", 50);
// 显示哈希表内容
System.out.println("哈希表内容：");
ht.display();
// 获取值
System.out.println("\n获取值：");
System.out.println("apple: " + ht.get("apple"));
System.out.println("banana: " + ht.get("banana"));
System.out.println("fig: " + ht.get("fig")); // 不存在的键
// 删除键值对
System.out.println("\n删除 'banana' 后：");
ht.remove("banana");
ht.display();
}
}
3.3.5 哈希表的性能分析
哈希表的性能主要取决于哈希函数的质量和冲突解决策略的效率。
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 查找 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
最坏情况：当所有键都被哈希到同一个桶时，哈希表退化为链表，操作的时间复杂度变为O(n)。
负载因子：负载因子是哈希表中元素数量与桶数量的比值。当负载因子增大时，冲突的可能性也会增加。因此，许多哈希表实现会在负载因子超过某个阈值（通常是0.75）时，自动增加桶的数量并重新哈希所有元素。
3.3.6 哈希表的应用场景
哈希表因其高效的查找、插入和删除操作，在许多场景中都有广泛应用：
数据库索引：数据库使用哈希索引来加速查询。
缓存系统：如Redis、Memcached等使用哈希表来存储键值对。
符号表：编译器和解释器使用哈希表来存储变量名和其属性。
关联数组：许多编程语言（如JavaScript的对象、Python的字典）使用哈希表实现关联数组。
去重：哈希表可以用来检测重复元素。
计数器：统计元素出现的频率。
缓存：实现LRU（最近最少使用）缓存。
生活中的哈希表应用例子
电话簿：你可以通过人名快速查找电话号码，而不需要从头到尾翻阅整本电话簿。
超市收银系统：收银员扫描商品条形码，系统立即显示商品信息和价格。
社交网络：当你搜索好友时，系统可以快速找到匹配的用户，而不需要遍历所有用户。
3.3.7 哈希表与其他数据结构的比较
| 数据结构 | 查找 | 插入 | 删除 | 有序性 | 空间效率 |
|---|---|---|---|---|---|
| 哈希表 | O(1) | O(1) | O(1) | 无 | 中 |
| 数组 | O(n) | O(1)* | O(n) | 无 | 高 |
| 链表 | O(n) | O(1) | O(n) | 无 | 中 |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | 有 | 中 |
| 平衡BST | O(log n) | O(log n) | O(log n) | 有 | 中 |
*数组在末尾插入的时间复杂度为O(1)，但在中间插入的时间复杂度为O(n)。
哈希表的优势：
- 查找、插入和删除操作的平均时间复杂度都是O(1)
- 实现简单，易于理解
哈希表的劣势：
- 不保持元素的顺序
- 需要一个好的哈希函数
- 可能需要动态调整大小
- 在最坏情况下性能可能下降到O(n)