Как мне реализовать функцию хеширования строк для этих требований?

Question

Хорошо, мне нужна функция хеширования для удовлетворения следующих требований. Идея состоит в том, чтобы иметь возможность связывать вместе каталоги, которые являются частью одной логической структуры, но хранятся в разных физических областях файловой системы.

Мне нужно реализовать его на Java, он должен быть согласованным между сеансами исполнения и может возвращать long.

Я буду хэшировать имена каталогов / строки. Это должно работать так, чтобы "somefolder1" и "somefolder2" возвращали разные хэши, как и "JJK" и "JJL". Я также хотел бы получить некоторое представление о том, когда могут возникнуть столкновения.

Есть предложения?

Спасибо

Answer 1

Ну, почти все хеш-функции имеют свойство, заключающееся в том, что небольшие изменения во входных данных приводят к значительным изменениям в выходных данных, что означает, что «somefolder1» и «somefolder2» всегда будут давать различный хеш.

Что касается столкновений, просто посмотрите, насколько велик выход хеша. Собственный Java hashcode() возвращает int, поэтому вы можете ожидать столкновения чаще, чем с MD5 или SHA-1 , например, которые дают 128 и 160 бит соответственно.

Вы не должны пытаться создавать такую ​​функцию с нуля.

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

Answer 2

Вы не описали, при каких обстоятельствах разные строки должны возвращать такой же хеш.

В общем, я бы подошел к разработке функции хеширования, сначала реализовав функцию равенства. Это должно показать вам, какие биты данных вам нужно включить в хеш, а какие следует отбросить. Если равенство между двумя разными битами данных является сложным (например, нечувствительность к регистру), то, надеюсь, для этого конкретного сравнения будет соответствующая хеш-функция.

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

Answer 3

При использовании равномерно случайной хэш-функции с М возможными значениями вероятность столкновения, произошедшего после N хешей, составляет 50% при

N = .5 + SQRT(.25 - 2 * M * ln(.5))

Посмотрите на проблему дня рождения для дальнейшего анализа.

Вы можете избежать коллизий, если заранее знаете все свои ключи, используя совершенное хеширование .

Answer 4

Хеш-код Java String даст вам int, если вы хотите long, вы можете взять наименее значимые 64 бита суммы MD5 для строки.

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