Я реализую дисковый индекс на основе хеша, сопоставляя строки с объектами.Чтобы найти нужный сегмент в хэш-таблице, я использую линейное зондирование и сравниваю хэш входной строки с хэш-таблицей, хранящейся в хэш-таблице.
Основная проблема этого подхода заключается в том, что две разные строки могут легкохэш к тому же значению.Поэтому, чтобы убедиться, что я нашел правильное место, мне нужно не только сравнить хэши, но и найти запись в файле данных и убедиться, что строка, хранящаяся там, равна строке ключа.Если это не так, я продолжаю итерировать хеш-таблицу.
Этот подход работает, но кажется бесполезным, потому что мне приходится выполнять поиск как в хеш-файле, так и в самом файле данных, чтобы проверить, присутствует ли строкаили нет.
Я слышал, что вместо этого вы можете хешировать строку с помощью двух разных хеш-функций и сохранять эти два хеша в хеш-файле.Затем аргумент гласит, что вероятность того, что две разные строки хэшируют одно и то же значение для обеих хеш-функций, астрономически мала.Таким образом, записи в хеш-файле будут выглядеть следующим образом:
h1(s1) h2(s2) ptr1
h1(s2) h2(s2) ptr2
...
И чтобы проверить, нашли ли вы правильное ведро для ключа k, вы должны проверить h1(k) == h1(p) && h2(k) == h2(p).
Мой вопрос: работает ли эта схема, потому что она кажется мне довольно сомнительной.Если это работает, это где-то описано в литературе?