作者abcb1 (好怕自己的未來...)
看板Prob_Solve
標題[問題] 找hash function的問題
時間Wed Nov 19 23:13:44 2008
假如現在有一串20 bit長的資料
裡面有10個是1 10個是0
ex:01111000011000101101 等等之類的
我想建一個hash table
如果直接拿資料的值來當位址的話 就需要2^20個entry
可是這樣很多的空間就都被浪費了
如果用ㄧ般的mod 或者其他hash function又會有碰撞的情況
想請問各位
有沒有什什麼好的hash function 或者編碼的方法
可以使用較少的記憶體又不會有碰撞的情況發生
感謝~~~
--
Everything is allright
Tomorrow"ll be fine
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.136.80
1F：推 ledia:hash 就是拿空間換時間呀~ 不然用 C(20,10)=184756 encode 11/20 00:51
2F：→ ledia:一般 hash collision 就是用 chain 或是向後 shift 來解決 11/20 00:52
3F：推 ykjiang:如果不考慮執行效率，你可以用 CRC 當 hash value 11/21 11:58
4F：→ ykjiang:如果知道資料特性的話，可以量身打造 11/21 11:59
5F：→ abcb1:3q~~~ 11/23 20:02