Java HashMap key hashing

Question

What will happen if I enter a key and value in hashmap and the index generated based on key hashcode is greater than 15 and the map size is still less than threshold which is 12?

Thanks in advance.

Answer 1

The HashMap will typically perform modulo arithmetic on the value supplied by the hashCode() method, in order to map the full range of integers onto the range of valid indices on its internal array.

This can lead to collisions (different hash values mapping to the same index), which is a separate topic, and also leads to the degradation of the O(1) expected time of a HashMap. One caveat is that it is assumed that your hashCode() implementation is a uniform distribution.

In a good HashMap API, you don't need to worry about the internal array size or collisions. That is handled internally by the implementation in various ways.

There is no "threshold" publicly visible in Java's HashMap API. The closest you can get is:

HashMap(int initialCapacity, float loadFactor)

Here, the threshold you mention is equivalent to the loadFactor. According to the Java docs:

"As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur."

Basically this means that if there are too many collisions in the HashMap, it will expand its current array size and re-hash all the current keys, resulting in a (hopefully) more uniform distribution. This should have the effect that the expected O(1) complexity is maintained across a series of additions or deletions from the HashMap.

Answer 2

Let me give you a bit broader picture, rather than concentrating only on Java's particular data type HashMap, as your question includes hashcode tag, and it seems to me, that you are interested into more generic picture - how does hashing function work.

Index Normalization

is what you need to understand.

Generally, how index normalization happens completely depends on the implementation of a particular data-structure that hashes input to the key (like HashTable/HashMap) and whatever implementation it is, one can be said for sure:

your hash function h(x) should be responsible for always and consistently producing an integer, which is in a valid index range of the backing array.

In many implementations, hash functions may return quite a long (and possibly negative) integer number, and this is most commonly resolved by index normalization, which just does something to that long integer (crops, makes negative number positive, etc.).

For Java's HashMap implementation, hashCode() is:

@HotSpotIntrinsicCandidate
public native int hashCode();

which means, that implementation is delegated to the underlying layer.

But in most cases, you can assume, that it will use modulo of the length of backing array (number of buckets), which means, it will never exceed the length of that array (hence, the size of your hashmap).