java - 是否有特定于 URL 的 hashCode 方法？

Question

有没有一种方法可以高效地“生成”URL 的内存？

目前我有一个缓存ala Set<String>对于我的 URL，我可以很容易地检查 URL 是否已经被我的抓取工具解析。现在这需要大量内存，我将其替换为 Set<Long>并使用了 URL 的 hashCode。现在的问题是即使对于 40k 的 URL 也有 10 个冲突。使用 long 而不是 int hashCode 的改进方法将其改进为 6 个冲突，但特别是短 url 在开始时看起来非常相似会产生问题:

5852015146777169869 http://twitpic.com/5xuwuk与 http://twitpic.com/5xuw7m 5852015146777169869

所以我最终采用了以下特定于 URL 的双哈希方法，该方法对 2.5mio URL 没有冲突，这对我来说很好:

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;
}

但是现在我想知道:是否有一些关于 URL 特定哈希算法的理论或 (google ;)) 论文？或者简单地说:我可以进一步减少 URL 的冲突吗？或者您认为我当前的解决方案有任何问题或改进吗？

更新:

• 另一种方法是按协议(protocol)、地址和文件分隔 URL，就像在 new URL(str).hashCode() 中所做的那样。方法(不能直接使用，因为它非常慢 -> 它即时解析 URL :/)
• 参见 squid-cache.org或 CacheDigest explanation

Answer 1

如果您想要始终有效的东西，而不仅仅是大部分时间，那么短哈希值不会削减它。正如您所观察到的，在任何长度小于 128 位的情况下，即使是理想的散列也会有很大的冲突率。你遇到的是一个缩放问题，你通过使用哈希码所做的就是减少常数因子——它仍然是 O(n)。

虽然听起来您的字符串有很多共同的前缀 - 您是否考虑过使用 trie 来存储它们？