Алгоритм URL Shortener
Я недавно купил себе домен для сокращения личных URL. И я создал функцию для генерации буквенно-цифровых строк из 4 символов в качестве ссылки.
НО
Как проверить, используются ли они уже или нет? Я не могу проверить каждый URL, если он существует в базе данных, или это просто так, и я должен это сделать? Если да, то что, если у меня создано 13 000 000 URL (из 14 776,336). Нужно ли продолжать генерировать строки, пока я не найду ту, которой еще нет в БД?
Это просто не выглядит правильным способом сделать это, кто-нибудь, кто может дать мне совет?
3 ответа
Я думаю о том, как эффективно и быстрее использовать память. Эта проблема может быть решена без использования базы данных вообще. Идея состоит в том, что вместо хранения используемых URL-адресов в базе данных, вы можете хранить их в памяти. А поскольку их хранение в памяти может занять много памяти, мы будем использовать набор битов (массив битов), и для каждого URL мы будем использовать только один бит.
- Для каждой случайной строки, которую вы генерируете, создайте хеш-код для этого, который лежит ч / б 0 и максимальное число K.
- Создать битовый набор (в основном битовый массив). Всякий раз, когда вы используете какой-либо URL, установите соответствующий бит хеш-кода в бит установлен в 1.
- Всякий раз, когда вы генерируете новый URL, посмотрите, установлен ли его бит хеш-кода. Если да, то откажитесь от этого URL и создайте новый. Повторите процесс, пока не получите один неиспользованный.
Таким образом вы навсегда избегаете БД, ваши поиски выполняются очень быстро и занимают наименьшее количество памяти.
Я заимствовал идею из этого места
Один алгоритм состоит в том, чтобы несколько раз попытаться найти свободный URL из N символов, если все еще не найдено, увеличить N. Начните с N=4.
Компромиссное решение - создать случайный идентификатор, и, если он уже есть в базе данных, найти первый пустой идентификатор, который больше его. (Оборачиваемся, если вы не можете найти пустое место в диапазоне выше.)
Если вы не хотите, чтобы идентификаторы были неосуществимыми (вероятно, нет, если вы используете только 4 символа), этот подход работает отлично и быстро.