作者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)