散列 Hash

一、什么是散列？

散列 Hash是和顺序、链接和索引一样，是存储集合或者线性表的一种方法。

散列的基本思想是：以集合或线性表中的每个元素的关键字K为自变量，通过一个散列函数 h(K) 得到的结果，将这个结果解释为一块连续的存储空间（如数组）的地址（如数组下标），将这个元素存储到这个空间中。

h(K) 称为散列函数或者哈希函数，它实现了关键字到存储地址的映射。h(K)的值 称为散列地址或者哈希地址。存储空间是线性表进行散列存储的空间，所以称之为散列表或者哈希表。

二、冲突

如果出现一个待插入的元素的散列地址已经被占用，使得该元素无法直接存入到此单元中，这种现象成为冲突。

我们把不同关键字通过散列函数后得到相同的散列地址的元素成为同义词。

• 影响同义词冲突的三个因素：

1. 装载因子 a：指散列表中已存入元素数 n 和散列空间大小 m 的比值。a 越小时，冲突可能性越小，但是空间利用率越小。a 一般控制在0.6~0.9为宜。

2. 散列函数：选择适当的散列函数讲元素均分在各个区域。

3. 解决冲突的方法

三、散列函数

• 直接定址法
• 除留余数法
• 数字分析法
• 平方取中法
• 折叠法

四、处理冲突的方法

解决冲突的方法分为开放定址法和链接法两种。

开放定址法

开放定址法是从发生冲突的单元开始，按照一定的次序，从散列表中找出一个空闲的存储单元，把冲突元素插入到该单元。插入到该单元的元素叫非同义词元素。

线性探查法

从发生冲突的单元开始，依次寻找下一个空闲单元。

• 特点：

1. 容易造成元素的堆积。

平方探查法

探查序列为 d, d+(1^2), d+(2^2), d+(3^2), ...

• 特点

1. 可以避免堆积现象；
2. 无法探查到散列表上的所有单元，但至少可以探查到一半的单元。

双散列函数探查法

使用两个散列函数 h1 和 h2，若关键字通过第一个散列函数得出的下标 d 冲突的话，探查的增量为 h2(K)。

链接法

把发生冲突的同义词元素用单链表链接起来，散列表则保存他们的表头指针。

• 特点

1. 填充因子有可能会大于1；
2. 比开放定址法占用更多存储空间用于存储表指针。

对比

开放定址法处理冲突的平均查找长度 > 链接法 > 任何其他查找方法

五、散列存储的缺点

1. 计算散列地址需要花费时间，关键字不是整数还先要转换为整数；
2. 占用更多的存储空间，开放定址法的装载因子小于1，链接法则需要空间存储指针；
3. 只能按关键字查找，无法按非关键字查找。