Цепочка — это метод, используемый для предотвращения коллизий в хеш-таблицах.
коллизия возникает, когда два ключа хешируются к одному и тому же индекс в хеш-таблице. Коллизии представляют собой проблему, потому что каждый слот в хеш-таблице должен хранить один элемент.
Техника объединения
В подходе цепочки хеш-таблица представляет собой массив связанных списков, т. е. каждый индекс имеет свой собственный связанный список.
Все пары ключ-значение, сопоставленные с одним и тем же индексом, будут сохранены в связанном списке этого индекса.
Преимущества цепочки
-
Посредством цепочки вставка в хеш-таблицу всегда встречается в O (1) , поскольку связанные списки позволяют вставку в постоянное время.
-
Теоретически связанная хеш-таблица может бесконечно увеличиваться до тех пор, пока есть достаточно места.
-
Хеш-таблица, которая используется Размер цепочки es никогда не нужно изменять.
