推 WSzc:感謝教授! 我發現我是被class A誤導 因為他的k = k()... 06/18 16:20
※ 引述《WSzc (WSzc)》之銘言：
: 想請問一下
: 在testHash.cpp中
: hash insert順序是
: hh.insert(10, 10.0);
: hh.insert(20, 20.0);
: hh.insert(10, 15.0);
: hh.insert(2, 2.0);
: hh.insert(5, 5.0);
: hh.insert(16, 16.0);
: 在.out是
: 2 --> 2
: 16 --> 16
: 10 --> 10
: 5 --> 5
: 20 --> 20
: 請問為什麼不是10 --> 10,15 而是只有 10 --> 10?
: hash不是會有collision讓它接在後面嗎?
Assume (k1, d1) has been in the Hash
and (k2, d2) is a HashNode to be inserted.
if (k2() == k1()) {
if (k2 == k1) return false; // cannot insert
else return true; // insert (k2, d2) after (k1, d1) in the SAME bucket
}
else ... // (k1, d1) and (k2, d2) are in different buckets
: 另外想請問
: 就是cache中不像hash有一個bucketNum() function來決定要插入哪個cacheNode
: 所以是我們可以自訂插入規則嗎? 還是一樣用key % bucketNum去決定?
: 這樣的話output出來的順序就會跟testHash.out不同...
: (像是.out這邊2被5蓋掉 如果規則不一樣 被蓋掉的node就不同了)
: 謝謝回答
啊, 你可能誤會 _size 的意思了...
這邊的 _size 是指 _cache array 的大小, 不是裡面有效 elements 的數目.
他的意思跟 _numBuckets 是很像的.
事實上除非你對每個 element 存個 valid bit 或是什麼的,
否則 Cache 是無法判斷它裡面的 element 是否為 valid
(比方說 _cache[0] = 0.0 <== 到底是 default 還是 garbage?)
所以, 就用 k() % _size 來決定 _cache index.
而 _cache 在印的時候就是每個 element 都印 (for (i = 0 ~ _size - 1)),
不管它是否 valid.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.40.13