随笔 - 13  文章 - 36  trackbacks - 0
<2009年10月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(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 阅读(1900) | 评论 (5)编辑 收藏