Индексирование хеш-таблиц

Question

Я только начинаю изучать хеш-таблицы, и до сих пор я знаю, что вы берете объект, который хотите хэшировать, и помещаете его через хеш-функцию, а затем используете возвращаемый индекс, чтобы получить соответствующий объект, который вы хотите.Однако есть кое-что, чего я не понимаю:

Какую структуру вы используете для хранения объектов, чтобы вы могли быстро проиндексировать их с помощью кода, возвращаемого хэш-функцией?Единственное, о чем я могу думать, - это использовать массив, но для обработки всех ключей вам нужно выделить один, который будет иметь 9999999999999 элементов или что-то нелепое.Или это так же просто, как перебирать связанный список или что-то еще и сравнивать идентификатор в каждом из элементов с ключом из этой хеш-функции?И если это так, то это кажется неэффективным, не так ли?

Answer 1

Обычно вы используете массив (или что-то похожее на вектор). Вы выбираете разумный размер (например, на 20% больше, чем ожидаемое количество элементов) и какой-то метод разрешения коллизий, когда / если два ключа выдают одинаковое хеш-значение (например, каждое из этих мест является заголовком связанного списка элементы, хэшированные до этого значения).

Answer 2

Да, вы обычно используете массив, но затем делаете пару вещей:

1. Вы конвертируете хэш-код в индекс массива, используя остаток хеш-кода, деленный на размер массива.

2. Вы делаете размер массива простым числом, поскольку это делает шаг # 1 более эффективным (некоторым хеш-алгоритмам это необходимо для получения равномерного распределения)

3. Вы придумали конструкцию для обработки хеш-столкновений. @ JerryCoffin ответ дает вам более подробную информацию.

Answer 3

Обычно это массив.Если размер массива равен N, используйте хеш-функцию, которая возвращает числа в диапазоне 0..(N-1).Например, примените modulo N к результату хеш-функции.А затем используйте разрешение столкновений в Википедии.