For what it's worth, the three main Java map implementations are HashMap, which does what it says on the time, LinkedHashMap, which has some additional pointers to maintain insertion order (and thus has performance that suffers by a constant factor), and TreeMap, which is really a red/black tree which thus offers logarithmic lookup time instead of constant lookup time (i.e. it's not a hashtable at all).