Анализ алгоритма - поиск хеша в O (1) со списками столкновений

Question

Я читаю учебник, и он говорит о реализации хэш-списка.Что касается конкретно хеш-таблицы, то в учебнике написано:

Метод сцепления работает достаточно хорошо, если элементы равномерно распределены по позициям массива, что называется равномерным хешированием.Например, если у нас 300 сотрудников и размер массива 100, а если на одну должность приходится около 3 сотрудников, отдайте или возьмите сотрудника, то у нас все еще есть функция поиска, которая работает за O (1) времени, так как не болеепотребуется 3 или 4 сравнения, чтобы найти подходящего сотрудника.

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

Итак, мой вопрос:

В этом параграфе говорится, что, учитывая наш алгоритм хеширования, мы можем искать элемент за O (1) время.Это меня удивляет, потому что чем больше становится ваш набор данных, тем больше у вас будет коллизий и тем больше будут ваши списки коллизий.Итак, списки столкновений будут медленно расти с (n = # сотрудников), но они будут расти.

Я бы подумал, что это заставило алгоритм действовать за O (n) время.

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

Answer 1

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

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

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

Answer 2

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

Это гарантирует, что «достаточно» ключей дляO (1) средняя производительность.

Answer 3

единица работы - это один элемент. Поиск одного элемента в хэш-таблице из N элементов в слотах M является процессом O (1).

создание хеш-таблицы - это, конечно (как минимум) процесс O (N). Поиск всех элементов также (как минимум) является процессом O (N).

Та же логика применима к двоичному поиску или деревьям: O (some_function_of_N) - это объем работы, необходимый для поиска одного элемента (с учетом массива или дерева размера N).