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

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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