散列表

散列表的查找：

基本思想：记录存储位置和关键字之间的对应关系——hash函数

散列函数H（key）= k;

优点：查找效率高

缺点：空间效率低

散列表若干术语：

散列方法(杂凑法)
选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放;

查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成

功。
散列函数（杂凑函数）：散列函数中使用的转换函数。

冲突：不同的关键码映射到相同的散列位置

在散列查找方法中，冲突是不可避免的，只能去尽量减少。

key1不等于key2，但是H（key1）=H（key2）

同义词：具有相同函数值的多个关键字。

散列函数的构造方法：

使用散列表要解决好两个问题:

1)构造好的散列函数

(a)所选函数尽可能简单，以便提高转换速度;

(b)所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。

2)制定一个好的解决冲突的方案

查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

构造散列函数考虑的因素：

1.执行速度

2.关键字的长度

3.散列表的大小

4.关键字的分布情况

5.查找频率

根据元素集合的特性构造：

● 要求一: n个数据原仅占用n个地址虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。

● 要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

构造方法：

1.直接定址法

2.数字分析法

3.平方取中法

4.折叠法

5.除数留余法

6.随机数法

直接定址法：

除数留余法

处理冲突的方法：

1.开放地址法

2.链地址法

3.再散列法

4.建立一个公共溢出区

开放地址法：

基本思想：有冲突时就去寻找下一个的散列地址，只要散列表足够大，空的散列地址总能

找到，并将数据元素存入。

二次探测法：（重点）

链地址法：
基本思想：相同散列地址的记录链成一个单链表

链地址法建立散列表的步骤：

● Step1:取数据元素的关键字key,计算其散列函数值(地址)。若该地址对应的链表为空，则

将该元素插入此链表;否则执行Step2解决冲突。

● Step2: 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链

表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

链地址的优点：

1.非同义词不会冲突，无聚集现象

2.链表上结点空间动态申请，更适合表长不确定的情况；