Why does Map has loadFactor and List does not have it?

Question

When one creates a Map or a List in Java, they both have the same default initial capacity of 10. Their capacity grows as they get new elements. However, the List only grows when the 11th element is added and the Map grows already when the 8th element is added. It happens because the Map has a loadFactor field, which regulates how "saturated" it can be. When the saturation is higher than the loadFactor, the Map grows. The loadFactor is 0.75 by default.

I wonder why do Lists and Maps have different mechanisms for deciding when to increase their initial capacity?

Answer 1

Maps have load factor because the load factor determines their performance. When you lower the load factor, you get better performance (but you pay for it with increased memory usage).

Take HashMap for example. The capacity is the size of the backing array. However, each position of the array may contain multiple entries. The load factor controls how many entries in average would be stored in a single array position.

On the other hand, in ArrayList each index of the backing array holds a single element, so there's no meaning to a load factor.

Answer 2

Maps as such don't have a loadFactor - only implementations based on some kind of HashMap do have it (e.g. there's no loadFactor on a TreeMap).

Why is that?

A HashMap contains a number of "buckets" and when adding or retrieving an entry you take the key's hashcode and calculate which bucket you have to put it in or retrieve it from. Based on the quality of the hash-implementation two distinct objects might end up in the same bucket. When this happens the hashmap starts a Linked list that you have to go through when retrieving the entry.

The HashMap and List differ in some important points:

• The capacity of the HashMap does not say how many elemnts could be stored in it, it's the number of buckets. In theory you could store more than capacity entries in a HashMap.
• Too much items ending up in the same bucket are bad for the HashMap's performance. If you have fewer buckets you have in relation to the number of entries you'll increase the number of such collisions. Enter the loadFactor: if things get "too tight" and you fear you'll get too much collisions you start to grow the number of buckets - even if there are still some empty ones left.