一、hash表的基本概念和优缺点比较

      hash表又称哈希表 ，是一种数据结构，与链表、二叉树有很大区别。

1、hash表优缺点

优点：能够在常数级的时间复杂度上进行查找，并且插入数据和删除数据简单。（Hash未满的时候速度很快）

缺点：不支持排序，一般比用线性表存储需要更多时间，并且记录的关键字不能重复

2、与链表比较

链表：查询上表中的数据从头开始遍历，直到查到或者查找失败。

hash：根据存储数据特定关键字，然后根据关键字直接查询想要得到数据。

hash存储位置通常称作Hash地址。

Hash地址是由关键字经过特定的 hash函数运算得到。

3、当关键字重复就会产生数据冲突。

二、hash表的构造方法

１、直接定址法

例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

           但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

          eg:f(x) = 5x+10

            x代表的就是年龄，而f(x)获取到的就是对应地址，是取Hash地址与关键字构成的线性函数。

2、平方取中法

适用关键字是数字的情况，将关键字平方然后取其中间的几位作为Hash地址。

3、数字分析法

比如同龄人的出生年月，由于前几位数字的重复几率较大，所以造成冲突的几率较高，所以尽量不取前几位。

4、折叠法

将关键字分割成相同的几段数字（最后一部分可以不同），然后将得到的几段数字叠加（进位舍去）作为Hash地址，折叠法

eg：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，

如果一本书的编号为1234-5678-321,可以将其分为{12,34,56,78,32,1}。而Hash地址则是这几个数之和。

5、除留取余法

如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，

然后对关键字进行取余运算，f(x) = x%p。

在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，

p一般取不大于m的最大质数。

6、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

f(x)=random(x) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

三、冲突处理

1、开放定址法

关键字冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，

当碰到一个空的单元时，则插入其中。

eg：一组关键字{13，25，23，38，34，6，84，91}，

Hash表长为14，Hash函数为f(x)=x%11，当插入13，25时可以直接插入，而当插入23时，地址1被占用了，

因此沿着地址1依次往下探测(探测步长可以根据情况而定)，直到探测到地址3，发现为空，则将23插入其中。

2、再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

3、链地址法

采用数组和链表结合的方式，HashMap中就是采用这种方式存储Hash地址，原理是将Hash地址（经过关键字计算的值）相同的记录存在同一个链表中，

而每张表的表头序号就是新的Hash地址。

４、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

 

 

 

 

参考博文：