Java HashSet and hashCode() 考題

最近面試的筆試題中關於HashSet的考題，測試面試者對於HashSet及Object.hashCode()的了解。

有一個類別Member如下。

Member

public class Member {

    private int id;

    public Member(int id) {
        this.id = id;
    }
    
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

}

則下面set.size()的印出的大小是多少？

Main

public class Main {

    public static void main(String[] args) {

        Set<Member> set = new HashSet<>();

        Member member = new Member(1);

        set.add(member);

        member.setId(2);

        set.remove(member);

        System.out.println(set.size()); // ?

    }

}

上面的答案是0，也就是set中的member最終被刪除了。

這題要能答對就要知道HashSet的運作機制。HashSet內部其實是利用HashMap的key來裝載加入的元素，物件的hashCode()值決定存放的bucket位置。

節錄HashSet原始碼如下：

HashSet

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }
    ...
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    ...
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    ...
}

若未覆寫hashCode()，則JVM預設以內部記憶體位址計算hash值，所以修改了member的屬性值也不影響其記憶體位置，所以set中的member被成功刪除。

不過考題的Member改為如下，也又是覆寫了hashCode()

Member

public class Member {

    private int id;

    public Member(int id) {
        this.id = id;
    }
    
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
    
    @Override
    public int hashCode() {
        return id; // 以id值做為hash值
    }
    
}

則結果大不相同，set的大小為1，也就是set中的member未被刪除，因為物件的hash值改以覆寫的hashCode()計算，也就不再以記憶體位置計算，而改以member.id的值計算。

因此修改member.id的值導致加入set的member的hash值(1)與用來刪除的member物件的hash值(2)不同，所以member沒被刪除。

---

原始題目類似如下。

Member

public class Member {

    private int id;

    public Member(int id) {
        this.id = id;
    }
    
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
    
    @Override
    public int hashCode() {
        return id; // 以id值做為hash值
    }
    
}

Main

public class Main {

    public static void main(String[] args) {

        Set<Member> set = new HashSet<>();

        Member member = new Member(1);
        set.add(member);

        for (Member m : set) {
            m.setId(2);
        }

        for (Member m : set) {
            set.remove(m);
        }

        System.out.println(set.size()); // 1

    }

}

• HashSet.remove not working