HashMap Implementation question

Question

HashMap contains a hash-table which is an array that hold the values

as I understood the hash-table has an initial size, yet it can get increased after many invocation of put() (depends on the load-factor)

anyhow I wonder how can you find a value after you change the size of the hash-table because I know that in order to calculate the has code of specific key you can use the size of the table

for instance key*prime%size

so how does it work?

Answer 1

Because the key is generally used to locate the bin in which your value has been put. Reallocation doesnt affect this, since all objects are reassigned to new bins according to the new size.

Answer 2

If you look at the code of the addEntry(..) method, you see:

if (size++ >= threshold)
   resize(2 * table.length);

On resizing, the transfer(..) method is called, which:

Transfers all entries from current table to newTable.

Answer 3

Visage answers the question in general: the hash values calculated from the keys are mapped to the buckets by spreading them modulo the actual size of the map, and when the map is resized, all the elements are spread again over the new range of buckets.

However, starting from Java 1.4, there are a few things happening behind the curtain which is worth knowing. First of all, in a traditional hash map, the size is ideally a prime number, because this helps spreading the elements more evenly over the range of buckets. However, in the Java 1.4 HashMap, the size is always a power of two! This would make the standard distribution behave very badly - however, in this implementation the hash values are rehashed internally using a very fast algorithm to smooth out the distribution.

More details in the Java Specialist Newsletters, issues 54 and 54b.