Я читаю, чем можно избежать наихудшей сложности, если мы будем избегать коллизий.
Это верно - сложность наихудшего случая возникает, когда все значения ha sh для элементов, хранящихся в таблице ha sh, отображаются в одной и той же корзине и сталкиваются в ней.
Как я понимаю, коллизия - это когда функция ha sh возвращает одно и то же значение в случае разных ключей.
В конечном итоге значение отображается с помощью функции ha sh в ведро в таблица ha sh. Тем не менее, общая концептуальная функция ha sh обычно реализуется как функция ha sh, производящая значение в огромном числовом диапазоне (например, 32-битное ha sh между 0 и 2 ^ 32-1 или 64-битный ha sh между 0 и 2 ^ 64-1), затем сопоставьте это значение с определенным сегментом c на основе текущего количества сегментов таблицы ha sh с помощью оператора % . Итак, предположим, что ваша таблица ha sh имеет 137 ведер, вы можете сгенерировать значение ha sh 139, затем сказать 139% 137 == 2 и использовать третье ([2] в массиве корзин). Этот двухэтапный подход позволяет легко использовать одну и ту же функцию ha sh (создание 32-битных или 64-битных хэшей) независимо от размера таблицы. Если вместо этого вы создадите функцию ha sh, которая напрямую генерирует числа от 0 до 136, она не будет работать для немного меньшего или большего количества ведер.
Возвращаясь к вашему вопросу ...
Как я понимаю, коллизия - это когда функция ha sh возвращает одно и то же значение в случае разных ключей.
... для "32- или 64-битных" ha sh, за которым следует подход% ", который я описал выше, существует два различных типа коллизий: 32- или 64-разрядная функция ha sh сама может выдавать точно такое же 32- или 64-разрядное значение для хешируются различные значения, или они могут давать разные значения, которые - после операции% - тем не менее сопоставляются с одним и тем же сегментом в таблице ha sh.
Как это влияет на Ha sh Сложность таблиц в операциях CRUD?
Ha sh Таблицы работают за счет вероятностного распределения значений по сегментам. Когда много значений сталкиваются в одной и той же корзине, должен использоваться вторичный механизм поиска для обработки всех конфликтующих значений (и, возможно, других смешанных значений, если вы используете открытую адресацию, чтобы попробовать последовательность сегментов в таблице ha sh вместо того, чтобы навешивать связанный список или двоичное дерево сталкивающихся элементов на каждую корзину). Таким образом, чем хуже частота столкновений, тем дальше от идеализированной сложности O (1) вы получаете, хотя вы действительно начинаете значительно влиять на сложность big-O, только если у вас есть функция особенно bad ha sh , в свете набора сохраняемых значений.