是什么让哈希图更快？

Question

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

Answer 1

哈希映射的工作原理是使用哈希函数将元素映射到“存储桶”。当有人试图插入一个元素时，会计算一个哈希码，并对哈希码进行模运算，以获得应插入该元素的桶索引（这就是为什么无论多大都没关系的原因）哈希码是）。例如，如果您有 4 个存储桶，并且您的哈希码是 40，则它将插入到存储桶 0 中，因为 40 mod 4 是 0。

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

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

因此，如果您搜索一个元素，并且您的哈希映射的存储桶上没有任何列表，则您的成本为 O(1)。最坏的情况是，当您只有 1 个存储桶和一个包含所有元素的列表时，其中获取元素与在列表中搜索的时间复杂度 O(N) 相同。