CODEWITHSUNDEEP
javasethashsetmutation
Tslat
Tslat

Reputation: 23

When exactly do sets in Java mutate?

We all know that unsorted Sets don't guarantee order, and that they can mutate and change.

My question is, how often does this happen, and what causes it?

If I were to occasionally grab the first element from a Set, would it be reliably pseudo-random?

Upvotes: 1

Views: 359

Answers (3)

Stephen C
Stephen C

Reputation: 719307

My question is, how often does this happen, and what causes it?

Mutation happens whenever the application calls a mutating operation; e.g. add, remove, etcetera. It doesn't happen spontaneously.

(How often? As often as you call a mutating method ... of course.)

If I were to occasionally grab the first element from a Set, would it be reliably pseudo-random?

No. It would most likely be a poor source of "randomness".

While this depends on what Set class you are using, mutations to a Set typically do not change the iteration order of the elements significantly ... or in many cases, at all. In the vast majority of cases, a "random" small mutation to a set won't change what gets returned as the first element.

Upvotes: 1

resueman
resueman

Reputation: 10613

The most important thing to keep in mind is that Set is not an implementation in Java. It's just an interface. And the only mention of ordering it makes in its documentation just states that it makes no guarantees.

The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).

This means you can't assume anything about the order of a Set, unless you know what the implementation is. Implementers are free to do anything from keeping it sorted, to having a background threading running which randomizes the order every few seconds.

If you look at the Javadocs for various Sets, you can see that the guarantees vary, from LinkedHashSet

[The iteration order] is the order in which elements were inserted into the set

to TreeSet

The elements are ordered using their natural ordering

to HashSet

makes no guarantees as to the iteration order of the set

Within the bounds of those descriptions, the Sets are free to order themselves however they want. That means the well defined ones only need to reorder when something (such as an insertion or removal) causes them to need a new ordering to fulfill their contract. The ones without a guarantee don't promise anything, but presumably have some form of internal structure which allows for fast lookups, which would a) likely remain fairly stable, and b) quite possibly favor certain items over others for being first. They also might not, but you can't make an assumption either way.

Upvotes: 1

rsutormin
rsutormin

Reputation: 1649

For instance adding new element in HashSet can reorder all elements that were added there before. It could happen when you reach capacity (take a look at this place in java sources: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#772)

In TreeSet you might want to add new element with compareTo placing this element in the middle of set and also changing the order.

Upvotes: 1

Related Questions