|
|
知识路径: > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 哈希表(Hash 表) >
|
|
被考次数:8次
|
|
被考频率:
中频率
|
|
总体答错率:
44%
|
|
知识难度系数:
|
|
考试要求:
掌握
|
|
相关知识点:11个
|
|
|
|
|
根据设定的哈希函数和处理冲突的方法,将一组关键字映射到一个有限的、连续的地址集(区间)上,并以关键字在地址集中的"像"作为记录在表中的存储位置,这种表称为哈希表,这一映射过程称为哈希造表或散列,所得的存储位置称为哈希地址或散列地址。
|
|
|
对于哈希表,主要考虑两个问题:一是如何构造哈希函数;二是如何解决冲突。
|
|
|
|
常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
|
|
|
|
常见的处理冲突的方法有开放地址法、链地址法、再哈希法、建立一个公共溢出区。
|
|
|
|
|
(1)虽然哈希表在关键字与记录的存储位置之间建立了直接映像,但由于冲突的产生,使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程,因此,仍须以平均查找长度衡量哈希表的查找效率。
|
|
|
(2)查找过程中须与给定值进行比较的关键字的个数取决于哈希函数、处理冲突的方法和哈希表的装填因子3个因素。哈希表的装填因子定义为
|
|
|
|
式中,α表示哈希表的装满程度。直观地看,α越小,发生冲突的可能性就越小;反之,α越大,表中已填入的记录越多,再填记录时,发生冲突的可能性就越大,则查找时,给定值需与之进行比较的关键字的个数也就越多。
|
|
|