CODEWITHSUNDEEP
javahashcodehash-collision
nd07
nd07

Reputation: 127

Uniform distribution of hashcode()

I define my class as:

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

I also define an array to contain object key . For example:

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

The problem is that hashcode() can return a negative value so

arr[h+i % h] = k;

can return an error out of array index. That's why I changed my code as(based on my searching for avoiding hashcode() return negative value):

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

So if I do this way, does a uniform distribution of the hashcode() be changed or not? I mean the probability to have a same value from two different objects will be increased or not?

Upvotes: 6

Views: 2961

Answers (2)

Ram Ghadiyaram
Ram Ghadiyaram

Reputation: 29165

Please have look in to Murmurhash and MurmurHash - what is it? Fortunately Google guava has ready made implementation for this.

Guava way is like below example We have following classes

import com.google.common.hash.HashCode; import com.google.common.hash.HashFunction; import com.google.common.hash.Hashing;

using the above classes I have my method to generate hashcode like below

/**
     * 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());
    }

Upvotes: 2

Peter Lawrey
Peter Lawrey

Reputation: 533500

The Object.hash() has a very simple hashCode which is not particularly uniform for simple examples. e.g. Objects.hash("B", "B") and Objects.hash("A", "a") have the same hashCode. (And BTW simple enough that I could work that out in my head)

Also every between Objects.hashCode("a", "a") and Objects.hashCode("z", "z") is between 4065 and 4865 which doesn't look particularly uniform, esp for the higher bits.

Within this context, I think you can say you are not making matters any worse.

Upvotes: 2

Related Questions