hashtable - 编程语言用于字典/关联数组的默认哈希函数是什么？

Question

所以当我知道字典或关联数组通常由哈希表实现时，我很好奇。在阅读哈希表时，我偶然发现了哈希函数，我了解到有各种哈希函数，例如 md5、md6、sha-1 等。我无法找到的是 python、C++ 等编程语言使用的是哪种哈希函数, java?

Answer 1

那些..不是同一种“哈希函数” D:

对于 hashtable hash functions ，代码必须根据对象数据计算适当的散列，以使其符合相等性要求。它还应该“分布良好”和“快速”。因此，大多数哈希表哈希通常是使用某种形式的滚动/移位计算的 32 位值。在一天结束时，此哈希用于从小得多的存储桶池中进行选择。

哈希表哈希通常由(或知道)要添加到哈希表的对象直接计算 - 也就是说，通常，加密哈希函数不参与哈希表。典型的 Java hashCode()函数，在被添加到哈希表的对象上定义，例如可能如下所示:

int hash = 7;
hash = 31 * hash + (int) int_field;
hash = 31 * hash + (str_field == null ? 0 : str_field.hashCode());
// etc.
return hash;

有discussions on the choice of seed and multiplication values elsewhere ..但采取的方法应该是大多数哈希表哈希函数 1) 直接从对象状态派生，谨慎地应用“调整”，以及 2) 不是设计为“安全”。

(现代哈希表实现通常对生成的哈希值应用“混合函数”以减轻退化的哈希函数结果和/或数据中毒攻击。)

另一方面，cryptographic hash旨在提供更强的加密要求并具有更大的输出空间。虽然这样的强哈希可以用于哈希表(在从对象派生然后提炼到哈希桶之后)，但它们的生成速度也较慢并且通常在散列/字典。

加密哈希通常适用​​于任意数据 block 或字节流。

Hashtable hash 可取的特性:

• 确定性
• 均匀分布/避免聚类
• 速度，速度，速度

加密哈希具有附加特性，超出了哈希表哈希的特性:

• 无法从其哈希值生成消息
• 无法找到具有相同哈希值的两条不同消息
• (虽然加密散列也应该很快，但相对于额外的要求，速度在很大程度上是次要的。)

编程语言通过其 standard libraries 支持各种不同的加密哈希函数和/或第 3 方库。更广为人知的散列(例如 MD5/SHA-x)通常会得到普遍支持，而更专业的散列(例如 MD6)可能需要额外的努力来定位实现。

另一方面，如上所示，许多哈希表“函数”是直接在哈希表中涉及的对象上实现的，遵循标准模式，一些语言(和 IDE)提供帮助以减少手动编码.例如，C# 为结构类型提供了默认的基于反射的 GetHashCode 实现。