哈希散列函数有两种情况，一种是key映射到同一个槽，一种是同一个key映射到多个槽
映射到同一个槽的散列方法:
除余散列法,乘法散列法,全域散列法,完全散列法(多次散列),这些算是直接寻址
映射到不同槽的散列方式:
线性试探法,二次试探法,双重试探法,这些都是开放寻址
除余散列中 hash(key) = key mod m,m取一个接近元素集合的大小的质数，而不是集合大小
乘法散列 key*(0~1)*大数,然后溢出的结果取模,大数按照Knuth的说法取(√5-1)/2 黄金分割点
这个大数是接近某个值(类似2^32)的黄金分割位置,这个值应该是接近原始元素集合的
一个2^n
Hash函数主要是将key映射的索引符合随机分布
阅读(1876) | 评论(0) | 转发(0) |
