哈希表（Hash Table）是一种常用的数据结构，它可以在常数时间内完成查找、插入和删除操作。哈希表通过 键值对 的形式存储数据，每个键（Key）通过一个 哈希函数 映射到表中的某个位置，该位置用于存储对应的值（Value）。
哈希函数：哈希函数将输入的键转换成表中的索引。一个好的哈希函数能尽可能均匀地分布数据，减少冲突。
冲突处理：由于哈希表的存储空间有限，不同的键可能会映射到相同的索引位置，这就是所谓的“冲突”。处理冲突的常见方法有：
• 开放地址法：如果某个位置已经被占用，尝试查找下一个空闲位置。
• 链地址法：每个哈希表的槽点存储一个链表，当冲突发生时，将新的键值对加入该链表中。
哈希表的优点
• 查找、插入、删除操作的时间复杂度为 O(1)，即常数时间。
• 哈希表非常适合用于需要快速查找和存储的数据场景，如缓存、字典等。
在 Python 中，内置的 dict 类型就是哈希表的一种实现，使用非常方便。我们可以用字典来存储键值对，查找和插入操作的时间复杂度接近 O(1)。
不过，我们也可以手动实现一个简单的哈希表来理解其内部工作机制。下面是一个基于链地址法的哈希表实现：
使用链地址法实现哈希表：
class HashTable:
def __init__(self, size=100):
"""初始化哈希表，并设置默认大小"""
self.size = size
self.table = [[] for _ in range(size)] # 每个槽点存储一个链表
def _hash(self, key):
"""哈希函数：将键转换为索引"""
return hash(key) % self.size
def insert(self, key, value):
"""插入键值对"""
index = self._hash(key)
# 检查键是否已经存在，若存在则更新
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
# 否则，插入新的键值对
self.table[index].append([key, value])
def get(self, key):
"""根据键查找对应的值"""
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
# 如果键不存在，返回 None
return None
def delete(self, key):
"""删除键值对"""
index = self._hash(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return True
return False
def __repr__(self):
"""返回哈希表的字符串表示，便于调试"""
return str(self.table)
# 测试哈希表
ht = HashTable()
# 插入键值对
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "New York")
# 获取值
print(ht.get("name")) # 输出: Alice
print(ht.get("age")) # 输出: 30
# 更新值
ht.insert("age", 31)
print(ht.get("age")) # 输出: 31
# 删除键值对
ht.delete("city")
print(ht.get("city")) # 输出: None
# 打印整个哈希表
print(ht)
代码解释