ASCII哈希数值列表按模运算结果分配到哈希桶的实现问题

原有代码问题梳理 #

• 没有提前初始化固定数量的空桶，动态append会导致桶索引和w中计算出的下标无法对应
• 遍历取值逻辑错误：enumerate(asciis)返回的是(下标, ascii值)的元组，没有同步取w中对应下标的桶索引
• 语法错误：self.buckets[i for i in enumerate(w)]属于非法表达式，无实际意义
• 追加元素逻辑错误：不需要判断值是否存在，也不应该把w整体追加到桶列表中，要把单个ascii值加到对应下标的桶子列表里
• 求和逻辑遗漏字符转ASCII码步骤：直接对字符ch求和会报错，需要用ord(ch)转成ASCII数值再计算

正确实现逻辑 #

1. 类初始化阶段先创建指定数量的空桶，提前固定桶的索引：

# 类初始化阶段执行，size为桶的总数，示例场景为7
self.size = 7
self.buckets = [[] for _ in range(self.size)]

2. 分配逻辑直接同步遍历asciis和对应的索引列表w，将每个ascii值插入对应下标的桶即可：

def add(self, word):
    hashed_word = self.get_hash(word)
    # 计算每个词的ASCII求和值
    asciis = [sum([ord(ch) for ch in word]) for word in hashed_word]
    # 计算每个值对应的桶索引，取模的基数是桶的总数量
    w = [s % self.size for s in asciis]
    # 同步遍历ascii值和对应桶索引，分配到对应桶
    for ascii_val, bucket_idx in zip(asciis, w):
        self.buckets[bucket_idx].append(ascii_val)
    # 触发重哈希的判断可根据你的负载因子规则调整，示例阈值为0.7
    total_elements = sum(len(bucket) for bucket in self.buckets)
    if total_elements / self.size >= 0.7:
        self.rehash()

验证结果 #

用你给出的示例数据测试：

• 输入asciis = [382, 409, 385, 302, 371, 387, 371]
• 计算得到w = [6, 1, 1, 6, 3, 3, 3]
  执行分配后得到的self.buckets为[[], [409, 385], [], [371, 387, 371], [], [], [382, 302]]，你给出的预期结果索引3的位置少了最后一个371，属于笔误。

内容的提问来源于stack exchange，提问作者Alice 7t