0

我正在尝试实现自己的哈希函数，我使用 java 将每个字符串的 ASCII 数字相加。我通过查找哈希表大小和总和的 mod 来找到哈希码。大小%总和。我想知道在搜索字符串时是否有办法使用相同的过程但减少冲突？

提前致谢。

4

2 回答 2

6

我会查看 String 和 HashMap 的代码，因为它们的冲突率很低，并且不使用%和处理负数。

来自字符串的来源

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

来自 HashMap 的来源

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

由于 HashMap 的大小始终是 2 的幂，因此您可以使用

        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);

和

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

使用比长度&快得多，%并且只返回正数，因为长度是正数。

于 2012-12-11T18:05:36.693 回答
6

Java String.hashcode()在成为一个非常好的哈希函数和尽可能高效之间进行权衡。简单地将字符串中的字符值相加并不是可靠的哈希函数。

例如，考虑两个字符串dog和god。由于它们都包含“d”、“g”和“o”，因此任何仅涉及加法的方法都不会产生不同的哈希码。

Joshua Bloch实现了 Java 的一个重要部分，他在他的《 Effective Java》一书中讨论了 String.hashCode() 方法，并讨论了在 1.3 之前的 Java 版本中，String.hashCode() 函数如何仅考虑 16 个字符在给定的字符串中。这比当前的实现运行得快一些，但结果是在某些情况下性能非常差。

一般来说，如果您的特定数据集定义非常明确，并且您可以利用其中的一些独特性，您可能会制作出更好的散列函数。对于通用字符串，祝你好运。

于 2012-12-11T17:57:02.947 回答