網頁

2020/8/21

Java HashSet and hashCode() 考題

最近面試的筆試題中關於HashSet的考題,測試面試者對於HashSetObject.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的值導致加入setmember的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

    }

}

沒有留言:

張貼留言