哈希表简单介绍

概念

在顺序结构以及平衡树中，元素关键字与他们存储的位置并没有直接的映射关系，从而会影响查找关键字的效率，顺序结构中查找关键字的时间复杂度为O（N），平衡树查找关键字的时间复杂度为O（log2^N）。

最理想的搜索方法——只搜索一次就能找到关键字。

如果有一种数据结构，能够使得关键字根据某种映射规则，将关键字和它的存储位置一一映射起来，那么在查找时通过映射规则就能够很快将关键字查找出来。

在这个数据结构中

插入元素：

根据某种特定的映射规则，找到关键字在存储结构中的位置，然后插入。

搜索元素：

根据某种特定映射规则，将求得的函数值作为元素的存储位置，然后与结构中此位置的元素比较，若关键字相等，则搜索成功。

该方式就被称为哈希或者散列，使用的映射函数就为哈希函数或者散列函数，构造出来的存储结构就为哈希表或者散列表。

比如：数据集合{1，7，6，4，5，9}

如果哈希函数设置为hash(key)=key%10，则数据在存储结构内会呈现以下关系

该方法查找每一个数只需要进行一次比较，效率很高，但是这种存储方式在实际使用的时候会导致很多的空间浪费，有些空间为空，被没有被有效利用起来，所以实际使用时模数的取值一般为不超过存储结构容量的最大质数。

哈希冲突

哈希冲突的原因是由于，当有一组数据需要通过相同的映射规则存储到到一个存储结构时，此时就有可能两个数得到的hash(key)的值相同，但是又不可能将两个数字同时存储在一个空间里面，这时就造成了哈希冲突，或者叫哈希碰撞。

此时把具有相同哈希地址的不同关键字记为“同义词”。

发生哈希表该如何处理呢？

处理方法

拉链法

比如：数据集合{1，7，6，4，5，9，12，25，36}

加入存储结构容量为7，则哈希函数为hash(key)=key%7。

这种情况就将哈希地址相同的数据元素依次链接到之前元素的后面。

成功查找的平均查找长度 ASL成功=（6*1+2*2）/9=1.11

ASL失败=9/7=1.286。

装填因子=表中记录数/散列表长度。

装填因子越大表示表装得越满。

直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

由于这是一个一次函数，所以对于每一个不相同的元素对应的值就不相同，所以哈希地址不会存在冲突。

优点：简单、均匀

缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

开放定址法

线性探测法

意思就是通过哈希函数处理后得到的关键字哈希地址如果存在冲突，那么就依次往后面去找空位将这个数放进去。