CODEWITHSUNDEEP
javacollectionsset
Manikandan A
Manikandan A

Reputation: 11

Why set insert the item in ordered?

Actually Set is not an ordered one. I just create the set and insert the numbers 5,2,10.
Wen it is printed in the console, it prints as 2,5,10.

Why since set is not ordered?

Upvotes: 0

Views: 80

Answers (5)

Siva Kumar
Siva Kumar

Reputation: 2006

Set is the Interface. It only indicates avoid duplicate entity of the collection.

HashSet internally uses Hashmap. Normally hashmap uses hashcode. So It wont return in ordered way. If you want insertion order you will use LinkedHashMap.

Upvotes: 0

enrico.bacis
enrico.bacis

Reputation: 31504

Set is just an interface, assuming that you are talking about HashSet (because it's where this happens), it doesn't keep them sorted. For example:

HashSet<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(16);
System.out.println(set);

Output

[16, 1]

This is because an HashSet uses the hashcode function to compute the index where the item will be stored in an array-like structure. This way, since the hashcode never changes, it can extract the element from the correct index computing again the hashcode and checking the cell at that index.

The hashcode function converts most classes to an integer:

System.out.println(new Integer(1).hashCode());      # 1
System.out.println(new Integer(1000).hashCode());   # 1000
System.out.println("Hello".hashCode());             # 69609650

Each class can define its own way to compute the hashcode and Integer returns itself. As you can see numbers get big soon, and we don't want to have an array with 1000 cells just to save the two integers. To avoid the problem we can create an array with n elements and then use the remainder of the hashcode divided by n as the index.

For example if we want to find the index for 1000 in an array of 16 elements:

System.out.println(new Integer(1000).hashCode() % 16);   # 8

So our dictionary will know that the integer 1000 is at index 8. That's how HashSet is implemented.

So, why [16, 1] is not ordered? That's because HashSet are created with 16 elements as capacity at the beginning (when not differently specified), and grow as needed (more on this here).

Let's compute the index to store the data having key = 2 and key = 9 in a dictionary with n = 8:

System.out.println(new Integer(1).hashCode() % 16);   # 1
System.out.println(new Integer(16).hashCode() % 16);  # 0

This means that the array that contains the dictionary data will be:

| index | value |
|-------|-------|
|   0   |  16   |
|   1   |   1   |
|   2   |       |
|   3   |       |
|   4   |       |
|   5   |       |
|   6   |       |
|   7   |       |
|   8   |       |
|   9   |       |
|  10   |       |
|  11   |       |
|  12   |       |
|  13   |       |
|  14   |       |
|  15   |       |

Iterating over it, the order will be the one presented in this representation, so 16 will be before 1.

Upvotes: 0

Ruchira Gayan Ranaweera
Ruchira Gayan Ranaweera

Reputation: 35557

Set is an interface while it has several implementations. HashSet is not guaranteed your insertion order(not ordered). LinkedHashSet preserve insertion order and TreeSet give you a sorted set(sorted set).

Then you insert 5,2,10 to HashSet you can't guaranteed the same order.

Upvotes: 0

Simon Richter
Simon Richter

Reputation: 29598

This is because this speeds up queries for whether a certain element is part of the set.

The difference is that this behavior is not guaranteed. It may be beneficial to keep small sets ordered for fast lookup, but switch to a hash based implementation once a certain number of elements has been reached, at which point elements would suddenly be sorted by hash value.

Upvotes: 2

ortis
ortis

Reputation: 2223

Set is just an interface. Ordering will depend on implementation. For example TreeSet is an ordered implementation of Set.

Upvotes: -1

Related Questions