数据结构——散列表

参考视频：懒猫老师-数据结构-(60)散列表(哈希表)_哔哩哔哩_bilibili

思路：在存储位置和关键码之间建立一个确定的对应关系。

概念

1、散列表：连续的存储空间

2、散列函数：将关键码映射到适当位置的函数

3、散列地址：由散列函数所得的存储地址

散列技术既是一种存储技术也是查找技术。

散列函数的设计方法

1、直接定址法

散列函数是关键码的线性函数，即H(key)=a*key+b

使用情况：事先知道关键码，且关键码集合不是很大连续性好

2、除留余数法（重要）

通常情况下，哈希表的长度n通常选取比元素个数大的质数，以此来减少冲突。

此方法为最简单，最常用的方法，并且不要求事先知道关键码的分布。

3、数字分析法

根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址（学号常用）。

4、平方取中法

5、折叠法

将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。

适用于关键码位数很多的情况

解决冲突的办法

1、开放地址法（闭散列表）

由关键码得到的散列地址一旦产生了冲突，就去寻找一个空的散列地址，并将记录存入。

寻找下一个空的散列地址的方法：

①线性探测法

元素发生冲突时，后来的元素不断向后退一格

②二次探测法

两个元素发生冲突时，后来的元素先向后试探，如果不行的话在向左试探，都不行的话那就先后向左右试探2的n次方。

③随机探测法

2、拉链法（开散列表）

散列查找的性能分析

影响产生冲突的因素

1、散列函数是否均匀

2、处理冲突的方法

3、散列表的装载因子