CODEWITHSUNDEEP
java
Rishi
Rishi

Reputation: 224

Collections.sort Hashcodes

Why is the below code printing different hashcodes on calling collections sort method Kindly let me know why is this behaviour?

    List<Integer> list = new ArrayList<>();

    for (int i = 0; i < 10; i++) {

        list.add((int) (Math.random() *100));

    }

    System.out.println("Before List =" + list);

    System.out.println("object hashcode-1 =" + list.hashCode());

    Collections.sort(list);

    System.out.println("In >>> object hashcode-1 =" + list.hashCode());
    Collections.sort(list,new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            return (o1.intValue() > o2.intValue() ?-1:1);
        }
    });
    System.out.println("object hashcode-2 =" + list.hashCode());
    System.out.println("After List =" + list);
    Collections.sort(list,Collections.reverseOrder());
    System.out.println("object hashcode-3 =" + list.hashCode());
    System.out.println("Reverse Order List =" + list);

The output is:

Before List =[58, 12, 38, 36, 56, 78, 65, 70, 51, 63]
object hashcode-1 =545500024
In >>> object hashcode-1 =975071634
object hashcode-2 =1492547664
After List =[78, 70, 65, 63, 58, 56, 51, 38, 36, 12]
object hashcode-3 =1492547664
Reverse Order List =[78, 70, 65, 63, 58, 56, 51, 38, 36, 12]

Regards

Upvotes: 1

Views: 644

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533530

A List is an ordered collection. This means that a List with [1, 2] is not equal to a List [2, 1] nor should the hashCode() be the same (ideally)

When you sort the collection you change it's order and thus it's hashCode. Note this is not guarenteed for all types. e.g. all Long of the formula ((x + y) & 0xFFFFFFFF) + y << 32) have the same hashCode for the same value of x. This means you have a list of Long where each long has the same hashCode and thus the list of these numbers will have the same hashCode regardless of order.

List<Long> l1 = Arrays.asList(-1L, 0L, (1L << 32) + 1, (2L << 32) + 2);
List<Long> l2 = Arrays.asList((2L << 32) + 2, (1L << 32) + 1, 0L, -1L);
System.out.println(l1.hashCode());
System.out.println(l2.hashCode());

As all the Long use the hashCode of 0, the order doesn't change the hashCode.

923521
923521

Upvotes: 5

Eran
Eran

Reputation: 393841

ArrayList#hashCode (actually implemented in AbstractList) calculates the hash value based on the order of the elements of the list :

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

You can see that before adding the hash code of each element to the total, you multiply the previous total by 31. Adding the hash codes of the elements in a different order would give a different result.

Upvotes: 4

Related Questions