Как улучшить производительность хеш-таблицы с 1 миллионом элементов и 997 корзинами?

Question

Это вопрос интервью.

Предположим, что в таблице 1 миллион элементов и 997 блоков неупорядоченных списков.Далее предположим, что хеш-функция распределяет ключи с равной вероятностью (т. Е. Каждое ведро имеет 1000 элементов).

В какое наихудшее время найти элемент, которого нет в таблице?Чтобы найти тот, который находится в таблице?Как вы можете улучшить это?

Мое решение: Наихудшее время нахождения элемента, которого нет в таблице и в таблице - O (1000)1000 - длина несортированного списка.

Улучшите его: (0) просто, увеличьте количество сегментов> 1 миллиона.(1) каждый сегмент содержит вторую хеш-таблицу, в которой используется другая хеш-функция для вычисления значения хеш-функции для второй таблицы.это будет O (1) (2) каждое ведро содержит двоичное дерево поиска.Это будет O (LG N).

, если можно сделать компромисс между пространством и временем.Держите их обоих в разумных пределах.

Есть идеи получше?Спасибо !

Answer 1

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

Answer 2

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

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

Если N - количество элементов, а M - количество сегментов, тосложность возрастает как O [log (N / M)], в случае равного распределения.

Answer 3

Если вы не можете использовать другую структуру данных или таблицу большего размера, есть опции:

Если активный набор элементов ближе к 1000, чем 1M, вы можете улучшить среднее время успешного поиска, переместив каждый найденный элемент в начало списка. Это позволит быстро найти его при повторном использовании.

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

Answer 4

Предположим, что в таблице 1 миллион элементов и 997 блоков неупорядоченных списков.Далее предположим, что хеш-функция распределяет ключи с равной вероятностью (т. Е. Каждое ведро имеет 1000 элементов).

Это не совсем суммируется, но давайте поработаем с этим ....

Какое наихудшее время для поиска элемента, которого нет вТаблица?Чтобы найти тот, который находится в таблице?Как вы можете улучшить это?

Худший (и лучший = только) случай для пропущенных элементов состоит в том, что вы хешируете в корзину, затем проходите проверку всех элементов в этом конкретном списке (то есть 1000), затемпотерпеть поражение.Если им нужна нотация big-O, по определению описывающая, как производительность варьируется в зависимости от количества элементов N, поэтому мы должны сделать предположение о том, как # сегменты также меняются в зависимости от N: я предполагаю, что 997 сегментов - это фиксированное количествои не будет увеличиваться, если количество элементов увеличивается.Таким образом, число сравнений равно N / 997, которое, будучи линейным коэффициентом, по-прежнему равно O (N).

Мое решение: время наихудшего случая нахождения элемента, отсутствующего в таблице и в таблицевсе O (1000).1000 - длина несортированного списка.

Нет - вы думаете о количестве сравнений - но нотация big-O касается масштабируемости.

Улучшите это: (0) просто, увеличьте номера сегментов> 1 миллион(1) каждый сегмент содержит вторую хеш-таблицу, в которой используется другая хеш-функция для вычисления значения хеш-функции для второй таблицы.это будет O (1) (2) каждое ведро содержит двоичное дерево поиска.Это будет O (LG N).

, если можно сделать компромисс между пространством и временем.Держите их обоих в разумных пределах.

Ну да - среднее число коллизий относится к количеству записей и интервалов.Если вы хотите очень мало коллизий, у вас будет более 1 миллиона записей в таблице, но это приводит к расточительному использованию памяти, хотя для больших объектов вы можете иметь индекс или указатель на фактический объект.Альтернативой является поиск более быстрых механизмов обработки столкновений, таких как попытка серии смещений из сегмента хэширования (используя%, чтобы отобразить смещения обратно в размер таблицы), а не обращение к некоторой куче с использованием связанных списков.Перефразирование является еще одной альтернативой, учитывая более низкие частоты повторных столкновений, но, как правило, требующие больше ресурсов ЦП, и наличие произвольно длинного списка хороших алгоритмов хеширования проблематично.

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