Why does HashMap require that the initial capacity be a power of two?

by

The map has to work out which internal table index to use for any given key, mapping any int value (could be negative) to a value in the range [0, table.length). When table.length is a power of two, that can be done really cheaply – and is, in indexFor:

static int indexFor(int h, int length) {
    return h & (length-1);
}

With a different table length, you’d need to compute a remainder and make sure it’s non-negative . This is definitely a micro-optimization, but probably a valid one 🙂

Also, when automatic rehashing is performed, what exactly happens? Is the hash function altered too?

It’s not quite clear to me what you mean. The same hash codes are used (because they’re just computed by calling hashCode on each key) but they’ll be distributed differently within the table due to the table length changing. For example, when the table length is 16, hash codes of 5 and 21 both end up being stored in table entry 5. When the table length increases to 32, they will be in different entries.

More Related Contents:

  1. What are the differences between a HashMap and a Hashtable in Java?
  2. Good Hash Function for Strings
  3. What happens when a duplicate key is put into a HashMap?
  4. How does Java order items in a HashMap or a HashTable?
  5. ConcurrentHashMap and Hashtable in Java [duplicate]
  6. How to create a HashMap with two keys (Key-Pair, Value)?
  7. What hashing function does Java use to implement Hashtable class?
  8. Why Hashtable does not allow null keys or values?
  9. Explanation of HashMap#hash(int) method
  10. How can I generate an MD5 hash in Java?
  11. Why does Java’s hashCode() in String use 31 as a multiplier?
  12. How to loop through a HashMap in JSP?
  13. How can I convert JSON to a HashMap using Gson?
  14. Is a HashMap thread-safe for different keys?
  15. Why there is no ConcurrentHashSet against ConcurrentHashMap
  16. Can an array be used as a HashMap key?
  17. How to hash a string in Android?
  18. What is the optimal capacity and load factor for a fixed-size HashMap?
  19. HashMap implementation in Java. How does the bucket index calculation work?
  20. HashMap to return default value for non-found keys?
  21. Java: how to convert HashMap to array
  22. Android – Get value from HashMap
  23. get string value from HashMap depending on key name
  24. Hashtable key within integer interval
  25. Initialize Java Generic Array of Type Generic
  26. Java calculate hex representation of a SHA-1 digest of a String
  27. Hash : How does it work internally?
  28. How does ConcurrentHashMap work internally?
  29. How to convert a string to a HashMap? [duplicate]
  30. Compare two hex strings in Java?

Leave a Comment