-3

(This question is not about using LinkedHashSet over HashSet)

I know that HashSet does not preserve any order of addition:

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

Suppose there is a program that adds the exactly same elements in the same order to a HashSet and outputs the elements. 

HashSet<Integer> set = new HashSet<Integer>();
Random random = new Random(1000);
for (int i = 0; i < 1000; i++)
    set.add(random.nextInt());
set.forEach(s -> System.out.println(s));

If I rerun the same program multiple times, are the outputs guaranteed the same?

Dau Zi
  • 268
  • 1
  • 3
  • 8
  • 1
    In practice, yes. But I wouldn't consider that a guarantee, so you should clarify what exactly you mean by guaranteed. The objects also need to have the same hash codes from run to run, which most do. That is, they can't use a seed that's randomly picked at jvm time. (Which is possible, though not common in Java. I don't think I've ever seen it.) – yshavit Aug 25 '17 at 03:04
  • 1
    Guaranteed? No. But they could be consistent depending on the `hashCode()` implementation. In contrast, I hear that Java 9's `Map` factory implementations will use a random seed to discourage developers from relying on the iteration order. – shmosel Aug 25 '17 at 03:05
  • Oh, and you'll need to keep the same jvm version, too – yshavit Aug 25 '17 at 03:10
  • @shmosel It could also be to prevent DOS attacks. It's possible (easy, even) to intentionally create hash collisions in order to make a hash map's time O(n^2) instead of O(n). – yshavit Aug 25 '17 at 03:14
  • Hash tables are completely deterministic, unless somebody's written one deliberately not to be. There's plenty of information online about how a hash table works, if you're curious about it. – Radiodef Aug 25 '17 at 03:19
  • 1
    What part of 'it makes no guarantees' don't you understand? – user207421 Aug 25 '17 at 03:24
  • 1
    @yshavit Interesting thought, but that doesn't seem to have been a motivation: https://stackoverflow.com/q/45222328/1553851 – shmosel Aug 25 '17 at 03:26
  • @shmosel Interesting, thanks for that link! That could because they solved that problem in Java 8 (I think) by having the linked list buckets turn into a balanced tree if it grows too big. I can't remember off hand if that's for all Comparables, or just string. Though now that I think of it, to solve it at the hash code level, you'd need to randomize String.hashCode, not HashMap. And you can't do that, because String.hashCode is documented and guaranteed. – yshavit Aug 25 '17 at 04:10
  • 1
    @yshavit I think it actually creates a tree for any key type based on the hashCode, falling back on Comparable or identityHashCode as a tiebreaker. – shmosel Aug 25 '17 at 04:21
  • leave unorderedness alone; that's what gives it O(1) instead of O(logn) – Dmytro Aug 25 '17 at 04:38

1 Answers1

0

You might want to check the documentation :

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

Vivick
  • 3,434
  • 2
  • 12
  • 25
  • 1
    OP quotes that exact sentence. :) – shmosel Aug 25 '17 at 03:08
  • Thanks for the quick response. So given that the `hashCode()` implementation is correct (i.e. doesn't change over time), the results will be consistent? I read the documentation but I find it a bit confusing, especially "it does not guarantee that the order will remain constant over time". That means I will get a different result if I retrieve outputs from the `HashSet`, let's say, 10 minutes later? – Dau Zi Aug 25 '17 at 03:09
  • 1
    Just saw that, but it makes no sense to me to ask if the order is guaranteed if it you already know that the documentation says the contrary – Vivick Aug 25 '17 at 03:09
  • I agree. Seems like a pretty direct answer. – shmosel Aug 25 '17 at 03:10
  • The mathematical concept of a set gives it away : there's no notion of iteration in a set, therefore the logarithmic representation should follow a similar trait (therefore no specific order over iteration) – Vivick Aug 25 '17 at 03:12
  • 1
    It all depends on how it is implemented, but the doc explicitly says that the order is not guaranteed so I would not risk myself to think of it as immutable/constant – Vivick Aug 25 '17 at 03:13
  • I understand mathematically, the concept of a set does not support the same output. To make my question clear, since the implementation for `HashSet` in Java is the same (assume I am using the same Java version), if I offer the exactly same input, it will give me the exactly same output? – Dau Zi Aug 25 '17 at 03:16
  • 1
    There's a chance it could do so, but I would not count on it as an expected and viable behavior. – Vivick Aug 25 '17 at 03:17