-1

For this question, why does it print out [1,2,3] in that specific order since I thought HashSets are not ordered, I would have thought it printed out [1,2,3] in any order. I am aware it gets rid of duplicates. Is it because this question converts from a list -> HashSet -> list?

import java.util.*;

class Try
{
    public static void main(String args[]) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(3);
        list.add(3);
        list.add(3);
        list.add(2);
        list.add(2);
        list.add(1);
        Set<Integer> set = new HashSet<Integer>(list);
        List<Integer> list_1 = new ArrayList<Integer>(set);
        System.out.println(list_1);
    }
}
futuredeveloper
  • 11
  • 4

3 Answers3

2

It's somewhat by chance that the numbers are in their natural order, but the order of the List's elements is dictated by the order that the Set iterates over its elements.

HashSets have no defined order of iterating their elements, but it is influenced by the hash code of each element. In the case of Integer objects, the hashCode() method returns its own value. The hash code determines which bucket the element is stored in, and since HashSets start out with 16 buckets, the remainder of the operation i % 16 on values 1, 2 and 3 is just 1, 2 and 3, so that's the bucket they'll be in. Iteration over elements is done bucket at a time. Each bucket has only one element in it - bucket 1 has the element 1, etc. That's why they are in order.

For larger quantities of Integers, the neat coincidence would not apply and elements would be in pseudo random order, but in fact determined by the implementation of both the hash code of each element, the current number of buckets, the precise algorithm used to chose the bucket and finally the order in which elements were added - each bucket has a List of elements within it (and if the List grows too large, a TreeSet).

Bohemian
  • 389,931
  • 88
  • 552
  • 692
  • I see okay. I got this question in a java quiz I did today. What was the correct answer then, It prints out [1,2,3] in that specific order or [1,2,3] in any order? Since you mention the hashCode() influences the order – futuredeveloper Mar 21 '22 at 22:39
  • 1
    @futuredeveloper See last paragraph. The tl;dr is that in the general case the order is pseudo random. In this case, the question can discover how much detailed knowledge of Java a candidate has, eg knowing that the hash code implementation of Integer is its own value, some knowledge of how HashMaps work, and also knowing that this kind of code would not result in elements being naturally ordered in the general case. – Bohemian Mar 21 '22 at 22:44
1

Hash sets are unordered which means that when new ArrayList<Integer>(set) is called the Java compiler makes no promises that the resulting list will be in order. In your case it so happens that it is in ascending order, compiling with a different java compiler, or even the same java compiler at a different time could result in a different ordering.

As an example editing your code slightly to be:

class Try {
  public static void main(final String args[]) {
    final List<Integer> list = new ArrayList<Integer>();
    for (int i = 10; i > -10; i--) {
      list.add(i);
    }
    final Set<Integer> set = new HashSet<Integer>(list);
    final List<Integer> list_1 = new ArrayList<Integer>(set);
    System.out.println(list_1);
  }
}

Results in an output on my machine of:

[0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, -8, 8, -9, 9, 10]

Clearly this is not in order.

Hence when converting a hash set into a list it is not safe to assume that the result will have some order

Alex
  • 79
  • 4
0

Hash sets are unordered which means that when new ArrayList(num) is called the Java compiler makes no promises that the resulting list will be in order. In your case it so happens that it is in ascending order, compiling with a different java compiler, or even the same java compiler at a different time could result in a different ordering.

souhail
  • 1