Блог

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

Каким будет асимптотическое время выполнения:

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

(б) Поиск ключа, которого нет в таблице.

Я понимаю, что вставка ключа в хеш-таблицу равна O (1), поэтому для вставки таких n записей будет O (n). Для части b поиск ключа, отсутствующего в таблице, считается наихудшим случаем, поэтому асимптотическое время выполнения поиска будет O (n), поскольку для этого потребуется выполнить поиск по всем n значениям в таблице.

Вы правы насчет a) — это O (n), где n — количество новых вставляемых ключей, поскольку каждый равен O (1) по отношению к ранее существовавшему количеству ключей.

Для b) — вы ошибаетесь — это O (1) . Поиск ключа, которого нет в таблице, требует только исчерпывающего поиска в сегменте, в который хэшируется ключ, и ожидаемая длина этого сегмента примерно определяется коэффициентом загрузки: отношением ключей к сегментам. Большинство хеш-таблиц предназначены для поддержания коэффициента загрузки в определенном диапазоне, изменяя размер хеш-таблицы по мере добавления новых ключей.

Например, стандарт C определяет значение по умолчанию max_load_factor 1.0, поэтому, если вы вставляете, скажем, 129-й элемент в таблицу со 128 сегментами, он изменит размер всего этого, чтобы иметь, возможно, 256 сегментов (MS Visual C использует количество сегментов степени двойки для быстрого побитового маскирования хэш-значений длясегменты, GCC использует простые числа для уменьшения коллизий). В любом случае, когда коэффициент загрузки сохраняется в таком диапазоне — скажем, от ~ 0,5 до 1,0 — у вас вряд ли будет больше пары элементов в корзине, вы будете искать ключ, которого на самом деле нет в таблице.

Помимо отдельной цепочки, существует другой способ хранения данных в хеш-таблицах, называемый закрытым хешированием или открытой адресацией, где — в случае коллизии — вы используете другие сегменты. Существует много способов выбора этих сегментов: линейное зондирование означает, что вы просматриваете последовательные сегменты, квадратичное зондирование означает, что вы пытаетесь, например 1, 4, 9, 16 из хэшированного — в ведро. При таких подходах, когда коэффициент загрузки приближается к 1,0 или если хэш-функция низкого качества, вы, скорее всего, приблизитесь к наихудшему показателю производительности O (N), но нет смысла использовать такую хэш-таблицу, если вы не собираетесь это предотвращать и иметь более низкий коэффициент загрузкиили лучшая хеш-функция, которая сохранит производительность на уровне амортизированного O (1).