哈希算法题目：设计一个简单的数据库索引

题目描述
设计一个简单的数据库索引系统，支持以下操作：

1. insert(record_id, data)：插入一条记录，包含记录ID和数据。
2. search(record_id)：根据记录ID查找对应的数据，若存在返回数据，否则返回空。
3. delete(record_id)：根据记录ID删除记录。

要求使用哈希算法实现快速操作，并处理哈希冲突。假设记录ID是整数，数据为字符串。

解题过程

步骤1：理解哈希索引的基本原理

哈希索引通过哈希函数将记录ID映射到数组的某个位置，从而实现快速查找。理想情况下，插入、查找和删除的时间复杂度为O(1)。但需解决哈希冲突（即不同ID映射到同一位置的问题）。

步骤2：设计哈希函数

选择简单的哈希函数：

hash(key) = key % capacity

其中 capacity 是底层数组的大小（通常取质数以减少冲突）。例如，若容量为1009，则ID为201的记录映射到位置 201 % 1009 = 201。

步骤3：解决哈希冲突的方法

采用链地址法（Separate Chaining）：每个数组位置维护一个链表，冲突的记录按顺序存储在链表中。

• 插入时：计算哈希值，若该位置为空，直接存入；否则将新记录添加到链表末尾。
• 查找时：计算哈希值，遍历链表查找目标ID。
• 删除时：计算哈希值，遍历链表删除对应节点。

步骤4：具体实现细节

1. 数据结构定义：

   • 每个节点包含 record_id、data 和指向下一个节点的指针。
   • 哈希表是一个固定大小的数组，每个元素为链表头指针。

2. 插入操作：

   • 计算 index = record_id % capacity。
   • 若 table[index] 为空，直接创建新节点作为头节点。
   • 若冲突，遍历链表：
     • 若遇到相同ID，更新数据（根据需求决定是否允许重复ID）。
     • 否则将新节点追加到链表末尾。

3. 查找操作：

   • 计算 index，遍历链表，比较ID直至找到匹配项或链表结束。

4. 删除操作：

   • 计算 index，遍历链表找到目标节点，调整相邻节点的指针以删除节点。

步骤5：复杂度分析

• 平均情况（哈希函数分布均匀）：
  • 插入、查找、删除：O(1)（假设链表长度常数）。
• 最坏情况（所有ID映射到同一位置）：
  • 所有操作退化为O(n)，n为记录数。

步骤6：优化考虑

1. 动态扩容：当记录数超过容量阈值时，扩大数组并重新哈希所有记录，以保持低冲突率。
2. 哈希函数优化：若ID分布不均匀，可采用更复杂的哈希函数（如MD5后取模）。

示例演示
假设容量为5，依次操作：

1. insert(3, "Alice") → index=3，直接存入。
2. insert(8, "Bob") → index=3（冲突），在index=3的链表追加节点。
3. search(8) → 遍历index=3的链表，找到"Bob"。
4. delete(3) → 删除index=3链表的头节点，链表只剩节点8。

通过这种设计，哈希索引在常规场景下能高效支持数据库的增删查操作。