更快的哈希函数

Question

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

提前致谢.

Answer 1

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

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

实现了Java的很好的一部分的Joshua Bloch在他的" Effective Java"一书中讨论了String.hashCode()方法,并讨论了在1.3之前的Java版本中,String.hashCode()函数如何仅考虑16个字符在给定的字符串中.这比当前的实施速度稍微快一些,但在某些情况下导致的性能非常差.

通常,如果您的特定数据集定义得非常好,并且可以利用其中的某些唯一性,那么您可能可以创建更好的散列函数.对于通用字符串,祝你好运.

Answer 2

我会看一下String和HashMap的代码,因为它们具有低冲突率并且不使用%和处理负数.

来自String的来源

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

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