Хеширование URL для генерации идентификатора

Question

Я хочу создать идентификатор объекта, хэшируя его относительный URL (например, /path/some/optional/part/last_part?maybe=query&some=params).Я не хочу использовать URL в качестве идентификатора, потому что он может быть очень длинным и может содержать специальные символы.Есть 4 решения, которые я могу себе представить:

1. Заменить все специальные символы на некоторые специальные символы. Pro : легко, быстро. Con : все еще длинные идентификаторы
2. Использовать криптографический хеш. Pro : легкие, почти нулевые столкновения. Con : медленно?.
3. Использовать некриптографический хеш. Pro : быстро. Con : коллизии?
4. Генерация UUID и запрос по полю url вместо id и / или сохранение url-> uuid в некотором хранилище значений ключей. Pro : ноль столкновений. Con : медленно, может быть трудно реализовать правильно.

Мне нравится # 3, но есть ли быстрый хеш без коллизий?Если нет, тогда я, вероятно, должен придерживаться # 2 (с md5 или sha1).Что бы вы выбрали и почему?

РЕДАКТИРОВАТЬ: читать "нет столкновений" как "незначительно низкая вероятность столкновений".

Answer 1

Зависит от того, что вы считаете «незначительно низким», и от того, сколько элементов вы хэшируете.

Если вы используете 32-битный хэш-код, то у вас есть 50% -ная вероятность возникновения коллизиитолько после 70000 или около того предметов.С 64-битным хеш-кодом вероятность столкновения составляет около 50% после примерно 4 миллиардов элементов.

См. Мою запись в блоге https://blog.mischel.com/2017/11/02/birthdays-random-numbers-and-hash-keys/,, а также День рождения .

С 64-битным хеш-кодом у вас есть 1% шанс создать дубликат после 610 миллионов элементов.Является ли эта вероятность "незначительно низкой" достаточной для вас?

Достойная 64-битная хеш-функция равна https://en.wikipedia.org/wiki/Jenkins_hash_function. Обратите внимание, что она не криптографически безопасна, но, похоже, она будет работать для вашего приложения,и вычисление будет намного быстрее, чем MD5 или SHA1.

И если вы хотите превратить его в идентификатор, просто base64 закодируйте .Это будет 12 символов в длину.