HashMap implementation in Java. How does the bucket index calculation work?

by

The hash itself is calculated by the hashCode() method of the object you’re trying to store.

What you see here is calculating the “bucket” to store the object based on the hash h. Ideally, to evade collisions, you would have the same number of buckets as is the maximum achievable value of h – but that could be too memory demanding. Therefore, you usually have a lower number of buckets with a danger of collisions.

If h is, say, 1000, but you only have 512 buckets in your underlying array, you need to know where to put the object. Usually, a mod operation on h would be enough, but that’s too slow. Given the internal property of HashMap that the underlying array always has number of buckets equal to 2^n, the Sun’s engineers could use the idea of h & (length-1), it does a bitwise AND with a number consisting of all 1‘s, practically reading only the n lowest bits of the hash (which is the same as doing h mod 2^n, only much faster).

Example:

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

More Related Contents:

  1. How to print all the values for a key in HashMap in java
  2. what is the method to delete hashmap entry
  3. How to check if an integer is in a set of given ranges? [closed]
  4. Java 8 Streams hashmap
  5. How to get percentile in java
  6. What are the differences between a HashMap and a Hashtable in Java?
  7. Is the order of values retrieved from a HashMap the insertion order
  8. Java Compare Two Lists
  9. How to preserve insertion order in HashMap? [duplicate]
  10. java.lang.OutOfMemoryError: GC overhead limit exceeded [duplicate]
  11. HashMap Java 8 implementation
  12. Java associative-array
  13. Can an array be used as a HashMap key?
  14. Performance ConcurrentHashmap vs HashMap
  15. Java HashMap performance optimization / alternative
  16. Reverse HashMap keys and values in Java
  17. HashMap to return default value for non-found keys?
  18. ArrayList as key in HashMap
  19. Copying a HashMap in Java
  20. Java HashMap nested generics with wildcards
  21. How can I iterate over a map of ?
  22. Memory overhead of Java HashMap compared to ArrayList
  23. Is there a way to get the value of a HashMap randomly in Java?
  24. Java HashMap – deep copy
  25. How to create a HashMap with two keys (Key-Pair, Value)?
  26. Collision resolution in Java HashMap
  27. Thread safe Hash Map?
  28. Theoretical limit for number of keys (objects) that can be stored in a HashMap?
  29. what is the best way to get a sub HashMap based on a list of Keys?
  30. Is Java HashMap.clear() and remove() memory effective?

Leave a Comment