Раздельная цепочка в ha sh map

Question

Насколько я понимаю, отдельная цепочка состоит в том, что мы конвертируем большое число в небольшое, чтобы мы могли использовать его как индекс. Но как нам справиться с большим индексом? Например, текущий размер моего hash_map равен 10, новый индекс, рассчитанный функцией ha sh, равен 55. Так нужно ли мне изменять размер моего hash_map каждый раз, когда новый индекс слишком велик?

Спасибо!

Answer 1

Обычный метод - иметь функцию ha sh, которая вычисляет некоторое целое число (обычно 32-битное или 64-битное), а затем сокращать это число до допустимого индекса в таблице ha sh путем модификации этого целого числа. по размеру стола. Например, если у вас есть таблица ha sh с 10 элементами и ваш код ha sh равен 55, вы должны вычислить 55 mod 10 = 5 и поместить элемент в индекс 5.

В зависимости от вашего языка программирования, здесь могут быть некоторые крайние случаи (скажем, если код ha sh может быть отрицательным, вам нужно убедиться, что ваш индекс положительный), но эта общая идея работает довольно хорошо и используется во многих общие реализации таблиц ha sh.