[討論] perfect hashing

[sandy4444 (質樸)]

面試題目

給N個(<1000) integer

給出一個 (min) perfect hashing

讓 N 個數儲存到 size 為 M 的array

(N<=M 他說可以的話讓 N=M)

達成之後 find 複雜度是O(1)

請問各位大大會選擇什方法

ps 小弟當下是用

0 = a * X^N + b * X ^(N-1) ....
1 = a * X^N + b * X ^(N-1) ....
.
.
.
N-1

把值帶進 X 然後去解 a b c ..

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 174.77.39.55
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1416206839.A.E07.html
※ 編輯: sandy4444 (174.77.39.55), 11/17/2014 15:06:18
推 pika0923: 如果輸入integer的最大bit數可以視為常數的話
→ pika0923: 也許可以用bit值的字典樹型式來實現?
→ sandy4444: int 是 unsigned 32 bit 可以多給點 hint 嗎
推 pika0923: 想像一棵二元樹 遇0走左子樹 遇1走右子樹
→ pika0923: 對於每個輸入數 讓他走這棵樹 路上沒節點就創節點
→ pika0923: 走到底作標記(hash值 可用一個counter累加)
→ pika0923: 這結構的空間正比於輸入數個數 查找為32次符合O(1)
→ sandy4444: 簡單明瞭!!! 但這樣的缺點是什麼?
→ FRAXIS: 上網搜尋Minimal Perfect Hashing 應該有現成的方法吧..