Создайте идеальный хэш для миллионов элементов - результат должен быть «существует или нет»

Question

Кто-нибудь знает хорошую библиотеку (windows), которая позволит мне создать статический (не во время выполнения) идеальный хэш для миллионов элементов (вероятно, около 10 м)?

У меня по существу есть миллионы наборовстрок, и я хочу знать с минимальной O (1), есть ли строка в моем наборе или нет - это все.Мне не нужно, чтобы он действительно искал строку - за ней нет никакого значения (кроме существования).

Answer 1

Попробуйте:

• Боба Дженкинса идеально .
• CMPH
• Gperf

perfect и gperf создают таблицы в виде кода на C, который должен нормально работать в Windows. Я не знаю, что вывод CMPH.

CMPH комментирует:

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

Если это правильно, то в вашем случае с ключом-миллионником вы, вероятно, предпочтете CMPH вместо gperf. Я не знаю, как они сравниваются с идеальным Дженкинс. Это должно быть достаточно просто, чтобы попробовать все три и сравнить их друг с другом.

Answer 2

Фильтр Блума будет делать то, что вы хотите, я бы посмотрел вокруг библиотек, в которых они есть, или вы можете попытаться написать один самостоятельно.