Как хеш-таблицы являются линейными для одинаковых или коллизионных значений?

Question

Я посмотрел на этот ответ Stackru, чтобы лучше понять хэширование, и увидел следующее (относительно того факта, что нам нужно будет получить размер сегмента в постоянном времени):

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

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

Как, например, если я использую линейное зондирование (размер шага 1) в хеш-таблице, и у меня есть разные ключи (не конфликтующие, все хеш-значения уникальным значениям), сопоставляемые с нечетными слотами индекса 1,3,5,7,9..... Затем я хочу вставить много ключей, все хэши которых равны 2, поэтому я заполняю все свои четные индексные области этими ключами. Если бы я хотел узнать, сколько ключей хэширует до 2, не нужно ли мне просматривать всю хеш-таблицу? Но я не просто перебираю элементы, которые хэшируются с одинаковым или совпадающим значением, поскольку нечетные интервалы индекса не сталкиваются.

Answer 1

Хеш-таблица концептуально похожа на массив (таблицу) связанных списков (ведро в таблице). Разница заключается в том, как вы управляете и обращаетесь к этому массиву: используя функцию для генерации числа, которое используется для вычисления индекса массива.

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

Однако вы пропускаете важное введение в этом параграфе:

Если вы используете что-то вроде линейного зондирования или двойного хеширования, то обнаружение всех элементов, хэшированных до одного и того же значения, означает, что вам нужно хэшировать значение, а затем пройтись по "цепочке" непустых элементов в вашей таблице, чтобы узнать, сколько из них хэшируется до того же значения. Это не является линейным по количеству элементов, которые хэшируются до одного и того же значения - это линейно по количеству элементов, которые хэшируются к одному и тому же или сталкивающемуся значению.

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

Это презентационное видео CppCon представляет собой хорошее введение и углубленный анализ хеш-таблиц.