關於HashSet 加入重覆物件卻成功加入的問題

[Bluesky7 ()]

class A{
        int a=0;
        public A(int va){a=va;}
        public boolean equals(Object o){
                A m=(A)o;
                return (a==o.a);
        }
        public String toString(){...return  a 的String}
}

class test{

        main(String[] argc)
        {
                HashSet<A> set= new HashSet<A>();
                set.add(new A(1));
                set.add(new A(2));
                System.out.println(set);
        }
}

結果印出來是 [1, 2] 第二次被成功加入了
可是SUN 的 Spec上明明定義set 重複的不會加入

More formally, adds the specified element, o, to this set if this set
contains no element e such that (o==null ? e==null : o.equals(e)).

可是現在看來 好像只有把address相同的才看成一樣 可是我的equals也overrinding了
也測過沒錯
我哪裡弄錯了嗎
請教板友 謝謝



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.107.75

> -------------------------------------------------------------------------- <

作者: qrtt1 (隱者) 看板: java
標題: Re: 關於HashSet 加入重覆物件卻成功加入的問題
時間: Thu Apr 27 17:51:29 2006

※ 引述《Jnaive (嘿嘿)》之銘言：
: ※ 引述《Bluesky7 ()》之銘言：
: : class A{
: :         int a=0;
: :         public A(int va){a=va;}
: :         public boolean equals(Object o){
: :                 A m=(A)o;
: :                 return (a==o.a);
: :         }
: :         public String toString(){...return  a 的String}
: : }
: : class test{
: :         main(String[] argc)
: :         {
: :                 HashSet<A> set= new HashSet<A>();
: :                 set.add(new A(1));
: :                 set.add(new A(2));
: :                 System.out.println(set);
: :         }
: : }
: : 結果印出來是 [1, 2] 第二次被成功加入了
: : 可是SUN 的 Spec上明明定義set 重複的不會加入
: : More formally, adds the specified element, o, to this set if this set
: : contains no element e such that (o==null ? e==null : o.equals(e)).
: : 可是現在看來 好像只有把address相同的才看成一樣 可是我的equals也overrinding了
: : 也測過沒錯
: : 我哪裡弄錯了嗎
: : 請教板友 謝謝
: 在head first java 那本書上看到過這問題
: class A 還需要overrinding過另一個hashCode()這個method
: 物件相等，似乎是先檢查物件的hashCode，然後才呼叫equal
: 都相等，才算物件相等
: 不是很確定…有錯請指正

import java.util.HashSet;

public class TasteHashSet {
        public static void main(String[] args) {

                Object o = new Object() {
                        public int hashCode() {
                                System.out.println("Call hashCode()");
                                return super.hashCode();
                        }

                        public boolean equals(Object obj) {
                                System.out.println("Call equals()");
                                return super.equals(obj);
                        }
                };
                HashSet hash = new HashSet() {
                        public boolean add(Object o) {
                                System.out.println("Do Add A Element");
                                return super.add(o);
                        }
                };

                hash.add(o);
        }

}


俺好奇到底誰先呼叫, 是equals還是hashCode
寫了程式測了一下, 結果..hahaha


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.26.34.20

> -------------------------------------------------------------------------- <

作者: tkcn (小安) 看板: java
標題: Re: 關於HashSet 加入重覆物件卻成功加入的問題
時間: Thu Apr 27 23:14:51 2006

※ 引述《lin1000 (你是研究生嗎)》之銘言：
:                 hash.add(o);
:                 hash.add(o);
:                 hash.add(o1);

HashSet 可以放同一個物件兩次嗎? :P

我沒有去看 HashSet 的 source code
但是我猜想流程大概是以下這個樣子

1. 呼叫傳入物件的 hashcode()，計算出物件存放的位址

2a. 如果該位址尚未存放其他物件，則將傳入的物件存入。接著結束這個 method。

2b. 若該位址已經有物件，並且是同一個物件 (使用 == )，則結束這個 method。

3. 呼叫 equals()，若回傳 true 不做任何處理，
   回傳 false，則存放這個物件
   ( 我不知道 HashSet 如何處理 hashcode 相同的存放問題，
     可能是存再下一個位址，
     或著是在同一個位址使用一個 collection 存放兩個以上的物件 )

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.70.65
※ 編輯: tkcn            來自: 220.131.70.65        (04/27 23:15)

> -------------------------------------------------------------------------- <

作者: lin1000 (你是研究生嗎) 看板: java
標題: Re: 關於HashSet 加入重覆物件卻成功加入的問題
時間: Thu Apr 27 23:48:24 2006


tkcn , good guess!!! thank you for your response
after tracing JDK(1.4.2) HashSet I have some answer here.
First of all, Inside HashSet there is a HashMap to store objects.

※ 引述《tkcn (小安)》之銘言：
: ※ 引述《lin1000 (你是研究生嗎)》之銘言：
: :                 hash.add(o);
: :                 hash.add(o);
: :                 hash.add(o1);
: HashSet 可以放同一個物件兩次嗎? :P
: 我沒有去看 HashSet 的 source code
: 但是我猜想流程大概是以下這個樣子
: 1. 呼叫傳入物件的 hashcode()，計算出物件存放的位址

     that's right! HashMap use a static method to calculate int hash

     int hash = hash(k);

    static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }
: 2a. 如果該位址尚未存放其他物件，則將傳入的物件存入。接著結束這個 method。
    that's right! and will return null to the the caller.
: 2b. 若該位址已經有物件，並且是同一個物件 (使用 == )，則結束這個 method。

    inside HashMap there is a static inner class Entry to wrap data

    transient Entry[] table;  <----- instance variable

    static class Entry implements Map.Entry {
        final Object key;
        Object value;
        final int hash;
        Entry next;   <------ Entry itself has a referece to another one
    }

    so we can say that JDK use linked list way to handle address collision
    if there is a "same" key object , replace the value object by
    a new value object.
    finally return the value object which has been replaced (the old one)

    As to the definition of "same" key object, we can see the following code
    from jdk(1.4.2) HashMap source :

            if (e.hash == hash && eq(k, e.key)) {  <------ this line
                Object oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }

            static boolean eq(Object x, Object y) {
                return x == y || x.equals(y);
            }


: 3. 呼叫 equals()，若回傳 true 不做任何處理，
:    回傳 false，則存放這個物件
:    ( 我不知道 HashSet 如何處理 hashcode 相同的存放問題，
:      可能是存再下一個位址，
:      或著是在同一個位址使用一個 collection 存放兩個以上的物件 )

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.178.206.10
※ 編輯: lin1000         來自: 202.178.206.10       (04/28 00:12)