java - 是什么让 hashmap 更快？

Question

所以我知道散列图使用桶和散列码等等。根据我的经验，Java 哈希码并不小，但通常很大，所以我假设它没有在内部建立索引。除非哈希码质量很差导致桶长度和桶数量大致相等，否则 HashMap 比名称-> 值对列表更快的原因是什么？

Answer 1

HashMap 通过使用哈希函数将元素映射到“桶”来工作。当有人试图插入一个元素时，会计算一个散列码，并对散列码进行取模运算，以获得应该插入元素的桶索引(这就是为什么哈希码有多大并不重要)。例如，如果你有 4 个桶，你的 hashcode 是 40，它会被插入桶 0，因为 40 mod 4 是 0。

当两个元素映射到同一个桶时，会发生“冲突”，通常该元素存储在同一个桶下的列表中。

如果您尝试获取一个元素，则使用哈希函数再次映射该键。如果桶包含一个元素列表，则使用 equals() 函数来识别哪个元素是正确的(这就是为什么必须实现 equals() 和 hashcode() 以将自定义对象插入 HashMap 的原因).

因此，如果您搜索一个元素，而您的 HashMap 在桶中没有任何列表，则您的成本为 O(1)。最坏的情况是当您只有 1 个桶和一个包含所有元素的列表时，在其中获取一个元素与在列表 O(N) 上搜索相同。