散列表的查找

特点 Features

. 散列，也称哈希 Hash

. 不是基于关键字查找；而是先利用散列函数处理关键字得到数据元素的地址，再根据地址查找

. 大脑是做索引的，不是做存储的

key → Hash(key) → Location

关键字空间 → 地址空间

基本术语 Items

. 散列地址：数据元素对应的存储地址

. 散列函数：处理关键字，建立起数据元素和存储地址确定的对应关系

. 散列表：地址连续的存储空间；通常使用数组表示，散列地址就是散列表数组的下标/索引

. 冲突/同义词：不同的关键字处理后可能得到同一个散列值

散列函树 Hash Function

1. 数字分析法

2. 平方取中法

3. 折叠法

4. 取余%

...

已知给定哈希函数Hash(key) = key % 5，求关键字集合{3, 15, 22, 30}对应的哈希表

Hash	0	1	2	3
key	15	30	22	3

关键字30的处理

1. 开发地址法；如果相邻单元 - 1为空，则存入

2. 链地址法；所有冲突的关键字以链表的形式挂载与当前地址；再根据关键字额外指定的标识进行查找

已知给定哈希函数Hash(key) = key % 13，求关键字集合{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}对应的哈希表