Python实现1009大小联系人哈希表索引不符预期问题求助

根本错误：哈希函数的方法定义错误 #

你的Contact类中calc_hash方法的定义存在严重问题：它被当作类方法调用，但既没有添加@classmethod/@staticmethod装饰器，也没有正确定义方法参数，导致参数传递完全混乱，这是索引与预期不符的核心原因。

错误细节 #

当你通过Contact.calc_hash(key, self.size)调用该方法时，Python会自动把Contact类本身作为第一个参数传入key形参，而你实际传入的名字（如"Sam Doe"）会被当作第二个参数table_size，彻底打乱了哈希计算逻辑，自然得到错误的哈希值和索引。

修复方案 #

将calc_hash改为静态方法，明确参数逻辑：

class Contact:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone

    @staticmethod
    def calc_hash(key, table_size):
        l = len(key)
        hash_value = 0

        for i in range(l):
            hash_value += ord(key[i])
            hash_value += (hash_value << 10)
            hash_value ^= (hash_value >> 6)

        hash_value += (hash_value << 3)
        hash_value ^= (hash_value >> 11)
        hash_value += (hash_value << 15)

        return abs(hash_value) % table_size  # 简化正负值处理逻辑

验证修复结果 #

修复后单独计算每个名字的原始哈希值，与你的预期完全一致：

print(Contact.calc_hash("John Smith", 1009))  # 输出343
print(Contact.calc_hash("Sam Doe", 1009))     # 输出681
print(Contact.calc_hash("Lisa Smith", 1009))  # 输出950

再运行完整代码，三个联系人会直接插入到各自的原始哈希索引位置，不会触发线性探测（当前插入顺序下无冲突），最终索引与预期完全匹配。

额外优化建议 #

• 线性探测逻辑可简化：因为步长为1，(index + attempt) % self.size等价于(index + 1) % self.size，无需依赖attempt参数，每次循环直接自增1即可。
• 添加哈希表满的判断：插入和搜索逻辑中增加最大尝试次数限制，避免哈希表满时出现无限循环。

内容的提问来源于stack exchange，提问作者Hossam sokkary