Use HashMap when order does not matter, LinkedHashMap when you need predictable encounter order, and TreeMap when keys must stay sorted or support range and navigation queries. Hashtable is a legacy synchronized option that rejects null keys and values; its synchronization does not automatically make multi-step operations atomic. The choice is mainly about ordering, null handling, and concurrency—not a universal speed ranking.
HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap: at a glance
| Implementation | Iteration order | Core operation cost | Null policy | Synchronization |
|---|---|---|---|---|
HashMap |
No order guarantee | Expected constant-time get and put if hashes disperse entries properly |
Allows one null key and null values | Not synchronized |
LinkedHashMap |
Insertion order by default; optionally access order | Expected constant-time basic hash operations with suitable hash dispersion; iteration takes time proportional to map size | Allows null elements | Not synchronized |
TreeMap |
Sorted by natural key order or a supplied comparator | Guaranteed logarithmic time for key lookup, insertion, and removal operations | Null keys depend on comparator; natural ordering rejects null. Null values are allowed. | Not synchronized |
Hashtable |
No useful predictable order guarantee | Hash-table performance is affected by capacity, load factor, and collisions | Rejects null keys and values | Synchronized legacy class |
These are API-described behaviors, not benchmark results. Hash-based constant-time descriptions depend on effective hash dispersion; TreeMap’s logarithmic guarantee is an asymptotic complexity guarantee. Oracle’s documentation does not establish one implementation as universally fastest. See Oracle’s HashMap, TreeMap, LinkedHashMap, and Hashtable API documentation.
When should you use HashMap?
Choose HashMap for general-purpose key-to-value lookup when you do not need a defined iteration order. It is hash-table-based and permits one null key and null values. Its basic get and put operations are expected to take constant time when the hash function disperses entries properly; poor dispersion and collisions can slow operations. Capacity and load factor also affect the space and lookup tradeoff.
Do not write code that relies on a particular HashMap iteration order. It has no order guarantee, and observed output can change as map contents or implementation conditions change. The class is not synchronized; concurrent structural mutation requires an explicit synchronization strategy.
When is LinkedHashMap a better fit?
Choose LinkedHashMap when iteration needs a defined encounter order. By default, that is insertion order: adding a value for a key already present does not move that key to a new position. Internally, it combines a hash table with a doubly linked list, adding bookkeeping compared with HashMap.
Insertion order
Use the normal constructor when consumers should see entries in the order they were first inserted. This can make iteration and output predictable without sorting keys.
Rank #2
Access order and cache policies
An access-order LinkedHashMap orders entries from least recently accessed to most recently accessed. A successful access can therefore change the map’s encounter order: in this configuration, even a get can affect iteration. The removeEldestEntry hook can support automatic eldest-entry removal policies, such as a simple least-recently-used cache policy.
Basic hash operations remain expected constant-time when hashes disperse well, while iteration over collection views takes time proportional to map size regardless of capacity. The class is not synchronized. If multiple threads use an access-ordered instance, account for accesses that alter its order when designing synchronization.
When should you use TreeMap?
Choose TreeMap when you need keys kept in natural sorted order or in an order defined by a Comparator. It is a red-black-tree implementation of NavigableMap, so it supports sorted views, range traversal, and navigation queries such as finding the floor, ceiling, higher, or lower key.
Oracle’s TreeMap API documentation guarantees logarithmic time for containsKey, get, put, and remove. That is a complexity guarantee, not a timing comparison against another map. The class is not synchronized.
Rank #4
Choose the ordering rule carefully
Natural ordering rejects null keys. A supplied comparator may define a different null policy, so check its behavior rather than assuming null keys are accepted. A further contract issue arises if a comparator treats two distinct keys as equal even though their equals methods do not: the map can still operate, but it no longer conforms to the general Map contract.
Is Hashtable the right choice for synchronized access?
Hashtable is a legacy synchronized hash table. It rejects null keys and values and relies on keys’ hashCode and equals behavior. Its older Dictionary inheritance and use by APIs such as Properties can matter when maintaining legacy code.
Do these 3 things before closing this tab:
1Fix the driver behind crashes, sound loss and screen glitches2Repair Windows errors before they cause bigger problems3Scan for outdated or missing drivers - takes under a minuteBest Value
Synchronization of individual methods does not make a sequence of calls atomic. For example, a check followed by an update can still require a deliberate strategy to protect the whole operation. Choose a concurrency design based on the required behavior rather than treating Hashtable as a universal answer for concurrent workflows.
Quick Recap
Map rules that apply whichever implementation you choose
- Order belongs to the implementation. The
Mapspecification defines order in terms of iteration over collection views; implementations may define an encounter order or leave it unspecified. See Oracle’s Map API. - Do not mutate a stored key in a way that changes equality behavior. A map depends on stable key equality behavior while the key is stored; changing it can undermine reliable lookup.
- Distinguish absent keys from null-valued keys. In null-permitting maps,
get(key)returns null both when the key is absent and when it is present with a null value. UsecontainsKey(key)when that distinction matters.
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
