Contain function() in hashSet

By | January 23, 2016
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

Today when I tried to solve a problem, I came across a weird problem. Look at below code:

public class test {

    static class Point {
        int a;
        public Point(int a) {
            this.a = a;
        }
    }

    public static void test1() {
        Point element = new Point(1);
        HashSet<Point> hs = new HashSet<Point>();
        hs.add(element);
        element.a = 2;
        System.out.println(hs.contains(element));
    }

    public static void test2() {
        HashSet<Integer> element = new HashSet<Integer>();
        HashSet<HashSet<Integer>> hs = new HashSet<HashSet<Integer>>();
        hs.add(element);
        element.add(2);
        System.out.println(hs.contains(element));
    }

    public static void main(String[] args) {
        test1();
        test2();
    }

}

test1 prints true, and test2 prints false. It is confusing. My friend junmin explained me the reason. Check code from JDK:

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

We can see contains() function both checks hashCode() and equals() function. Only when 2 functions return true, it will return true.

Accordingly, if I change the Point class to below, test1() will return false too.

static class Point {
    int a;
    public Point(int a) {
        this.a = a;
    }
    public int hashCode() {
        return a;
    }
}

Ideally, the element in HashSet() should be immutable. Or if we want to change, we should do remove, update, put operations.

Or another way is that we should guarantee that hashCode for new element should be the same as before, and new element should equal to before. But this is actually a worse way. Remember ideally, element in HashSet should be immutable.

 

  • junmin liu

    the reason for the hash key is immutable is that if the key is being updated, which causes the hashCode() result changes, then the hash table is not only valid for that key.