作者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