Python----数据结构（哈希表：哈希表组成，哈希冲突）

一、哈希表

哈希表(Hash table)是一种常用、重要、高效的数据结构。

哈希表通过哈希函数,可以快速地将键(Key)映射到值(Value)。从而允许在近常数时间内对键关联的值进行插入、删除和查找操作。

哈希表的主要思想是通过哈希函数将键转换为索引，将索引映射到数组中的存储位置

通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表，在首字母为L的表中查找“雷”姓的电话号码，显然比直接查找就要快得多。

二、代码展示

2.1、键值对

class Pair:  """键值对的类，包含一个键和一个值"""  def __init__(self, key: int, val: str):  """初始化键值对"""  self.key = key  # 键，整数类型  self.val = val  # 值，字符串类型  def __repr__(self):  """返回键值对的字符串表示"""  return f"{self.key} -> {self.val}"

2.2、初始化

    def __init__(self):  """构造方法，初始化哈希表"""  # 创建一个包含 100 个桶的数组  self.buckets: list[Pair | None] = [None] * 100

2.3、哈希函数

    def hash_func(self, key: int) -> int:  """哈希函数，将键映射到索引"""  index = hash(key) % 100  # 使用内置哈希函数计算键的哈希值，并对桶的数量取模  return index

2.4、添加键值对

    def put(self, key: int, val: str):  """添加键值对到哈希表"""  pair = Pair(key, val)  # 创建新的键值对  index: int = self.hash_func(key)  # 计算键的哈希索引  self.buckets[index] = pair  # 将键值对放入相应的桶中

2.5、查询值

    def get(self, key: int) -> str:  """根据给定的键查询值"""  index: int = self.hash_func(key)  # 计算键的哈希索引  pair: Pair = self.buckets[index]  # 获取对应的键值对  if pair is None:  return None  # 如果未找到，返回 None  return pair.val  # 返回找到的值

2.6、删除键值对

    def remove(self, key: int):  """根据给定的键删除键值对"""  index: int = self.hash_func(key)  # 计算键的哈希索引  self.buckets[index] = None  # 将桶置为 None，表示删除

2.7、返回所有键值对

    def entry_set(self) -> list[Pair]:  """返回哈希表中所有的键值对"""  result: list[Pair] = []  for pair in self.buckets:  if pair is not None:  result.append(pair)  # 将非空桶的键值对添加到结果列表中  return result

2.8、返回键

    def key_set(self) -> list[int]:  """返回哈希表中所有的键"""  result = []  for pair in self.buckets:  if pair is not None:  result.append(pair.key)  # 将非空桶的键添加到结果列表中  return result

2.9、返回值

    def value_set(self) -> list[str]:  """返回哈希表中所有的值"""  result = []  for pair in self.buckets:  if pair is not None:  result.append(pair.val)  # 将非空桶的值添加到结果列表中  return result

2.10、输出

    def print(self):  """打印哈希表中的所有键值对"""  for pair in self.buckets:  if pair is not None:  print(pair.key, "->", pair.val)  # 打印每个键值对

2.11、完整代码

class Pair:  """键值对的类，包含一个键和一个值"""  def __init__(self, key: int, val: str):  """初始化键值对"""  self.key = key  # 键，整数类型  self.val = val  # 值，字符串类型  def __repr__(self):  """返回键值对的字符串表示"""  return f"{self.key} -> {self.val}"  class ArrayHashMap:  """基于数组实现的哈希表"""  def __init__(self):  """构造方法，初始化哈希表"""  # 创建一个包含 100 个桶的数组  self.buckets: list[Pair | None] = [None] * 100  def hash_func(self, key: int) -> int:  """哈希函数，将键映射到索引"""  index = hash(key) % 100  # 使用内置哈希函数计算键的哈希值，并对桶的数量取模  return index  def put(self, key: int, val: str):  """添加键值对到哈希表"""  pair = Pair(key, val)  # 创建新的键值对  index: int = self.hash_func(key)  # 计算键的哈希索引  self.buckets[index] = pair  # 将键值对放入相应的桶中  def get(self, key: int) -> str:  """根据给定的键查询值"""  index: int = self.hash_func(key)  # 计算键的哈希索引  pair: Pair = self.buckets[index]  # 获取对应的键值对  if pair is None:  return None  # 如果未找到，返回 None  return pair.val  # 返回找到的值  def remove(self, key: int):  """根据给定的键删除键值对"""  index: int = self.hash_func(key)  # 计算键的哈希索引  self.buckets[index] = None  # 将桶置为 None，表示删除  def entry_set(self) -> list[Pair]:  """返回哈希表中所有的键值对"""  result: list[Pair] = []  for pair in self.buckets:  if pair is not None:  result.append(pair)  # 将非空桶的键值对添加到结果列表中  return result  def key_set(self) -> list[int]:  """返回哈希表中所有的键"""  result = []  for pair in self.buckets:  if pair is not None:  result.append(pair.key)  # 将非空桶的键添加到结果列表中  return result  def value_set(self) -> list[str]:  """返回哈希表中所有的值"""  result = []  for pair in self.buckets:  if pair is not None:  result.append(pair.val)  # 将非空桶的值添加到结果列表中  return result  def print(self):  """打印哈希表中的所有键值对"""  for pair in self.buckets:  if pair is not None:  print(pair.key, "->", pair.val)  # 打印每个键值对  if __name__ == '__main__':  map = ArrayHashMap()  # 创建一个新的哈希表实例  map.put('m', '蟒')  # 添加键值对  map.put('s', '蛇')  map.put('c', '程')  map.put('x', '序')  map.put('y', '员')  # 查询并打印值  print(map.get('m'))  # 输出：蟒  print(map.get('s'))  # 输出：蛇  print(map.get('c'))  # 输出：程  print(map.get('x'))  # 输出：序  print(map.get('y'))  # 输出：员  # 打印哈希表的内容  map.print()  print(map.entry_set())  # 输出所有的键值对