Как быстро хешировать URL

Question

У меня уникальная ситуация, когда мне нужно создавать хэши на лету. Вот моя ситуация. Этот вопрос относится к здесь . Мне нужно хранить много URL в базе данных, которые должны быть проиндексированы. URL может быть длиной более 2000 символов. База данных жалуется, что не может быть проиндексирована строка длиной более 900 байт. Мое решение заключается в хешировании URL с использованием MD5 или SHA256. Я не уверен, какой алгоритм хеширования использовать. Вот мои требования

• Наименьшая длина символа с минимальным столкновением
• Быть очень быстрым . Я буду хэшировать ссылку на каждый запрос страницы
• Столкновения необходимо свести к минимуму, поскольку в базе данных могут быть миллионы URL

Я не беспокоюсь о безопасности. Я беспокоюсь о длине персонажа, скорости и столкновениях. Кто-нибудь знает хороший алгоритм для этого?

Answer 1

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

Я бы настоятельно не рекомендовал использовать String.GetHashCode(), поскольку реализация неизвестнаи MSDN говорит, что это может варьироваться между различными версиями платформы.Даже результаты между версиями x86 и x64 могут отличаться.Таким образом, у вас возникнут проблемы при попытке доступа к той же базе данных с использованием более новой (или другой) версии .NET Framework.

Я нашел алгоритм для реализации Java hashCode в Википедии ( здесь ), это кажется довольно простым для реализации.Даже простая реализация будет быстрее, чем реализация MD5 или SHA IMO.Вы также можете использовать long значения, которые уменьшают вероятность коллизий.

Здесь также приводится краткий анализ реализации .NET GetHashCode здесь (не сам алгоритм, а некоторая реализациядетали), вы также можете использовать это, я думаю.(или попробуйте реализовать версию Java аналогичным образом ...)

Answer 2

Возможно, вы захотите взглянуть на следующий проект:

CMPH - C Минимальная идеальная библиотека хеширования

И посмотрите следующие горячие темы для идеальных хэшей:

Самые горячие ответы 'perfect-hash' - Переполнение стека

Вы также можете рассмотреть возможность использования полнотекстового индекса в SQL вместо хеширования:

СОЗДАТЬ ИНДЕКС ПОЛНОГО ТЕКСТА (Transact-SQL)

Answer 3

Отраженный исходный код функции GetHashCode в .net 4.0

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

Было O (n) простых операций (+, <<, ^) и одно умножение. Так что это очень быстро. </p>

Я тестировал эту функцию на 3 млн. БД содержит строки длиной до 256 символов, и около 97% строк не имеет столкновения. (Максимум 5 строк имеют одинаковый хэш)

Answer 4

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

Answer 5

быстрый:

URLString.GetHashCode().ToString("x")

Answer 6

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

Любая из двух названных вами функций хеширования должна быть достаточно быстрой, чтобы вы не заметили большой разницы между ними. Если бы этот сайт не требовал сверхвысокой производительности, я бы не стал сильно о них беспокоиться. Я лично, наверное, пошел бы на MD5. Это может быть отформатировано как строка как шестнадцатеричный в 64 символа или как строка из 64 основных в 44 символов.

Причина, по которой я бы выбрал MD5, заключается в том, что вы вряд ли столкнетесь с коллизиями, и даже если вы это сделаете, вы можете структурировать свои запросы с помощью "где urlhash = @hash and url = @url". Механизм базы данных должен определить, что один проиндексирован, а другой нет, и использовать эту информацию для разумного поиска.

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

Answer 7

Используйте класс System.Security.Cryptography.SHA1Cng, я бы предложил.Это 160 бит или 20 байт, так что это должно быть достаточно мало.Если вам нужно, чтобы это была строка, для нее потребуется всего 40 символов, поэтому она должна хорошо соответствовать вашим потребностям.Он также должен быть достаточно быстрым, и, насколько я знаю, столкновений пока не обнаружено.