ds9.3陆小马功钟浩.pptVIP

9.3 哈希表 9.3 哈希表 1. 哈希表 2. 哈希函数 3. 处理冲突的方法 4. 性能分析 1. 哈希表 根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。 2. 哈希函数 哈希函数：H(key) 构造方法： 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 常用除留余数法： H(key) = key MOD p 3. 处理冲突的方法 冲突：不同的关键字映射到相同的哈希地址。 处理冲突的方法： (1) 开放定址法 用H(key)⊕di，如：线性探测再散列： H(key)⊕1，H(key)⊕2，... (2) 再哈希法 H1(key)冲突，试用H2(key)，H3(key)，... (3) 链地址法 发生冲突的记录链成单链表。 (4) 建立公共溢出区 所有冲突记录存入溢出区。 构造哈希表举例 例：关键字{19, 14, 23, 1, 68, 20, 85, 9}，哈希函数H(key)=key MOD 11，用下列方法处理冲突，构造哈希表，并计算平均查找长度。 （1）开放定址法（线性探测再散列） （2）链地址法 方法：从空表开始，依次插入关键字构造哈希表。 0 1 2 3 4 5 6 7 8 9 10 例(1) 开放定址法构造哈希表 关键字：{19, 14, 23, 1, 68, 20, 85, 9} 哈希函数：H(key)=key MOD 11 处理冲突：开放定址法（线性探测再散列） 9 23 1 14 68 19 20 85 0 1 2 3 4 5 6 7 8 9 10 3 1 2 1 3 1 1 3 key 19 14 23 1 68 20 85 9 H(key) 8 3 1 1 2 9 8 9 +1 2 3 9 10 +2 4 10 0 查找长度 1 1 1 2 3 1 3 3 ASL=15/8 例 (2) 链地址法构造哈希表 关键字：{19, 14, 23, 1, 68, 20, 85, 9} 哈希函数：H(key)=key MOD 11 处理冲突：链地址法 1 23 68 14 9 85 19 20 0 1 2 3 4 5 6 7 8 9 10 /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ key 19 14 23 1 68 20 85 9 H(key) 8 3 1 1 2 9 8 9 查找长度 1 1 1 2 1 1 2 2 ASL=11/8 4. 性能分析 哈希表的查找性能 影响哈希表平均查找长度的因素： 哈希函数 处理冲突的方法 哈希表的装填因子（填满的程度） 哈希表查找的时间复杂度：O(1) 哈希表的平均查找长度时装填因子的函数，而不是 n 的函数。 不管 n 多大，总可以选择合适的装填因子，使平均查找长度限定在一个范围内。