散列表

一、散列表基础定义

散列表（Hash Table，又称哈希表）是一种根据键（Key）直接访问内存存储位置值（Value）的数据结构，由数组演化而来，利用了数组按下标随机访问的特性。

核心逻辑：通过散列函数将键（Key）映射为数组下标（hashValue = hash(key)），从而实现O(1)时间复杂度的快速访问。

---

二、散列函数与核心要求

散列函数的作用是将键（Key）映射为数组下标，需满足以下要求：

1. 计算得到的散列值必须为大于等于0的正整数（作为数组下标）
2. 若 key1 == key2，则 hash(key1) == hash(key2)（一致性）
3. 理想情况下，若 key1 != key2，则 hash(key1) != hash(key2)（避免冲突）

---

三、散列冲突与解决方式

1. 散列冲突定义

多个不同的键（Key）经过散列函数计算后，映射到同一个数组下标位置，称为散列冲突（哈希碰撞）。实际中几乎无法避免，需通过特定方式解决。

2. 拉链法（链地址法）

数组的每个下标位置（桶/槽）对应一条链表，所有散列值相同的元素都放入该槽位对应的链表中：

• 插入操作：通过散列函数计算槽位，直接插入链表头部，时间复杂度O(1)
• 查找/删除操作：先计算槽位，再遍历链表定位元素
  • 平均情况：链表长度较短，时间复杂度接近O(1)
  • 极端情况：链表过长（退化为纯链表），时间复杂度退化为O(n)

3. 优化方案：链表转红黑树

当链表长度过长时，将链表改造为红黑树，将查找/删除操作的时间复杂度从O(n)优化为O(log n)，同时可防止DDoS攻击（避免攻击者构造大量冲突数据拖慢系统）。

---

四、面试高频问题解析

1. 问：什么是散列表？它的核心优势是什么？答： 散列表是通过散列函数将键映射为数组下标的数据结构，核心优势是平均情况下插入、查找、删除操作的时间复杂度为O(1)，访问效率极高。

2. 问：什么是散列冲突？如何解决？答： 散列冲突是指不同键映射到同一数组下标。常用解决方式为拉链法（链地址法），即每个槽位维护一条链表存储冲突元素；当链表过长时，可转为红黑树优化查询效率。

3. 问：为什么要将链表改造为红黑树？答： 当链表过长时，查询效率会从O(1)退化为O(n)，红黑树可将时间复杂度优化为O(log n)，同时避免因大量冲突数据导致的性能问题，提升系统稳定性。

4. 问：散列函数的设计原则是什么？答： 需满足一致性（相同键映射到同一位置）、高效性（计算速度快）和低冲突率（不同键尽量映射到不同位置），同时散列值需为非负整数以作为数组下标。