随笔 - 13  文章 - 36  trackbacks - 0
<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

     摘要: 哈希结构

C++博客 Alex-Lee 2009-10-21

哈希结构在处理大量数据时具有很好的优势,在插入,查询,删除等操作上具有常量的时间复杂度O(1)。使用范围是数据集具有自然数上的关键字域(不是自然数也需要能够转为自然数域),通过哈希函数将关键字映射到寻址数组的槽。由于关键字域U[0...n]与寻址数组[0...m]中,总是n>m,也就是说,总有多个关键字对应一个槽。这个碰撞就需要通过一些方法改变。可以通过拉链法(链表法)和开放地址法。对于拉链法中,链表不能太长,否则影响速度,最好控制在10个元素之内,这样就要去寻址数组长度m>= n/10,这样就会多消耗些空间。为了让每个链表长度基本一致,就需要  阅读全文
posted @ 2009-10-22 00:31 Alex-Lee 阅读(1867) | 评论 (5)编辑 收藏