| 散列表中双重hash函数的设计与分析 |
| |
| 引用本文： | 罗永龙,黄刘生. 散列表中双重hash函数的设计与分析[J]. 计算机工程与应用, 2002, 38(12): 59-60 |
| |
| 作者姓名： | 罗永龙 黄刘生 |
| |
| 作者单位： | 1. 安徽师范大学计算机系,芜湖,241000;中国科技大学计算机系,合肥,230027
2. 中国科技大学计算机系,合肥,230027 |
| |
| 基金项目： | 国家自然科学基金资助(编号:10071001)，国家973项目资助(编号:G1998030403)，安徽省自然科学基金资助(编号:01046103) |
| |
| 摘 要： | 开放地址法是散列表中处理冲突的常用方法,它的三种基本实现方式是线性探测、二次探测及随机探测,文章指出了这三种方式的不足;介绍了双重散列函数的构造方法并证明了其探测序列有Θ(m2)种;对双重散列处理碰撞时堆积很少产生进行了分析。
|
| 关 键 词： | 散列 碰撞 探测 堆积 序列 检索 |
| 文章编号： | 1002-8331-(2002)12-0059-02 |
| 修稿时间： | 2002-03-01 |
Design and Analysis of the Double Hash Function of a Hash Table |
| |
| Luo Yonglong , Huang Liusheng. Design and Analysis of the Double Hash Function of a Hash Table[J]. Computer Engineering and Applications, 2002, 38(12): 59-60 |
| |
| Authors: | Luo Yonglong Huang Liusheng |
| |
| Affiliation: | Luo Yonglong 1,2 Huang Liusheng 21 |
| |
| Abstract: | Open addressing is a frequently used strategy to accommodate collisions.It has three essential ways that lin-ear probing,quadratic probing and random probing.This paper points out the disadvantages of the three methods,intro-duces the methods of construction of the double hash function,proves it hasΘ(m 2 )probing sequences and concludes that the clustering will seldom happen when collision is solved through using double hash function. |
| |
| Keywords: | hash collision probing clustering sequence search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
