实现哈希表（HashMap）

哈希表是一种基于键值对存储的数据结构，通过哈希函数将键映射到数组的特定位置，从而实现平均O(1)时间复杂度的插入、查找和删除操作。下面逐步讲解如何实现一个基础的哈希表。

1. 核心结构设计

哈希表主要由两部分组成：

• 数组（Buckets）：用于存储键值对，每个位置称为一个"桶"（Bucket）。
• 哈希函数：将任意类型的键转换为数组范围内的整数索引。

对于哈希冲突（不同键映射到同一索引），常用链地址法（Chaining）解决，即每个桶使用链表存储冲突的键值对。

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

class HashMap:
    def __init__(self, capacity=1000):
        self.capacity = capacity  # 初始桶数量
        self.buckets = [None] * capacity
        self.size = 0  # 当前键值对数量

2. 哈希函数设计

哈希函数需满足：

• 均匀分布：键应均匀映射到不同索引。
• 高效计算：快速计算索引。

简单实现（以字符串键为例）：

def _hash(self, key):
    # 将键转换为字符串后计算哈希值
    key_str = str(key)
    hash_code = 0
    for char in key_str:
        hash_code = (hash_code * 31 + ord(char)) % self.capacity
    return hash_code

实际中可直接用Python内置的hash()函数，但需取模限制在数组范围内：

def _hash(self, key):
    return hash(key) % self.capacity

3. 插入操作（Put）

步骤：

1. 计算键的哈希索引。
2. 若该桶为空，直接插入新节点。
3. 若桶非空，遍历链表：
   • 若找到相同键，更新值。
   • 若未找到，在链表头部插入新节点。
4. 检查负载因子（Load Factor），若过高则扩容。

def put(self, key, value):
    index = self._hash(key)
    node = self.buckets[index]
    
    # 遍历链表，检查键是否已存在
    while node:
        if node.key == key:
            node.val = value  # 更新值
            return
        node = node.next
    
    # 键不存在，插入新节点到链表头部
    new_node = ListNode(key, value)
    new_node.next = self.buckets[index]
    self.buckets[index] = new_node
    self.size += 1
    
    # 检查负载因子（假设阈值0.75）
    if self.size / self.capacity > 0.75:
        self._resize()

4. 查找操作（Get）

步骤：

1. 计算哈希索引。
2. 遍历该桶的链表，查找匹配的键。
3. 找到返回对应值，否则返回None或抛出异常。

def get(self, key):
    index = self._hash(key)
    node = self.buckets[index]
    while node:
        if node.key == key:
            return node.val
        node = node.next
    return None  # 或抛出KeyError

5. 删除操作（Remove）

步骤：

1. 计算哈希索引。
2. 遍历链表，找到匹配的键并删除节点（需处理链表指针）。
3. 若键不存在可抛出异常。

def remove(self, key):
    index = self._hash(key)
    node = self.buckets[index]
    prev = None
    while node:
        if node.key == key:
            if prev:
                prev.next = node.next
            else:
                self.buckets[index] = node.next
            self.size -= 1
            return
        prev = node
        node = node.next
    raise KeyError(f"Key {key} not found")

6. 动态扩容（Resize）

当负载因子过高时（如>0.75），哈希冲突概率增大，性能下降。需扩容：

1. 创建新容量（如2倍）的数组。
2. 遍历所有桶中的键值对，重新哈希到新数组。
3. 更新哈希表的桶数组和容量。

def _resize(self):
    new_capacity = self.capacity * 2
    new_buckets = [None] * new_capacity
    
    # 临时保存旧数据
    old_buckets = self.buckets
    self.capacity = new_capacity
    self.buckets = new_buckets
    self.size = 0
    
    # 重新插入所有键值对
    for bucket in old_buckets:
        node = bucket
        while node:
            self.put(node.key, node.val)  # 注意：这里会重新计算哈希
            node = node.next

7. 时间复杂度分析

• 平均情况：插入、查找、删除均为O(1)（假设哈希函数均匀分布）。
• 最坏情况：所有键冲突，退化为链表操作，时间复杂度O(n)。

8. 实际优化考虑

• 哈希函数选择：需减少冲突（如SHA-256用于加密场景，但一般场景用简单哈希即可）。
• 负载因子阈值：Java HashMap默认0.75，平衡空间与时间效率。
• 链表优化：当链表过长时（如>8），可转换为红黑树（如Java HashMap）。
• 并发安全：多线程环境下需加锁或使用并发哈希表。

通过以上步骤，可实现一个功能完整的哈希表，理解其核心原理有助于应对相关面试问题。