[討論] 有關hash
因為我一開始也不太了解
想了一陣子加上singerlibra大的解說才豁然開朗
剛好剛跟hunallen討論了一下
想到幾個關鍵點
提供給還沒寫到的人一些參考~
或是寫完的人可以討論看看我的想法有沒有錯吧~
1. 不同的fanin透過hash function 可能 對應到相同的key值
2. 由於不可能窮盡所有可能的key值 都做一個bucket去裝他
所以老師給定的code裡面有k()%bkt_num這樣的處理
3. 也因此相同的key與不同的key都有可能被塞在同一個bucket裡面
(因為他們%之後一樣)
4. 被塞在bucket裡面的東西就是老師講義的slot
5. 因為同一個bucket裝了不同key值的slot, 當你在做overload key的==
的時候 你必須要進去bucket裡面 對所有的slot搜尋過
來確認新加進來的這組fanin 是不是已經裝在bucket裡面了
所以說他搜尋的時間是O(s)
莫約如此~
我自己也不知道有沒有錯|||
不過感覺是有hash到
有錯就請別人講一下吧~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.217
※ 編輯: scuendless 來自: 140.112.243.217 (01/11 00:48)
推
01/11 00:58, , 1F
01/11 00:58, 1F
推
01/11 01:51, , 2F
01/11 01:51, 2F
推
01/11 01:57, , 3F
01/11 01:57, 3F