algorithm - 哈希函数学习指南

Question

这是我的期末学习指南上的一个问题，我似乎不明白。

问：假设所有变量名称都必须以字母开头，可能是字母和数字的混合，并且区分大小写，最长可达 10 个字符。哈希表是 1000 个条目。建议一个适用于此表大小的哈希函数。

这会是 64^10 之类的吗？

谢谢你

Answer 1

有很多散列函数适用于这些约束，它实际上取决于字符的可能分布，哪个是最好的。

我假设您的数字是变量名称的可能性数量，但它有点错误 - 它应该限制第一个字符不能是数字，但无论如何，这不允许变量短于十字符，所以它只是近似值。实际上，它会类似于.641052x62952 + 52x62 + 52x622 + 52x622 + ... + 52x629

它也与散列函数本身几乎无关。

您可以选择的最简单的散列函数可能是遍历变量名称，提取每个“值”（0 到 61 表示 26 个大写字母、26 个小写字母和 10 个数字），然后根据该值简单地计算 0 到 999 之间的值：

def hashIt (varname):
    chars =
        "0123456789" +
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
         abcdefghijklmnopqrstuvwxyz"
    hashVal = 0
    for each char in varname:
        hashVal = (hashVal * len(chars) + chars.findIndexOf(char)) % 1000
    return hashVal

同样，这并没有考虑到字母的可能分布，但是，由于您没有提供有关这方面的信息，我们可以做的事情不多。