Раздельно связывание как способ борьбы с коллизиями в хеш-таблице
Необходимо реализовать борьбу с коллизиями методом раздельного связывания. Однако на просторах интернета мне не удалось найти какую либо информацию касательно этого метода. Возможно у него есть другое, более распространённое название?
Ответы (1 шт):
Я вот тоже посмотрел на это и понял, что я такого не знаю. Но благодаря "обратному переводу через гугл" я восстановил название. Это называется в английском Separate Chaining - https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/ (там есть картинки!) или классика - wiki -> Hash_table -> Separate_chaining или ru wiki - Метод цепочек
Суть очень проста и популярна - внутри хеш-таблица хранится как массив фиксированного размера, элементы которого - связанные списки. По хешу ключа определяем элемент массива (bucket - корзину) (если нужно - делим по модулю на размер массива, который обычно простое число) и потом смотрим в списке, нет ли такого элемента и действуем соответствующее (добавляем/удаляем/модифицируем).
Если с хешем не угадали, будет перекос, в этом случае иногда меняют либо хеш, либо размер массива (скорее всего увеличивают).