Поиск по хеш-таблице - с идеальным хешем, в C
У меня есть приложение на языке C, где мне нужно искать таблицы.
Записи являются строками. Все они известны в начале выполнения. Таблица инициализируется один раз, а затем просматривается много раз. Таблица может измениться, но это в основном так, как будто приложение запускается заново. Я думаю, это означает, что я могу использовать идеальный хеш? Можно потратить некоторое время на инициализацию хеш-таблицы, как это происходит только один раз.
Будет от 3 до 100 000 записей, каждая из которых уникальна, и я предполагаю, что в 80% случаев будет менее 100 записей. В таких случаях простой наивный поиск достаточно быстр. (== никто не жалуется)
Однако в случаях, когда существует более 10 000 записей, скорость поиска наивного подхода неприемлема. Каков хороший подход для обеспечения хорошей производительности поиска строк на основе хеш-таблиц? Предположим, у меня нет сторонней коммерческой библиотеки, такой как Boost/etc. Какой алгоритм хеширования я должен использовать? как мне решить?
3 ответа
Генерация идеального хэша - не простая проблема. Есть библиотеки, посвященные этой задаче. В этом случае наиболее популярным является, вероятно, CMPH. Я не использовал это, хотя так не могу помочь кроме этого. gperf - это еще один инструмент, но он требует, чтобы строки были известны во время компиляции (вы можете обойти это, скомпилировав.so и загрузив, но с некоторым перебором).
Но, честно говоря, я бы, по крайней мере, сначала попытался выполнить бинарный поиск. Просто отсортируйте массив, используя qsort, затем искать с bsearch (или сверните свое собственное). Оба эти являются частью stdlib.h с C89.
Если наивный (я предполагаю, что вы имеете в виду линейный) подход подходит для 100 записей (таким образом, в среднем выполняется 50 сравнений), то двоичного поиска будет более чем достаточно для 100 000 записей (для этого требуется не более 17 сравнений).
Так что я бы не стал беспокоиться о хешах, а просто прибегнул к сортировке таблицы строк при запуске (например, используя qsort) и позже, используя бинарный поиск (например, используя bsearch) искать записи.
Если известен (максимальный) размер таблицы, очень легко реализовать простую хеш-таблицу с цепочкой. Размер накладных расходов составляет всего два дюйма на элемент. При разумной хэш-функции в среднем требуется только 1,5 зонда на поиск, это для таблицы, загруженной на 100%.
Создание идеального хэша возможно только в том случае, если ваши данные не изменяются. Как только он изменится, вам придется пересчитать и перефразировать, что намного дороже, чем сделать несколько дополнительных сравнений.