Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Order of elements in a hash collection

DZone's Guide to

Order of elements in a hash collection

· Java Zone
Free Resource

Learn how our document data model can map directly to how you program your app, and native database features like secondary indexes, geospatial and text search give you full access to your data. Brought to you in partnership with MongoDB.

While is it generally understood that keys or elements in a HashMap or HashSet occur in a pseudo random order, what is not obvious is that two collections with the same elements can be in different orders. This is because the capacity of the collection also determines the order the elements appear.

This can be important if you have only an Iterator to a Set. It is easy to assume the order will be the same and most of the time it will work (you can write unit tests with this assumption which will pass) However, if the Set has a different capacity (something you don't normally know or worry about) the order will change.

 

Find what order elements can appear in

The following test adds the same 11 elements to a HashSet, each time with a different collection and prints out all the combinations it finds.

 

@Test
public void testSetOrder() {
  Set<String> order = new HashSet<String>();
  Collection<String> elements = Arrays.asList(
                     "zero, one, two, three, four, five, six, seven, eight, nine, ten".split(", "));

  try {
  for(int i=1;i > 0;i*=2) {
    Set set = new HashSet<String>(i, 100.0f);
    set.addAll(elements);
    String str = set.toString();
    if (order.add(str))
      System.out.println("HashSet("+i+") order was "+str);
  }
  } catch(OutOfMemoryError ignored) { }
}

prints this output

 

HashSet(1) order was [ten, nine, eight, seven, six, five, four, three, two, one, zero]
HashSet(2) order was [eight, three, zero, ten, nine, seven, six, five, four, two, one]
HashSet(4) order was [three, zero, ten, two, eight, nine, seven, six, five, four, one]
HashSet(8) order was [three, ten, two, seven, five, four, zero, eight, nine, six, one]
HashSet(16) order was [ten, two, seven, five, nine, one, three, four, zero, eight, six]
HashSet(32) order was [ten, five, nine, one, zero, eight, six, two, seven, three, four]
HashSet(64) order was [ten, nine, one, zero, eight, six, three, four, five, two, seven]
HashSet(128) order was [ten, nine, zero, eight, three, one, six, four, five, two, seven]
HashSet(256) order was [nine, zero, six, ten, eight, three, one, four, five, two, seven]
HashSet(512) order was [six, four, five, seven, nine, zero, ten, eight, three, one, two]
HashSet(1024) order was [six, five, nine, eight, two, four, seven, zero, ten, three, one]
HashSet(2048) order was [eight, seven, zero, six, five, nine, two, four, ten, three, one]
HashSet(4096) order was [eight, seven, zero, six, five, nine, three, one, two, four, ten]
HashSet(8192) order was [eight, seven, zero, six, nine, four, five, three, one, two, ten]
HashSet(16384) order was [eight, zero, nine, five, three, two, ten, seven, six, four, one]
HashSet(32768) order was [zero, six, one, eight, nine, five, three, two, ten, seven, four]
HashSet(65536) order was [zero, eight, five, seven, four, six, one, nine, three, two, ten]
HashSet(131072) order was [nine, zero, eight, five, seven, four, six, one, three, two, ten]
HashSet(262144) order was [nine, five, seven, six, one, two, ten, zero, eight, four, three]
HashSet(524288) order was [nine, seven, six, one, two, ten, zero, four, five, eight, three]
HashSet(1048576) order was [nine, seven, six, one, two, ten, four, eight, three, zero, five]
HashSet(2097152) order was [seven, six, one, two, ten, five, nine, four, eight, three, zero]
HashSet(4194304) order was [six, one, two, ten, eight, seven, five, nine, four, three, zero]
HashSet(8388608) order was [six, one, two, ten, eight, five, nine, four, zero, seven, three]
HashSet(16777216) order was [six, one, two, ten, five, nine, four, zero, eight, seven, three]
HashSet(33554432) order was [six, one, two, ten, five, nine, four, zero, seven, three, eight]

As you can see almost every initial capacity has a different order (even for a relatively small number of elements)

Single note: with a capacity of 1 and a large load factor (to prevent it resizing the capacity), the HashSet becomes a linked list which shows object in reverse order. i.e. as there is 100% collisions.

 


As @Alex Zhang, notes, if you have small positive numbers (Byte, Short, Integer, Long) and you allow the capacity to grow naturally, you will get those numbers in order. However if you vary this a little the pattern breaks up.
Collection<Integer> col = Arrays.asList(-1, 1, 10, 100, 1000, 10000, 100000, 1000000);
for (int i = 1; i < 5000000; i *= 2) {
    Set<Integer> set = new HashSet<Integer>(i, 100f);
    set.addAll(col);
    System.out.println("HashSet(" + i + ") " + set);
}
prints
HashSet(1) [1000000, 100000, 10000, 1000, 100, 10, 1, -1]
HashSet(2) [1000000, 100000, 100, 10, 10000, 1000, 1, -1]
HashSet(4) [10000, 1000, 1, 1000000, 100000, 100, 10, -1]
HashSet(8) [1000, 1, 1000000, 100, 10, 10000, 100000, -1]
HashSet(16) [1000, 1, 100, 1000000, 10, 10000, 100000, -1]
HashSet(32) [1, 100, 10, 10000, 1000, 1000000, 100000, -1]
HashSet(64) [1, 10, 1000, 1000000, 100000, -1, 100, 10000]
HashSet(128) [1, 10, 1000000, -1, 10000, 1000, 100000, 100]
HashSet(256) [1, 10, 1000000, -1, 10000, 100, 1000, 100000]
HashSet(512) [1, 10, 1000000, 100, -1, 10000, 1000, 100000]
HashSet(1024) [1, 10, 1000000, 100, 10000, 100000, -1, 1000]
HashSet(2048) [1, 10, 1000000, 100, 1000, 10000, 100000, -1]
HashSet(4096) [1, 10, 100, 1000, 10000, 1000000, 100000, -1]
HashSet(8192) [1, 10, 100, 1000, 10000, 1000000, -1, 100000]
HashSet(16384) [1, 10, 100, 1000, 100000, 10000, 1000000, -1]
HashSet(32768) [1, 10, 100, 1000, 100000, 10000, 1000000, -1]
HashSet(65536) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]
HashSet(131072) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(262144) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(524288) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(1048576) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(2097152) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]
HashSet(4194304) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]

The Code

 

From http://vanillajava.blogspot.com/2011/09/order-of-elements-in-hash-collection.html

Discover when your data grows or your application performance demands increase, MongoDB Atlas allows you to scale out your deployment with an automated sharding process that ensures zero application downtime. Brought to you in partnership with MongoDB.

Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}