Поиск по хеш-таблице - с идеальным хешем, в C

Question

У меня есть приложение на языке C, где мне нужно выполнять поиск по таблицам.

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

Будет от 3 до 100 000 записей, каждая из которых уникальна, и я предполагаю, что в 80% случаев будет менее 100 записей.В таких случаях простой наивный поиск достаточно быстр.(== никто не жалуется)

Однако в случаях, когда существует более 10 000 записей, скорость поиска наивного подхода неприемлема.Каков хороший подход для обеспечения хорошей производительности поиска строк на основе хеш-таблиц?Предположим, у меня нет сторонней коммерческой библиотеки, такой как Boost / etc.Какой алгоритм хеширования я должен использовать?как мне решить?

Answer 1

Если наивный (я полагаю, вы имеете в виду линейный) подход подходит для 100 записей (таким образом, в среднем выполняется 50 сравнений), то двоичного поиска будет более чем достаточно для 100 000 записей (для этого требуется не более 17 сравнений).

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

Answer 2

Создание идеального хэша не простая проблема.Есть библиотеки, посвященные этой задаче.В этом случае наиболее популярным является, вероятно, CMPH .Я не использовал это, хотя так не могу помочь кроме этого. gperf - это еще один инструмент, но он требует, чтобы строки были известны во время компиляции (вы могли бы обойти это, скомпилировав .so и загрузив, но с некоторым перебором).

Но, честно говоряЯ бы хотя бы попытался сначала выполнить бинарный поиск.Просто отсортируйте массив с помощью qsort, затем выполните поиск с помощью bsearch (или сверните свой собственный).Оба они являются частью stdlib.h, начиная с C89.

Answer 3

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

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