Python基于拉链法实现字典（散列表）详解

Alice

发布时间：2026-10-13 | 2人浏览过

原创

本文介绍如何在Python中使用列表模拟字典，重点讲解利用拉链法解决Hash冲突的方法。通过在每个哈希桶中嵌套子列表，即使发生碰撞也能存储数据，配合良好的Hash函数和足够大的表长，可实现接近O(1)的查找效率。

前言

字典（亦称散列表）的核心优势在于能够通过键（key）快速定位对应的值，其理想状态下的时间复杂度为O(1)。下文将详细介绍如何在Python中基于拉链法构建字典功能。

在Python中，如何利用列表来模拟字典结构？

使用列表实现字典时，核心难点在于处理Hash冲突。当不同的键通过哈希计算映射到相同的索引位置时，该如何妥善存储这些数据？

一种简单有效的解决方案是采用拉链法（Chaining）。

拉链法的原理是：在列表的每个索引位置再嵌套一个子列表。即便发生Hash冲突，新元素仍可存入该位置的子列表中。只要选取的Hash函数质量足够高，

且列表容量num设置得足够大，就能确保每个子列表中的元素极少（理想情况下仅有一个）。此时，通过键计算哈希值定位到具体位置，

即可实现平均时间复杂度为O(1)的数据访问。

方法示例

class MyDict:
 def __init__(self, num=100): # 指定列表大小
  self._num = num
  self._lst = []
  for _ in range(self._num):
   self._lst.append([])

 def update(self, key, value): # 添加 key-value
  key_index = hash(key) % self._num
  for i, (k, v) in enumerate(self._lst[key_index]):
   if key == k:
    self._lst[key_index][i] = [key, value]
    break
  else:
   self._lst[key_index].append([key, value])

 def get(self, key): # 根据指定的 key 弹出值
  key_index = hash(key) % self._num
  for k, v in self._lst[key_index]:
   if k == key:
    return v
  else:
   raise KeyError('No such {} key'.format(key))

 def pop(self, key): # 根据 key 弹出元素 并且删除
  key_index = hash(key) % self._num
  for i, (k, v) in enumerate(self._lst[key_index]):
   if k == key:
    result = v
    self._lst.pop(i)
    return result
  else:
   raise KeyError('No such {} key'.format(key))

 def __getitem__(self, key): # 可以通过下标来取值
  key_index = hash(key) % self._num
  for k, v in self._lst[key_index]:
   if k == key:
    return v
  else:
   raise KeyError('No such {} key'.format(key))

 def keys(self): # 取得所有的key
  for index in range(self._num):
   for k, v in self._lst[index]:
    yield k

 def values(self): # 取得所有的 value
  for index in range(self._num):
   for k, v in self._lst[index]:
    yield v

 def items(self): # 取得所有的条目
  for index in range(self._num):
   for item in self._lst[index]:
    yield item

通过键查询数据的时间表现，可见下图