作者scuendless (scu)
看板EE_DSnP
标题[讨论] 有关hash
时间Tue Jan 11 00:46:24 2011
因为我一开始也不太了解
想了一阵子加上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)
1F:推 ric2k1:推一个!! 01/11 00:58
2F:推 hunallen:GOOD 01/11 01:51
3F:推 TommyKSHS:大推 01/11 01:57