CODEWITHSUNDEEP
javadata-structureshashhashmap
Sandeep Jindal
Sandeep Jindal

Reputation: 15338

Java hashcode and bucket size - Relationship

Java hashcode is an integer (size 2 pow 32)

When we create a hashtable/hashmap it creates buckets with size equals Initial Capacity of the Map. In other words, it creates an array of size "Initial Capacity"

Question 1. How does it map the hashcode of a key (java object) to the bucket index? 2. Since size of hashmap can grow, can the size of hashmap be equal to 2 pow 32? If answer is yes, it is wise to have an array of size 2 pow 32?

Upvotes: 1

Views: 1748

Answers (2)

Stephen C
Stephen C

Reputation: 718758

Here is a link to the current source code: http://www.docjar.com/html/api/java/util/HashMap.java.html

The answers to your questions are (in part) implementation specific.

1) See the code. Note that your assumption about how initialCapacity is implemented is incorrect ... for Oracle Java 6 and 7 at least. Specifically, initialCapacity is not necessarily the hashmap's array size.

2) The size of a HashMap is the number of entries, and that can exceed 2^32! I assume that your are actually talking about the capacity. The size of the HashMap's array is theoretically limited to 2^31 - 1 (the largest size for a Java array). For the current implementations, MAX_CAPACITY is actually 2^30; see the code.

3) "... it is wise to have an array of size 2^32?" It is not possible with Java as currently defined, and it is unwise to try to do something that is impossible.

If you are really asking about the design of hash table data structures in Java, then there is a trade-off between efficiency for normal sized hash tables, and ones that are HUGE; i.e. maps with significantly more than 2^30 elements. The HashMap implementations are tuned to work best for normal sized maps. If you routinely had to deal with HUGE maps, and performance was critical, then you should be looking to implement a custom map class that is tuned to your specific requirements.

Upvotes: 2

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

The size of a Java array is actually limited to Integer.MAX_VALUE elements, 2^31-1.

HashMap uses power of two array sizes, so presumably the largest it could use is 2^31. You would need a large physical memory to make that reasonable.

HashMap does a series of shift and xor operations to reduce some sources of collisions before doing a simple bitwise AND to get the bucket index.

Upvotes: 2

Related Questions