How Does Java Order Items in a Hashmap or a Hashtable

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 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).

java.util.TreeMap, a 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 Comparator provided 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.

Reason
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 HashTable.

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.

http://www.webopedia.com/TERM/H/hashing.html

http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

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.

The 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

Use a LinkedHashMap.

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 k is reinserted into a map m if
m.put(k, v) is invoked when
m.containsKey(k) would return true
immediately prior to the invocation.)

combined with Collections.synchronizedMap().

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 TreeMap. 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; TreeMap has O(log n) performance for containsKey, get, put, and remove, according to the Javadocs, while LinkedHashMap is 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, NavigableMap or 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 LinkedHashMap:

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 k is reinserted into a map m if 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 HashMap (and Hashtable), without incurring the increased cost associated with TreeMap.

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 Vector).

I've assumed you want insertion order rather than key-sorted order. If you want the latter, use TreeMap.

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 TreeMap.

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 map.

        myMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());

---

Related Topics