HashMap, LinkedHashMap and TreeMap

Three implementations of Map, with the same methods and three different answers to the question the interface does not ask: in what order do the entries come back.

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 input. TreeMap when you need keys sorted, or the questions only a sorted map can answer — firstKey, headMap, ceilingKey.

LinkedHashMap has one option worth knowing about. Constructed in access order, it moves an entry to the end every time it is read, and overriding one method turns it into a least-recently-used cache in about six lines.

java

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