HashMap vs LinkedHashMap vs TreeMap

The same methods, and three answers to the order in which entries come back.

HashMap, LinkedHashMap and TreeMap implement Map with the same methods. They differ in the order entries come back in when you iterate, what that costs, and what they require of the keys. Switching between them is one word after new, as long as the keys meet each new class's own key requirements.

The three maps on order, cost and what they demand of keys
Class	Iterates in	get and put	Keys must
`HashMap`	No promised order	Constant	Have `hashCode` and `equals`
`LinkedHashMap`	Insertion order, or access order	Constant, plus two pointers each	Have `hashCode` and `equals`
`TreeMap`	Sorted by key	Proportional to the logarithm of the size	Be `Comparable`, or have a `Comparator`

The decision rule. HashMap unless you need an order. LinkedHashMap when output must be reproducible or must match the input order. TreeMap when you need keys sorted, or the questions only a sorted map can answer, such as firstKey, headMap and ceilingKey.

LinkedHashMap has one option worth knowing. Constructed in access order, it moves an entry to the end each time it is read, and overriding one method turns it into a least-recently-used cache (one that drops the entry nobody has read for longest) in a few lines:

java

new LinkedHashMap<String, Row>(16, 0.75f, true) {
    @Override protected boolean removeEldestEntry(Map.Entry<String, Row> eldest) {
        return size() > 1000;
    }
};

On the Java Collections cheatsheet

← → move through sections and cards