Хеширование методом цепочек

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

0

На процесс поиска и удаления не повлияет, а добавление станет более медленным. Это в случае если реализация цепочек будет классической, то есть односвязным списком.

Но если пофантазировать и реализовать цепочки в виде блоков динамической памяти (которые по ошибке традиции называют динамическими массивами), то во-первых память будет выделяться единовременно (это быстрее), а во-вторых можно использовать бинарный поиск. Но добавление и удаление будут замедлены копированием части элементов. Это не дорого по сравнению с операцией выделения памяти на каждый новый элемент у списка, особенно учитывая, что цепочки не велики. При угрозе переполнения можно произвести рехешинг. Это не будет больно, если хеш будет размазывать данные более-менее равномерно и будет очень плохо, если нет. И всё же игра вряд ли стоит свеч. Выигрыш от логарифмического времени поиска на короткой цепочке не будет заметен по сравнению с последовательным прохождением, но появятся затраты при копировании.
Однако есть и хорошая новость. Поскольку выделение памяти для цепочки в этом случае делается единовременно, то есть хорошие шансы, что все элементы будут лежать в пределах кэша L3. Для очень большой структуры построенной на списках, такой уверенности нет, если не использован какой-то специальный аллокатор. Последние фантазии рассуждения вряд ли предполагаются данным вопросом.

1