Understanding strange Java hash function

by

Here is some code and the sample output:

public static void main ( String[] args ) {
    int h = 0xffffffff;
    int h1 = h >>> 20;
    int h2 = h >>> 12;
    int h3 = h1 ^ h2;
    int h4 = h ^ h3;
    int h5 = h4 >>> 7;
    int h6 = h4 >>> 4;
    int h7 = h5 ^ h6;
    int h8 = h4 ^ h7;

    printBin ( h );
    printBin ( h1 );
    printBin ( h2 );
    printBin ( h3 );
    printBin ( h4 );
    printBin ( h5 );
    printBin ( h6 );
    printBin ( h7 );
    printBin ( h8 );

}

static void printBin ( int h ) {
    System.out.println ( String.format ( "%32s", 
        Integer.toBinaryString ( h ) ).replace ( ' ', '0' ) );
}

Which prints:

11111111111111111111111111111111
00000000000000000000111111111111
00000000000011111111111111111111
00000000000011111111000000000000
11111111111100000000111111111111
00000001111111111110000000011111
00001111111111110000000011111111
00001110000000001110000011100000
11110001111100001110111100011111

So, the code breaks down the hash function into steps so that you can see what is happening. The first shift of 20 positions xor with the second shift of 12 positions creates a mask that can flip 0 or more of the bottom 20 bits of the int. So you can get some randomness inserted into the bottom bits that makes use of the potentially better distributed higher bits. This is then applied via xor to the original value to add that randomness to the lower bits. The second shift of 7 positions xor the shift of 4 positions creates a mask that can flip 0 or more of the bottom 28 bits, which brings some randomness again to the lower bits and to some of the more significant ones by capitalizing on the prior xor which already addressed some of the distribution at the lower bits. The end result is a smoother distribution of bits through the hash value.

Since the hashmap in java computes the bucket index by combining the hash with the number of buckets you need to have an even distribution of the lower bits of the hash value to spread the entries evenly into each bucket.

As to proving the statement that this bounds the number of collisions, that one I don’t have any input on. Also, see here for some good information on building hash functions and a few details on why the xor of two numbers tends towards random distribution of bits in the result.

More Related Contents:

  1. Count number of values of a list having same hash value in java?
  2. How to convert fuzzy hash string to a file? [closed]
  3. How can I generate an MD5 hash in Java?
  4. Why does Java’s hashCode() in String use 31 as a multiplier?
  5. Best implementation for hashCode method for a collection
  6. How to decrypt a SHA-256 encrypted string?
  7. Good Hash Function for Strings
  8. How to call a method stored in a HashMap? (Java) [duplicate]
  9. How to hash a string in Android?
  10. What is a best practice of writing hash function in java?
  11. How do I generate a SALT in Java for Salted-Hash?
  12. Why does HashMap require that the initial capacity be a power of two?
  13. Convert a String to a byte array and then back to the original String
  14. Initialize Java Generic Array of Type Generic
  15. How to create a HashMap with two keys (Key-Pair, Value)?
  16. What hashing function does Java use to implement Hashtable class?
  17. Java Equivalent to Python Dictionaries
  18. What is a good 64bit hash function in Java for textual strings?
  19. Java calculate hex representation of a SHA-1 digest of a String
  20. What is the reason behind Enum.hashCode()?
  21. Persisting sha256 hash objects?
  22. Java, divide incoming work uniformly via hashing in multithreaded evnironments
  23. Hash : How does it work internally?
  24. Good hashCode() Implementation
  25. Compare two hex strings in Java?
  26. Generate Subject Hash of X509Certificate in Java
  27. How to hash a password with SHA-512 in Java?
  28. Explanation of HashMap#hash(int) method
  29. How to bind an object list with thymeleaf?
  30. Printing out a 2D array in matrix format

Leave a Comment