-6

The backing data structure is a HashMap, which is basically an array of Entry. Since the backing structure is an array, how can the iteration order change over time?

user2698
  • 315
  • 1
  • 3
  • 8
  • 7
    Your basic assumption (it's only an array and nothing else) is incorrect. Read the Wikipedia article on the hash table data structure. – Jim Garrison Oct 02 '16 at 02:42
  • HashMap IS just an array. See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#HashMap.0table – user2698 Oct 02 '16 at 02:49
  • 3
    @user2698 - Yea ... but did you look at the rest of the code? The methods ... for instance? It is not just an array **and nothing else**. – Stephen C Oct 02 '16 at 02:53
  • The get() just goes through the array, and each array element (node) is a linked list or a tree. Where is the randomness in iteration coming from? – user2698 Oct 02 '16 at 02:54
  • 1
    @user2698 - So now read the methods that add and remove elements. (I am waiting to hear the sound of a light bulb going on ......) – Stephen C Oct 02 '16 at 02:55
  • 1
    I'm really confused by the number of downvotes this is getting. Is the question really that bad, or are people voting based on how obvious they may think the answer is? – 4castle Oct 02 '16 at 03:02
  • @StephenC I do know that resize() and linked list insertion/deletion can occur. Maybe I should rephrase my question as "if no elements are inserted or deleted, how can the iteration order change even though the backing data structure is basically an array?" – user2698 Oct 02 '16 at 03:02
  • 1
    These two might help: http://stackoverflow.com/questions/31471982/why-hashset-order-always-same-for-my-program, http://stackoverflow.com/questions/34625357/why-does-the-set-in-java-seem-to-insert-the-same-way-every-time-i-thought-order – Tom Oct 02 '16 at 03:11
  • 1
    @user2698 - The answer to your modified question is. With current / past implementations it won't; e.g. the code you are looking at. With future implementations, it might; e.g. the code that you can't see because it hasn't been written yet. The javadoc allows that it >>could<< be non-deterministic. – Stephen C Oct 02 '16 at 03:11
  • The down votes are because this is a data structure that is extremely well documented in many places, and the Java source code is easily available. It is a waste of everybody's time to ask this question here. Part of being a developer is knowing how to find answers, and this is a canonical example of a question you could have answered yourself very easily with 30 minutes of research. – Jim Garrison Oct 02 '16 at 04:44

1 Answers1

2

The order of iteration of a hash set is arbitrary, yet it is deterministic.

The order does not change over time, unless the set is changed in between of iterations. Given the same set of items and a specific insertion order, the order of iteration is going to remain the same.

The order of iteration is going to change if you insert or delete items. The underlying data structure, an array of list nodes, remains the same, but since the placement of an item into a hash bucket is determined by item's hash code, you cannot tell where a specific item is going to end up when you iterate a hash set.

The documentation does say that the order of iteration is not guaranteed:

[HashSet] 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.

The "over time" part is pretty vague, for two reasons: it is not clear if "over time" refers to the run time of your program, or to the time between upgrades to Java class library, and also it is not clear if modifications are allowed during the time over which the iteration order is allowed to change.

However, knowing the way a hash set is organized and implemented, it is a very near certainty that the iteration order is going to remain deterministic in the absence of updates. It does not mean that you can rely on the order, though, because it is subject to change at any time.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    I don't think that's true. From the javadocs: "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." From this sentence, I understand that even if you don't add/delete any elements, iteration order can still change. – user2698 Oct 02 '16 at 02:56
  • 3
    @user2698 - Well, for a different implementation of `HashSet`, they could change! The point is the javadoc is a contract that will be fulfilled by past, present and future versions of `HashSet`, even if it the code was rewritten completely. The contract says "don't rely on the order not changing in some circumstance that we can't tell you about ... yet". – Stephen C Oct 02 '16 at 03:02
  • 3
    Oh yes ... and serializing / deserializing is likely to change iteration order, as is copying using `new HashSet(set)`. – Stephen C Oct 02 '16 at 03:04
  • 1
    @StephenC Right, so user2698 is saying that the JavaDoc is saying that the order of iteration is **not** deterministic according to the contract. The JavaDoc doesn't agree with the first two paragraphs of this answer. – 4castle Oct 02 '16 at 03:04
  • 1
    @4castle - That is correct. But the flip-side is that earlier he was arguing that not only was the order deterministic, but it couldn't even change! What dasblinkenlight is actually talking about is the behavior of current and past versions of `HashSet` which are all deterministic ... even though the javadoc does not guarantee that. – Stephen C Oct 02 '16 at 03:09
  • 1
    (It is now clear that he (user2698) was not considering what happens when a `HashSet` is updated. But even when you exclude that, the javadoc >>allows<< the iteration order to be non-deterministic, even though the current implementations are deterministic in that circumstance.) – Stephen C Oct 02 '16 at 03:17