Menu
I have some code utilizing standard Java collections: arrays, ArrayDeques, HashMaps, Lists, HashSets.
My code is expected to be deterministic: the hash codes of all the elements, the initial contents of the collections, and etc. are expected to depend only on the input data. The final output of the code is produced from a keySet() of some HashMap.
I've noticed that the order of the elements in the resulting keySet sometimes changes from run to run. What does it mean?
This happens quite consistently with JDK 1.7.0_60, x86 on Windows 7 x64. Allegedly, this does not happen (or happens rarely) with JDK 1.8.0_05. Also, the order of elements in the resulting keySet (and the overall order in which the data items are processed) changes when switching between the above JDKs.
I suspect, this is some feature of a HashSet, but could not trace it to a specific line of code.
UPD 1 I do not really need deterministic sets, and I know that HashSet provides no guarantees. I'm just trying to find the reason of non-deterministic behavior. If it is in library code - fine. But if it is in my code - I'll likely have to fix it. Hence the question.
UPD 2 Of course, I managed to find the answer right after posting the question. Just in the beginning of 1.7's HashMap.java:
/**
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find. If 0 then
* alternative hashing is disabled.
*/
transient int hashSeed = 0;
In 1.8, this randomization doesn't seem to be there any more.
744
But when put into HashSet, it has its own order base on hashcode of elements, it means if all elements have unique hashcode, you run 1000 times, the orders are always the same! You see? No Alphabet order! if you run 1000 times, the orders are always the same: No.
HashSet does not provide any method to maintain the insertion order. Comparatively, LinkedHashSet maintains the insertion order of the elements. We can not predict the insertion order in HashSet, but we can predict it in LinkedHashSet. The LinkedHashSet extends the HashSet, so it uses a hashtable to store the elements.
It means that HashSet does not maintains the order of its elements. Hence sorting of HashSet is not possible.
No, a hash set won't preserve insertion order, at least not predictably. You could use a LinkedHashSet (Java), or an equivalent. A LinkedHashSet will preserve order. If you want order, you shouldn't even be using a set in the first place... its not made for ordered elements, except in exceptional cases.
From the documentation of HashSet:
It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.
148
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
