Разработка хорошей хэш-функции для сокращения URL-адресов заданной длины в PHP

Question

Я работаю над сокращением URL. Входные данные являются URL-адресом, а выходные данные должны быть 4-символьной строкой (буквенно-цифровой, с учетом регистра).

Я рассчитал, что если я использую 4 символа с регистрозависимым буквенно-цифровым пространством клавиш, я потенциально смогу хранить 64 ^ 4 (16777216) URL-адресов до тех пор, пока у меня не будет свободного места.

Я также не хочу, чтобы средство сокращения URL генерировало короткие URL, содержащие оскорбительные слова из четырех букв. Было бы прискорбно, если бы кто-то сделал короткий URL-адрес domain.com/f**k. Вы получаете картину ...

Есть какие-нибудь идеи о том, как это сделать? Я чувствую, что где-то в процессе буду использовать base64_encode.

Answer 1

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

Таким образом, вместо алгоритма хеширования, они просто в порядке. Первые несколько будут выглядеть так:

id   | url
-------------------------
0000 | http://google.com
0001 | http://yahoo.com
0002 | http://example.com
...
000a | http://mail.google.com
000b | http://adobe.com
...
000A | http://microsof.com
...
0010 | http://w3.org
...
00a0 | http://youtube.com
...
00A0 | http://stackoverflow.com

и т. Д.

Вот подсказка о том, как будет работать функция: http://us3.php.net/manual/en/function.ord.php

Кстати, моя математика может быть неправильной, но я думаю, что это (10 + 26 + 26) ^ 4 = 14776336

Редактировать : Просто для удовольствия и задачи я написал функцию инкремента. Когда достигается максимум, он возвращает false, поэтому просто сравните его с false (с ===) при его использовании.

http://pastebin.com/957KPn4p

Answer 2

Это смутно напомнило мне об этом Как мне создать уникальные идентификаторы, такие как YouTube? .Вы просто должны проверить (в более ограниченном пространстве) возможность столкновения.