哈希表

我们储存数据有没有面临1~1亿随机存有1W （不等）个数的时候呢？

这时候如果直接储存就有可能造成大量内存的浪费。

这时就需要一个算法将地址压缩至1W 的范围。

平时如果直接储存的话可能觉得直接用个什么 index 依次++ 不就好了吗。

是啊，但是这里还面临查找的问题。

所以就需要利用hash函数来查找记录的地址了。

Hash 函数的一种方法是对哈希表长度进行取模，那么这时有会有所得数字相等的情况，但你一个地址不能存放两个值啊，这就被称为冲突。

这种情况是一种理想情况。

构造哈希函数有不同的构造方法：

一：直接定值法

如果本身数据是基本连续的，那么可以用这样的形式来寻求地址。但如果数据有大量的不连续分布就将造成内存的浪费。

二：除留余数法

取关键字 k 处以哈希表长度m 来计算地址。即。

这是一种较简单、常用的方式。关键是选好长度m 尽量避免冲突的产生，研究表明m 取值为素数时，冲突较少。

三：平方取中法

即取关键字平方后的中间几位数作为哈希表的地址（可取模）

例如

四：折叠法

将关键字分隔成位数相同的几部分，用这几部分的和作为哈希表的地址。适用于位数较多的情况，如身份证号。

五：数值分析法

顾名思义，找规律，发现数据之间的玄学奥秘。（厉害的不行）

如：观察得数据的某几位取值较为集中，取不集中的几位组成数字作为地址。

以上就是几种构造哈希函数的方法。

那么之前有提到有冲突产生，怎样解决呢？

处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，则再求下一个，依次类推。直至新的哈希地址不再发生冲突为止。

常用的处理冲突的方法有开放地址法、链地址法两大类。

一：开放地址法

其中又有

（1）线性探测：（最坏为（1+m）* m / 2）

（2）平方探查：

二：链地址法

把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。