什么让hashmaps更快？

Question

所以我明白，hashmaps使用桶和hashcode和什么不是。根据我的经验，Java的hashcodes不是很小，而是通常数量很大，所以我认为它没有在内部建立索引。除非哈希码质量差，导致大致相等的桶长度和数量桶，那么什么使hashmaps比名称 - >值对列表更快？

Answer 1

通过使用散列函数将元素映射到“桶”，散列图工作。当有人试图插入一个元素时，会计算一个哈希码，并对散列码应用一个模数运算，以便获取元素应该插入其中的存储区索引（这就是为什么它并不重要散列码有多大）。例如，如果您有4个存储桶并且您的散列代码为40，则它将被插入到存储桶0中，因为40模4是0.

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

如果尝试获取元素，则使用散列函数再次映射密钥。如果存储区包含元素列表，则使用equals（）函数来标识哪个元素是正确的（这就是为什么您必须实现equals（）和hashcode（）以将自定义对象插入到散列表中的原因）。

所以，如果你搜索一个元素，并且你的hashmap在桶上没有任何列表，你就有O（1）的成本。最糟糕的情况是，只有一个桶和一个包含所有元素的列表，其中获取元素与在列表O（N）上搜索相同。

Answer 2

我查看了Java的实现，发现它有点类似于模数，这对减少数组大小有很大的意义。这允许O（1）访问，使HashMaps更好。