java - hashcode() 均匀分布

Question

我将我的类定义为:

final class Key<T extends Comparable<T>> {
    private final T q;
    private final T o;
    public Key(T q1, T o1) {
        q = q1;
        o = o1;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Key) {
            Key<T> s = (Key<T>)obj;
            return q.equals(s.q) && o.equals(s.o);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(q,o);
    }
}

我还定义了一个数组来包含对象键。例如:

Object arr[] = new Object[100];
Key<String> k = new Key<>("a","b");
int h = k.hashcode();
...
arr[h+i % h] = k; //i from 1 to 10 for example

问题是 hashcode() 可以返回一个负值，所以

arr[h+i % h] = k;

可以返回数组索引之外的错误。这就是为什么我将代码更改为(基于我为避免 hashcode() 返回负值而进行的搜索):

@Override
        public int hashCode() {
            return (Objects.hash(q,o)&0x7FFFFFFF);
        }

如果我这样做，hashcode() 的均匀分布是否会改变？我的意思是两个不同对象具有相同值的概率会增加还是不会增加？

Answer 1

请查看Murmurhash和 MurmurHash - what is it?幸运的是，Google Guava 已经为此做好了准备。

Guava 方法如下例我们有以下类(class)

导入com.google.common.hash.HashCode；
导入 com.google.common.hash.HashFunction；
导入 com.google.common.hash.Hashing;

使用上面的类，我有生成哈希码的方法，如下所示

/**
     * getMurmur128Hash.
     * 
     * @param content
     * @return HashCode
     */
    public static HashCode getMurmur128Hash(String content) {
        final HashFunction hf = Hashing.murmur3_128();
        final HashCode hc = hf.newHasher().putString(content, Charsets.UTF_8).hash();
        return hc;
    }
    /**
     * getAbsMurmur128HashAsLongVal.
     * 
     * @param content
     * @return Long Absolute value of Long for the HashCode.
     */
    public static Long getAbsMurmur128HashAsLongVal(String content) {
        return Math.abs(getMurmur128Hash(content).asLong());
    }