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.
ReasonHashTable
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 theMap
interface,
with predictable iteration order. This
implementation differs fromHashMap
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 returntrue
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 mapm
ifm.put(k, v)
is invoked whenm.containsKey(k)
would return true immediately prior to the invocation.)This implementation spares its clients from the unspecified, generally chaotic ordering provided by
HashMap
(andHashtable
), without incurring the increased cost associated withTreeMap
.
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
How to Ensure in Java That the Current Local Time Is Correct
Is Concurrenthashmap Totally Safe
Find an Array Inside Another Larger Array
Java.Net.Connectexception :Connection Timed Out: Connect
Why Does Java's Java.Time.Format.Datetimeformatter#Format(Localdatetime) Add a Year
Retrieve Java Annotation Attribute
Java 8 Default Methods as Traits:Safe
How to Redirect to Another Action Class Without Using on Struts.Xml
How to Get a Token from a Lucene Tokenstream
Java: String Concat VS Stringbuilder - Optimised, So What Should I Do
Numeric Textfield for Integers in Javafx 8 with Textformatter And/Or Unaryoperator
Java.Lang.Nosuchmethoderror in Flink
When Does the Main Thread Stop in Java
Java: Right Shift on Negative Number