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

Question

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

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

Для меня время поиска O (1), но я думаю, что это не хороший ответ, может кто-нибудь помочь?

Answer 1

Открытая адресация - это метод разрешения столкновений в хэш-таблицах.

Open адресация имеет три хорошо известные методов зондирующие:

• Linear зондирующего
• Квадратичного зондирование
• двойного хеширования

Без потери общности можно считать с помощью любого метода зондирования.

Предположим, что у вас есть хеш-функция h и элементы E = [e1, e2, ..., en]. Предположим теперь, что h не слишком хорош, поэтому для каждого элемента в E есть h(ex) = c, где c - некоторая константа. Теперь, если вы добавите элементы из E по порядку, а затем попросите n-й элемент, тогда время доступа не будет O (1), а O (n) для каждого вызова.

Answer 2

Время поиска в Open Addressing hasthable независимых по числу ключей (N). Итак, в обозначении big-O это O (1). Однако, это зависит от "отношение населения" в Hashtable, :

Ожидаемые цифры попытка:

1. Успешный поиск: (1/а) * Ln (1/(1 - а));
2. Неудачный поиск: 1/(1 - a);

Ссылка:

Кормена & аль Введение в алгоритмы, 12.5-12.7