Можно использовать только 64-битный хэш sha1 в качестве идентификатора?

Question

1) В целях действительно низкого коллизирования хешей, могу ли я избежать использования только половины из 128 битов sha1 вместо того, чтобы иметь дело с самим sha1? Я понимаю, что это не подходит для криптографических хэшей, но мне просто нужны хэши для ключей хеш-таблиц.

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

3) Я новичок sql. Это хорошая идея использовать 64-битные хэши в качестве идентификаторов в SQL? Будут ли 64-битные идентификаторы вызывать проблемы с производительностью в sqlite или postgres? Мне нужно будет координировать данные по нескольким базам данных (включая индекс Lucene), поэтому я решил, что мне следует иметь дело с хешами непосредственно в таблицах, а не с автоматически увеличивающимися идентификаторами (которые будут иметь смысл только в одном дБ, а не во всех хранилищах данных). Я считаю, что 64-битный код - хороший компромисс: достаточно большой для маловероятных столкновений, но экономит место (и время поиска?).

4) А как насчет CRC-64? Создает ли это случайное распределение?

Answer 1

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

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

Но разве у вашего SQL нет какого-то GUID? И если это так, почему бы не использовать его?

Answer 2

Для хорошего сравнения длин хешей, посмотрите на http://en.wikipedia.org/wiki/List_of_hash_functions

Кроме того, просто примечание: SHA-1 составляет 160 бит, а не 128.

Answer 3

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

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

Answer 4

С 64-битными хэшами вероятность столкновения составляет 1% с 6,1 × 10 ⁸ записями. (Другие комбинации см. На странице Википедии, посвященной проблеме дня рождения .) Вы можете отбрасывать первые 64-битные или последние каждого второго бита, это не имеет никакого значения для свойств хеш.

Answer 5

Если время вычислений не имеет значения, почему бы не использовать целые 128 бит? Есть ли реальная причина выбрать 64 бита помимо возможных проблем с памятью? (и тогда дополнительные 8 байт не убьют вас с таким дешевым хранилищем)

64 бит против 128 бит не вызовет проблем со скоростью в SQLite, я не уверен насчет mySQL.