列表满时倍增，但hashmap/hashtable在达到负载因子时倍增，那么为什么hashmap不能等待调整大小直到满，它是底层hasing算法的一部分吗？
问问题
149 次
3 回答
5
数组列表和哈希映射之间有很大的区别：前者将每个条目存储到离散槽中，而后者可能会在条目的哈希匹配时将多个条目放入一个槽中。这意味着哈希映射可能在每个插槽被占用之前很久就开始变慢，实际上，您不太可能在必须在插槽中加倍之前只填充每个插槽一次。
如果您有一组可以散列的固定事物，则可以创建一个散列并从中创建一个散列映射，该散列映射将以有效的方式存储该固定的事物集：结果称为完美散列.
于 2012-07-17T14:55:11.697 回答
3
因为散列冲突的概率在其容量即将结束时急剧上升（没有足够的空桶）。随着更多条目最终进入相同的存储桶，查询的效率在它满之前很久就降低了。根据散列算法，最佳负载因子可能会有所不同。
数组查询的有效性不受其负载因子的影响，这就是为什么提前调整大小没有意义。
于 2012-07-17T14:57:16.617 回答
1
数组列表总是将新元素放在下一个空闲槽中，除非您想在将来节省时间，否则在占用该槽之前无需扩展 - 在这种情况下，您可以使用ensureCapacity.
另一方面，哈希图会为您放入其中的每个对象计算一个整数值。基于这个值，对象被存储在一个特定的桶中——这样做是为了支持快速查找。但是，计算的值不一定是唯一的，即使是两个不同的值也可能指向同一个桶。这对于少量的水桶尤其常见，如果您的水桶几乎满了，这种情况极有可能发生。
考虑一个哈希图，它根据生日将人们存储在桶中。即使有 365 个桶，如果有 10 个人，也有大约 10% 的机会发生碰撞。23 有50%的机会（更多在这里）。
现在，单个冲突并不是什么大问题，但是当您使用 hashmap 时，您通常会使用它来进行快速查找。如果多个项目在同一个存储桶中，则执行查找所需的时间会越来越长。因此，出于性能原因，您希望增加存储桶的数量以降低元素的密度。
于 2012-07-17T15:05:15.017 回答