[理工] [資結] Quadratic and Double hashing

[dunkjames (Firefighter)]

1. quadratic probing的定義 (H(X)+i^2) mod B ; i=1.2.3...(B-1)/2

假設bucket有10個 是不是說i最多只能代到4? (就算i代5就可以將資料置入slot也不算)

補充: 每個BUCKET只有一個SLOT

ex: 給定 13.19.23.10.33.15.29.14

我的問題是最後一個14擺不進去 (如果i 最多只能到4 )!! 那該怎麼半呢?


2. Double hashing, quadratic, Linear probing 都是 open addressing mode 嗎?



3. 我知道Chain是屬於close addressing mode.
 另外假定依序給予13.33.23
在第三個bucket中的link list會如何串聯?

(1) 13=>33=>23 //X兔說如果不講究這樣也算對

(2) 23=>33=>13 //這好像是課本寫法

如果遇到非選題 該寫哪一種呢 真的兩者皆可嗎?


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.81.133.121
→ shooo:3. 23->33->13 才符合LINK LIST操作
→ shooo:2. Yes
推 rayway30419:為什麼這樣寫才符合linked list操作?
推 KiroKu:因為linked list insert是從頭吧 1我覺得是設計問題 如果有
→ KiroKu:10個slot就應該i再1~10能都跑一變
忘記說 slot都只有一個
※ 編輯: dunkjames       來自: 42.73.128.182        (01/21 23:44)
推 wheels:1.這個定義有問題，有些給的是+和-都要試，所以題目應該會
→ wheels:給它的定義，如果作到結束都沒辦法放，那就是data lost了。
→ wheels:就回答"所有探測格皆已被使用"，14的資料lost或者有excep等
推 wheels:3.通常都寫(2)的作法，因為insert只花O(1)的時間。
→ wheels:2.open就是可以用到別格去，這三種都會用到別人的格子。
→ LightChen23:洪逸上課說過若擺不進去直接在題目中說明即可
→ dunkjames:謝謝各位先進
→ sneak: 3.通常都寫(2)的作 https://daxiv.com