为什么2D哈希映射是内存效率低下？

Question

朋友告诉我，由于碎片问题，强烈建议不要使用2D哈希表？任何人都可以告诉如果是这种情况，为什么？

Answer 1

就我个人而言，如果合理需要2d散列表，我不认为有任何理由阻止使用。

他们可能指的是系统如何处理碰撞。如果两个不同的值以相同的散列值位置结束，我们该怎么做？我们仍然需要将它们都存储起来。有几种不同的技术可以用来处理这个问题，其中之一是旨在从一大堆可能的散列值位置开始，这可能会导致大量的浪费空间。更好的方法是检查下一个可用位置，直到找到空闲位置。

自从我研究这些类型的存储以来，这已经有一段时间了，但这似乎就像他们可能在谈论的那样。这不是一个主要问题，当然也不是一个不使用hashmaps（包括2d）的理由。我不确定这一点，但我认为上面的问题复合使用更多的维度（因此更多的是2d散列表问题）。

Answer 2

为了高效，hashmap需要一定数量的空白空间，否则冲突率会太高。如果哈希映射包含更多hashmaps，则效果会相乘 - 如果每个哈希映射满了50％，则组合只有25％满。

更有效的策略可能是将两个密钥合并成一个密钥并使用单级哈希映射。