Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Can we predict the iteration order of hashset?

 
Helen Ma
Ranch Hand
Posts: 451
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Suppose we hash each string in String[] strs = {"1", "3", "1", "2"} into a hashset. When I iterate this hashset using a iterator, it always output 3 2 1.
I assume if I run the program in a different platform (eg different JVM, different OS), the output may be 1 2 3, 1 3 2 or 3 1 2 .
So if I am asked this question in the exam, I should say the ouput is unpredictable.

When I worked on the practice exam 4 in OCP Java SE 6 Programmer Practice Exams , there is a question like this:
give a String[] str = {"1", "3", "1", "2"}, put each of them in a hashset, a linked list, a tree map and a list , what will be the possible output if all of the data structures are iterated.
From my interpretation from the study guide, I cannot predict the output from hashset.

Anyway, my question is will the output be 1 2 3 or 3 2 1 or 2 1 3 or etc depending on the platform your JVM is running.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Helen Ma wrote:Anyway, my question is will the output be 1 2 3 or 3 2 1 or 2 1 3 or etc depending on the platform your JVM is running.

It's not dependent on anything. The output could be 1 2 3 or 3 2 1 or 2 1 3 or etc even on the same platform. As the javadoc says
no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time
 
Nitin Surana
Ranch Hand
Posts: 129
Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can't unless if you have implemented/overridded public int hashCode(){} in the object contained in the HashSet, in which case you already know the logic behind the arrangement and hence the order of iteration can be predicted.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nitin Surana wrote: the order of iteration can be predicted.

No it can't. Which you have just demonstrated. In some versions of Java it may be related to the hashCode of the objects contained in the HashSet, but in Java 7 it isn't, because the HashSet is backed by a LinkedHashMap so the itertion order will actually be the insertion order.

Edit: and even that's misleading, because the type of Map that backs the HashSet actually depends on which constructor you use. So it could be a HashMap as well. And the iteration order will then depend on the type of Set that is returned by the Map's keySet method.
 
Helen Ma
Ranch Hand
Posts: 451
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is the question from the book:
import java.util.*;
public class Bucket {
public static void main(String[] args) {
Set<String> hs = new HashSet<String>();
Set<String> lh = new LinkedHashSet<String>();
Set<String> ts = new TreeSet<String>();
List<String> al = new ArrayList<String>();
String[] v = {"1", "3", "1", "2"};
for(int i=0; i< v.length; i++) {
hs.add(v[i]); lh.add(v[i]); ts.add(v[i]); al.add(v[i]);
}
Iterator it = hs.iterator();
while(it.hasNext()) System.out.print(it.next() + " ");
Iterator it2 = lh.iterator();
while(it2.hasNext()) System.out.print(it2.next() + " ");
Iterator it3 = ts.iterator();
while(it3.hasNext()) System.out.print(it3.next() + " ");
Iterator it5 = al.iterator();
while(it5.hasNext()) System.out.print(it5.next() + " ");
} }
Which statements are true? (Choose all that apply.)
A. An exception is thrown at runtime.
B. Compilation fails due to an error on line 18.
C. "1 3 2" is only guaranteed to be in the output once.
D. "1 2 3" is only guaranteed to be in the output once.
E. "1 3 2" is guaranteed to be in the output more than once.
F. "1 2 3" is guaranteed to be in the output more than once.
G. "1 3 1 2" is guaranteed to be in the output at least once.
H. Compilation fails due to error(s) on lines other than line 18.

I think these :
tree set will output 1 2 3
hash set will output 3 2 1 / 1 2 3 / 1 3 2 .... (unpredictable)
linkedhashset will output 1 3 2
arraylist will output 1 3 1 2
Therefore c and d are not guaranteed as the hash set's output is unpredictable.
However, the book's answer is C D and G

Can anyone explain why?

 
Deepak Soni
Greenhorn
Posts: 10
Eclipse IDE Hibernate Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
exactly I have tried this problem with different inputs and it behave unpredictably .....so only G is a valid answer...
 
Nitin Surana
Ranch Hand
Posts: 129
Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
LinkedHashSet maintains the order of insertion.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic