Alex Rivera | Logout

What hashing function does Java use to implement Hashtable class?

Asked 2012-02-20T15:57:40.613
67

From the book CLRS ("Introduction to Algorithms"), there are several hashing functions, such as mod, multiply, etc.

What hashing function does Java use to map the keys to slots?

I have seen there is a question here Hashing function used in Java Language. But it doesn't answer the question, and I think the marked answer for that question is wrong. It says that hashCode() let you do your own hashing function for Hashtable, but I think it is wrong.

The integer returned by hashCode() is the real key for Hashtble, then Hashtable uses a hashing function to hash the hashCode(). What this answer implies is that Java give you a chance to give Hashtable a hashing function, but no, it is wrong. hashCode() gives the real key, not the hashing function.

So what exactly the hashing function does Java use?

java algorithm hashtable hash
Edit
Report

1 Answer

35

According to hashmap's source(java version < 8), every hashCode is hashed using the following method:

 /**
 * Applies a supplemental hash function to a given hashCode, 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.
 */
static int hash(int h) {
    // 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);
}

The reason every hashCode is hashed again is to further prevent a collision (see comments above)

HashMap also uses a method to determine the index of a hash code(java version < 8) (since length is always a power of 2, you can use & instead of %):

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

The put method looks something like:

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

The purpose of a hash code is to provide a unique integer representation for a given object. It makes sense, then, that Integer's hashCode method simply returns the value because each value would be unique to that Integer object.

Additional Ref:
answered 2012-02-20T16:09:30.540

Your Answer