1

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?

1
  • 1
    Have a look at the java HashMap class(source code). You will get answers. Commented Feb 23, 2013 at 2:44

2 Answers 2

2

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.

Sign up to request clarification or add additional context in comments.

1 Comment

Does this mean that one bucket will only have one hashcode mapped to it and collision is only when two objects get the same hashcode and hence get mapped to the same bucket?
2

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.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.