※ 引述《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