How Is Hashcode() Calculated in Java

How is hashCode() calculated in Java

A hashcode is an integer value that represents the state of the object upon which it was called. That is why an Integer that is set to 1 will return a hashcode of "1" because an Integer's hashcode and its value are the same thing. A character's hashcode is equal to it's ASCII character code. If you write a custom type you are responsible for creating a good hashCode implementation that will best represent the state of the current instance.

how hashcodes are calculated for objects in java?

hashcodes are usualy implemented for each object and are calculated using the fields that make that object unique and to comply with the hashcode equals contract.
If left unimplemented the hashcode of the super class will be used.

The "default implementation" will be objects hashcode which is calculated using it's memory address also known as pointer.

How is Java String hashCode calculated on objects

When an object is inserted into a HashMap, it does use the hashCode method to decide where to store it. But hashCodes aren't intended to be completely unique. There can be different values that produce the same output but aren't equal, so the HashMap will have some method of dealing with collisions like that. get will only return a value if the keys have both the same hashCode, and are equal using the equals method. "Sun" does not equal "TWO", but the hashCode of "Sun" does equal the hashCode of "TWO".

From the documentation:

if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

So it's equality, not the hashcode, that determines what gets returned. The hashcode is effectively just an optimization to make the process of finding which objects are likely to be equal much faster.

How does Java Hashtable calculate where to place an element based on hashcode?

Implementation-dependent (as in, if you rely on it working this way, your code is broken; the things HashMap guarantees are spelled out in its javadoc, and none of what I'm about to type is in there):

hashes are just a number. Between about -2billion and +2billion. That 'long weird string' you see is just a more convenient way to show it to you.

First, the higher digits of that number are mixed into the lower digits (actually, the higher bits are XORed into the lower ones): 12340005 is turned into 12341239.

Then, that number is divided by how many buckets there currently are, but the result is tossed out, it's the remainder we are interested in. This remainder is necessarily 0 or higher, and never more than '# of buckets there are', so always points exactly at one of the buckets.

That's the bucket that the object goes into.

if buckets grow too large, a resizing is done.

For more, well, HashMap is open source, as is HashSet - just have a look.

How to calculate the hash code of a string by hand?

Take a look at the source code of java.lang.String.

/**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;
        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Why do we use number 31 while calculating hashcode

from Joshua Bloch, Effective Java, Chapter 3, Item 9

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

Some words about multiplication can be replaced by a shift. Multiplying to 2 is pretty easy operations in binary algebra. You just need to shift the number to the left and add 0 to the end. 4*2 = b100 << 1 = b1000 = 8. If a factor is a power of 2, you need to shift the binary number by the power value. 4*8 = 4 * 2^3 = b100 << 3 = b100000 = 32.

Also the same logic works for dividing: 8/4 = 8/2^2 = b1000 >> 2 = b10 = 2

---

Related Topics