Understanding HashCode of sorted & unsorted ArrayList

Question

Im working on a small Project and have encountered a problem(?) I cant really explain. This is my code:

====Main=====

    Beacon b1 = new Beacon("192.168.0.12", 72.0);
    Beacon b4 = new Beacon("192.168.0.13", 72.0);
    Beacon b2 = new Beacon("192.168.0.24", 84.0);
    Beacon b3 = new Beacon("192.168.0.5", 64.0);
    ArrayList<Beacon> alBeacons = new ArrayList();

    alBeacons.add(b4);
    alBeacons.add(b2);
    alBeacons.add(b1);
    alBeacons.add(b3);

    Room room = new Room("Testroom", alBeacons);

====Beacon====

public class Beacon {
String sIP;
private int ID = 0;
private Double RSSi;



public Beacon(String sIP, double RSSi){
    this.sIP = sIP;
    this.RSSi = RSSi;
    setID();
}

private void setID(){
    String sTemp[] = sIP.split("\\.");
    this.ID = Integer.parseInt(sTemp[sTemp.length-1]);

}

public String getsID(){
    return String.valueOf(ID);
}

public int getID(){
    return ID;
}
}

====Room====

    public Room(String sName, ArrayList<Beacon> alBeacons){
    System.out.println("Unsorted: " + alBeacons.hashCode());
    for(Beacon b: alBeacons){
        System.out.println(b.getID());
    }
    alBeacons.sort(new Comparator<Beacon>() {

        @Override
        public int compare(Beacon o1, Beacon o2) {
            return o1.getID() - o2.getID();
        }
    });
    System.out.println("Sorted: " + alBeacons.hashCode());
    for(Beacon b: alBeacons){
        System.out.println(b.getID());
}

}

Now my Problem I have is that in the unsorted state, no matter how the Beacons have been inserted into the ArrayList, I always get the same HashCode(), 1498918675. As soon as I sort them, I get a different HashCode, which makes sense. But the Problem now is that, depending on how the ArrayList was sorted in the first place, I get a different HashCode after sorting it. Is this inherent to .sort(), or is my fix for real number sorting breaking it?

EDIT: Here are some output examples:

Unsorted: 1498918675
13
24
12
5
Sorted: 341854239
5
12
13
24

Unsorted: 1498918675
24
5
12
13
Sorted: 638040239
5
12
13
24

Unsorted: 1498918675
12
5
24
13
Sorted: 1060992495
5
12
13
24

Can you clarify what your goal is in sorting the list of beacons? — Tim Biegeleisen, Jun 10 '17 at 10:18
What hashCode are you talking about? The hashCode of the list? Why are you surprised that its hashCode changes depending on what is contains? And why do you care? — JB Nizet, Jun 10 '17 at 10:18
@TimBiegeleisen Im working on a Indoor Location Engine and for speed I am giving each Room a hash. When I need to look if someone is in the Room I can just compare the hashCode. — Ricardo, Jun 10 '17 at 10:31
@JBNizet I am not surprised. For example in Main I give the ArrayList b4, b2, b1, b3. If I do alBeacons.hashCode(), I get 1498918675. If I change order in which the bs get added into the ArrayList, I still get 1498918675 from hashCode(). The problem is that I want to sort the ArrayList first. Afterwards, for the above example, I get the hashCode 341854239. If I now change the order in which the bs get input, sort it and do hashCode() again, I get a completely different haschCode(). — Ricardo, Jun 10 '17 at 10:35
You can't use the hashCode alone as an indication of what is in the list. Hashcodes are not unique and are not guaranteed to have any specific properties beyond compatibility with `equals()` when correctly implemented. — user207421, Jun 10 '17 at 10:59

score 2 · Accepted Answer · answered Jun 10 '17 at 10:43

The hashCode of a List must (contract inside the interface) be :

int hashCode = 1;
for (E e : list)
    hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;

So, the ordering of elements is important in determining the hashcode : getting a different hashcode for a sorted or unsorted list is normal.

However you state that 'depending on how the ArrayList was sorted in the first place, I get a different HashCode after sorting it' : so basically you state that :

case 1: You start with [b, a, c] which is sorted to [a, b, c] you get hashCode X
case 2: You start with [c, b, a] which is sorted to [a, b, c] you get hashCode Y

This shouldn't happen if the hashcode method of your Beacon class depends on the fields of the Beacon. You haven't overriden hashCode thus it's the basic implementation which is "typically implemented by converting the internal address of the object into an int" (from the javadoc).

To solve your problem, you should define your own hashCode inside Beacon :

public int hashCode() {
    final int prime = 31;
    int res = (sIP != null) ? sIP.hashCode() : 1;
    res = res * prime + ID;
    return res * prime + Double.hashCode(RSSi);
}

Ah, very nice. I was expecting the Hash to work out of the sorting aswell as the internal Variables of the ArrayList. Looks like I'll might need to implement my own .equals() from what I can take out of this answer: https://stackoverflow.com/a/27609/5471598 Thanks a lot for the clarification! — Ricardo, Jun 10 '17 at 10:50
@Redimo yup you should always override equals if you define your own hashCode ;) — Ronan Dhellemmes, Jun 10 '17 at 10:56
I've just created a separate method equals(Beacon b), as any other comparison shouldnt work. And considering the size of possible Beacons per Project(~80 at absolute maximum), the shouldnt be any colissions. Thanks alot for the help, learned quite alot from that answer! — Ricardo, Jun 14 '17 at 08:33

score 0 · Answer 2 · answered Jun 10 '17 at 10:26

0

Hash code of list calculated depending upon the content and order.

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

answered Jun 10 '17 at 10:26

gati sahu

2,576
2
10
16

The problem is that alBeacons unsorted gives always the same hashCode(). If I sort it, I always get a different hashCode() depending on how unsorted it was beforehand. – Ricardo Jun 10 '17 at 10:38

2 Answers2