Почему 2D-хэш-память неэффективна?

Question

Мне сказали друзья, что использование 2D-хэш-карты сильно обескуражено из-за проблемы фрагментации? Может ли кто-нибудь сказать, если это так и почему?

Answer 1

Лично я не вижу причин препятствовать использованию, если есть законная потребность в 2-х хэш-карте.

Что они могут иметь в виду, так это то, как система имеет дело с столкновениями. Если два разных значения совпадают с одной и той же позицией хеш-позиции, что мы будем делать? Нам все равно нужно их хранить. Существует несколько различных методов, используемых для решения этой проблемы, и одна из них заключается в том, чтобы начать с очень большого набора возможных позиций хэш-позиции, что потенциально может привести к большому количеству потраченного впустую пространства. Лучший метод - просто проверить следующую доступную позицию, пока не найдет свободное место.

Прошло некоторое время с тех пор, как я изучил хранилище этих типов, но это похоже на то, о чем они могут говорить. Это не главная проблема и, конечно, не причина никогда не использовать хэшмапы (в том числе 2d). Я не уверен в этом, но я думаю, что проблемы выше составных, когда они используются в больших размерах (следовательно, больше проблема с 2-х хэш-картами).

Answer 2

Для того, чтобы быть эффективным, для хэш-карты требуется определенное количество пустого пространства, иначе скорость столкновения будет слишком высокой. Если хэш-карта содержит больше хэш-карт, эффект умножается - если каждая хэш-карта заполнена на 50%, комбинация заполняется только на 25%.

Более эффективной стратегией может быть объединение двух ключей в один ключ и использование одноуровневой хэш-карты.