How does Java order items in a HashMap or a HashTable?
java.util.HashMap is unordered; you can't and shouldn't assume anything beyond that.
This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
java.util.LinkedHashMap uses insertion-order.
This implementation differs from
HashMapin that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
SortedMap, uses either natural or custom ordering of the keys.
The map is sorted according to the natural ordering of its keys, or by a
Comparatorprovided at map creation time, depending on which constructor is used.
How does HashTable Order Values?
Similar to HashMap, HashTable also does not guarantee insertion order for the elements.
HashTable is optimized for fast look up. This is achieved by calculating hash for key values stored. This ensures that searching for any value in
HashTable is O(1), takes the same time irrespective the number entries in
Thus the entries are stored based on the hash generated for key. This is the reason why
HashTable does not guarantee the order of the elements in which they were inserted.
A hash value (or simply hash), also called a message digest, is a number generated from a string of text. The hash is substantially smaller than the text itself, and is generated by a formula in such a way that it is extremely unlikely that some other text will produce the same hash value.
Is the order of values retrieved from a HashMap the insertion order
The values are printed in the order in which they have been inserted. Is this true in general? I was expecting the values to be printed in random order.
HashMap API does not define the order of iteration.
However, if you look at the implementation of HashMap, you can deduce that there is a complex transient relationship between the iteration order, the keys' hash values, the order in which the keys were inserted and the size of the hashtable. This relationship gets scrambled if the hashtable resizes itself.
In your case, you are using
Integer keys which means that the hash values of the keys are the key values themselves. Also, you inserted the entries in key order. This leads (fortuitously!) to the iteration order matching the insertion order. But if you kept inserting more keys, you would find that the iteration order "wraps around". Then as the table goes through a series of resizes, the order will get progressively more and more scrambled.
In short, what you are seeing is an artefact of the hashtable implementation, and not something that you can (or should) sensibly make use of. Not least because it could change from one Java release to the next.
How to keep the order of elements in hashtable
Hash table and linked list
implementation of the
with predictable iteration order. This
implementation differs from
that it maintains a doubly-linked list
running through all of its entries.
This linked list defines the iteration
ordering, which is normally the order
in which keys were inserted into the
map (insertion-order). Note that
insertion order is not affected if a
key is re-inserted into the map. (A
key k is reinserted into a map m if
m.put(k, v)is invoked when
immediately prior to the invocation.)
So, for example:
Map<String, String> map = Collections.synchronizedMap(
new LinkedHashMap<String, String>());
Java Class that implements Map and keeps insertion order?
I suggest a
LinkedHashMap or a
LinkedHashMap keeps the keys in the order they were inserted, while a
TreeMap is kept sorted via a
Comparator or the natural
Comparable ordering of the keys.
Since it doesn't have to keep the elements sorted,
LinkedHashMap should be faster for most cases;
O(log n) performance for
remove, according to the Javadocs, while
O(1) for each.
If your API that only expects a predictable sort order, as opposed to a specific sort order, consider using the interfaces these two classes implement,
SortedMap. This will allow you not to leak specific implementations into your API and switch to either of those specific classes or a completely different implementation at will afterwards.
How to sort a Java Hashtable?
If you want an order-preserving map, you should use
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key
kis reinserted into a map
m.put(k, v)is invoked when
m.containsKey(k)would return true immediately prior to the invocation.)
This implementation spares its clients from the unspecified, generally chaotic ordering provided by
Hashtable), without incurring the increased cost associated with
Note that this is usually compared with
HashMap rather than
Hashtable - I don't know of an order-preserving equivalent to
Hashtable; the latter isn't usually used these days anyway (just as
ArrayList is usually used in preference to
I've assumed you want insertion order rather than key-sorted order. If you want the latter, use
Order HashMap alphabetically by value
HashMaps are intrinsically unordered and cannot be sorted.
Instead, you can use a SortedMap implementation, such as a TreeMap.
However, even a sorted map can only sort by its keys.
If you want to sort by the values, you'll need to copy them to a sorted list.
HashMap where the order of keys is important
LinkedHashMap maintains insertion-order. Beyond that there are various
SortedMap implementations such as
Sorting a HashMap and collecting it to a list
There are no parameters for
Collectors.toList() as you should see...
So, you got stream of entries, you want map entries to keys, you should use