Существуют ли специфичные для URL методы hashCode? - PullRequest
Новая
       14

Существуют ли специфичные для URL методы hashCode?

3 голосов
/ 31 июля 2011

Есть ли способ для эффективной генерации идентификатора URL из памяти?

На данный момент у меня есть кеш аля Set<String> для моих URL, и я могу легко проверить, был ли URL уже разрешен моим сканером или нет. Теперь это требует много памяти, и я заменил ее на Set<Long> и использовал хэш-код URL. Проблема сейчас в том, что даже для 40k URL-адресов существует 10 конфликтов. Усовершенствованный метод, использующий long вместо int hashCode, немного улучшает его до 6 конфликтов, но особенно короткие URL выглядят очень похоже на возникшие проблемы:

5852015146777169869 http://twitpic.com/5xuwuk против http://twitpic.com/5xuw7m 5852015146777169869

Итак, я остановился на следующем методе двойного хэширования, специфичном для URL-адреса, который не дает конфликтов для URL-адресов 2,5 млн., Что мне подходит: 

public static long urlHashing(String str) {
    if (str.length() < 2)
        return str.hashCode();

    long val = longHashCode(str, 31, false);
    if (str.length() > 3)
        // use the end of the string because those short URLs
        // are often identical at the beginning
        return 43 * val + longHashCode(str.substring(str.length() / 2), 37, true);
    return val;
}

public static long longHashCode(String str, int num, boolean up) {
    int len = str.length();
    if (len == 0)
        return 0;

    long h = 0;
    // copying to a temp arry is a only a tiny bit slower in our case.
    // so this here is ~2ms faster for 40k urls
    if (up)
        for (int i = 0; i < len;) {
            h = num * h + str.charAt(i++);
        }
    else
        for (int i = len - 1; i >= 0;) {
            h = num * h + str.charAt(i--);
        }

    return h;
}

НО Теперь я задался вопросом: есть ли какие-то теории или (google;)) статьи об алгоритмах хеширования, специфичных для URL? Или просто: могу ли я дополнительно уменьшить конфликты для URL-адресов или вы видите какие-либо проблемы или улучшения для моего текущего решения?

Обновление:

  • Другой подход заключается в разделении URL-адреса по протоколу, адресу и файлу, как это делается в методе new URL(str).hashCode() (который нельзя использовать напрямую, поскольку он очень медленный -> он разрешает URL-адрес на лету: /)
  • См. squid-cache.org или объяснение CacheDigest

Ответы [ 2 ]

3 голосов
/ 31 июля 2011

Если вы хотите что-то, что работает постоянно, а не только большую часть времени, короткие хэши не будут сокращать это.Как вы заметили, при любой длине короче, чем около 128 бит, даже идеальный хеш будет иметь значительную частоту столкновений.У вас есть проблема масштабирования, и все, что вы делаете, используя хэш-коды, это уменьшаете постоянный коэффициент - это все равно O (n).

Похоже, что у ваших строк много общих префиксов,хотя - вы рассматривали возможность использования trie для их хранения?

2 голосов
/ 31 июля 2011

Вам, вероятно, следует использовать MD5-хэш .Частота столкновений должна быть намного меньше.

...