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