Search code examples
javahashmaphashtablehash

Why would a higher load factor in HashMap increase lookup cost?

From JavaDoc of HashMap :

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).

If we have a higher value ,why would it increase the lookup cost ?

Solution

  • Hash table's Load Factor is defined as

    n/s, the ratio of the number of stored entries n and the size s of the table's array of buckets.

    High performance of hash table is maintained when the number of collisions is low. When the load factor is high, the number of hash buckets needed to store the same number of entries remains lower, thus increasing the probability of collisions.