Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1405636
  • 博文数量: 277
  • 博客积分: 2551
  • 博客等级: 少校
  • 技术积分: 3918
  • 用 户 组: 普通用户
  • 注册时间: 2011-02-21 22:46
文章分类

全部博文(277)

文章存档

2017年(3)

2016年(9)

2015年(65)

2014年(27)

2013年(85)

2012年(61)

2011年(27)

分类: LINUX

2015-05-08 08:27:56

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