Почему хэш-таблица имеет в среднем постоянное время доступа?

Question

Я не понимаю это объяснение, которое говорит, что если n - это количество элементов в хеш-таблице, а m - общее количество сегментов, то хеш-таблицы имеют в среднем постоянное время доступа, только если n пропорционально тета (n). Почему это должно быть пропорционально?

Answer 1

ну на самом деле м должно быть пропорционально п.В противном случае вы могли бы, например, иметь только 1 сегмент, и это было бы как несортированный набор.

Точнее, если m пропорционально n, то есть m = c * n, то числоэлементы в каждом ведре будут n / m = 1 / c, который является константой.Переход к любому сегменту - это операция O (1) (просто вычисление хеш-кода), а затем поиск по сегменту является постоянным порядком (вы можете просто выполнить линейный поиск по элементам в сегменте, которые будут постоянными).

Таким образом, порядок алгоритма O (1), если m = c * n.

В качестве обратного примера предположим, что у нас есть таблица фиксированного размера size tableSize.Тогда ожидаемое количество элементов в каждом сегменте равно n / tableSize, что является линейной функцией от n.Любой вид поиска в сегменте - в лучшем случае O (log (n)) для дерева (я предполагаю, что вы не вставляете другую таблицу хеш-функции внутри корзины, или у нас будет тот же аргумент над этой таблицей), поэтомув этом случае это не будет O (1).

Answer 2

Строго говоря, сложность времени в среднем случае доступа к хеш-таблице фактически равна Ω (n ^1/3 ).Информация не может двигаться быстрее скорости света, которая является постоянной.Поскольку пространство имеет три измерения, для хранения n битов данных требуется, чтобы некоторые данные располагались на расстоянии порядка n ^1/3 от ЦП.

Подробнее в моем блоге .

Answer 3

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

То, что определяет коэффициент совпадений попаданий, является именно отношением числа-of-items to size-of-hash (т. е. процентная вероятность того, что случайно выбранный слот будет заполнен).

Answer 4

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

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

Answer 5

Вероятность столкновений выше, и, следовательно, вероятность сканирования списка элементов с одинаковым хэш-ключом также выше.