Why does Java use (hash & 0x7FFFFFFF) % tab.length to decide the index of a key?

java algorithm hashtable
Jackson Tale picture Jackson Tale · Feb 21, 2012 · Viewed 12.8k times · Source

From the link below, I know Java uses (hash & 0x7FFFFFFF) % tab.length to decide which slot of an array to put the {key, value} in.

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Hashtable.java#Hashtable.put%28java.lang.Object%2Cjava.lang.Object%29

My question is why Java first does hash & 0x7FFFFFFF? Is there any particular purpose?

Answer

sinsedrix picture sinsedrix · Feb 21, 2012

Because:

  • 0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit.

  • (hash & 0x7FFFFFFF) will result in a positive integer.

  • (hash & 0x7FFFFFFF) % tab.length will be in the range of the tab length.

Related questions

What hashing function does Java use to implement Hashtable class?

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 …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More