数据结构和算法——哈希表 Hash Table (二）_数据结构的链地址法处理中n是什么?

散列表

散列表使用某种算法操作(散列函数)将键转化为数组的索引来访问数组中的数据，这样可以通过Key-value的方式来访问数据，达到常数级别的存取效率。现在的nosql数据库都是采用key-value的方式来访问存储数据。

散列表是算法在时间和空间上做出权衡的经典例子。通过一个散列函数，将键值key映射到记录的访问地址，达到快速查找的目的。如果没有内存限制，我们可以直接将键作为数组的索引，所有的操作操作只需要一次访问内存就可以完成。但这种情况不太现实。

Hashmap应用

1. cocos2d 游戏引擎 CCScheduler
2. ux 内核bcache。 缓存加速技术，***D固态硬盘作为高速缓存，提高慢速存储设备HDD机械硬盘的性能
3. hash表在海量数据处理中有广泛应用。如海量日志中，提取出某日访问百度次数最多的IP
4. Java 中HashMap实现。编程语言中HashMap是如何实现的呢? 说说 Java ， Golang
5. redis hash结构， set通常也是基于Hash结构实现

哈希表常见操作

1. put(key, value) 插入或修改操作。
2. get(key) 获取哈希表中特定位置的元素。
3. remove(key) 删除哈希表中特定位置的元素。
4. isEmpty() 如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false。
5. size() 返回哈希表包含的元素个数。
6. resize(value) 对哈希表进行扩容操作。

哈希表（HashTable）优缺点

哈希表优点

• 哈希表可以提供非常快速的插入-删除-查找操作；
• 无论多少数据，插入和删除值都只需要非常短的时间，即O(1)的时间级。实际上，只需要几个机器指令即可完成；
• 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。

哈希表缺点

• 哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大 ）来遍历其中的元素。
• 通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素。

哈希表的构建

在初中的数学课本中学习过函数的相关知识，给定一个 x，通过一个数学公式，只需要将 x 的值带入公式就可以求出一个新的值 y。
哈希表的建立同函数类似，把函数中的 x 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。即：

数据的哈希地址=f（关键字的值）
…

• 哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。
  f（）是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。

例如，这里有一个电话簿（查找表），电话簿中有 4 个人的联系方式：

张三 13912345678
李四 15823457890
王五 13409872338
赵六 13805834722

假如想查找李四的电话号码，对于一般的查找方式最先想到的是从头遍历，一一比较。而如果将电话簿构建成一张哈希表，可以直接通过名字“李四”直接找到电话号码在表中的位置。

在构建哈希表时，最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为：每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。这时会发现，张三和赵六两个关键字的姓的首字母都是 Z ，最终求出的电话号码的存储位置相同，这种现象称为冲突。在设计哈希函数时，要尽量地避免冲突现象的发生。

对于哈希表而言，冲突只能尽可能地少，无法完全避免。

散列函数

散列函数就是将键转化为数组索引的过程。且这个函数应该易于计算且能够均与分布所有的键。

散列函数最常用的方法是除留余数法。这时候被除数应该选用素数，这样才能保证键值的均匀散布。

散列函数和键的类型有关，每种数据类型都需要相应的散列函数；比如键的类型是整数，那我们可以直接使用除留余数法；这里特别说明下，大多数情况下，键的类型都是字符串，这个时候我们任然可以使用除留余数法，将字符串当做一个特别大的整数。

int hash = 0;
for (int i=0;i<s.length();i++){
    hash = (R*hash +s.charAt(i)%M);
}
1
2
3
4

还有，比如下面的：

Hash hashCode(char *key){
    int offset = 5;
    Hash hashCode = 0;
    while(*key){
        hashCode = (hashCode << offset) + *key++;
    }
    return hashCode;       
}
1
2
3
4
5
6
7
8
9

使用时 hashCode(key) & (size-1) 就可以得到一个 size-1 范围内的hash值

当然，还有其他的散列函数，如平方取中法, 随机数法等。

哈希函数的构造：
常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

冲突碰撞解决

hash 表有一个特性， 随着元素越来越多， 新插入一个元素发生hash冲突的次数就会越来越多， 查找一个元素的速度也会越来越慢。

不同的关键字得到同一个散列地址f(key1)=f(key2)，即为碰撞 。这是我们需要尽量避免的情况。常见的处理方法有：

• 开放定址法（线性探测法）
• 链地址法（拉链法）
• 再哈希法
• 建立一个公共溢出区

开放定址法
使用hash table剩下空间。遇到冲突时顺着原先的hash address找到下一个空闲地址然后插入。
这种方法有一个显著问题：空间不足怎么解决？
这个时候可以使用链地址法

H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量）

当得出的哈希地址产生冲突时，选取以下 3 种方法中的一种获取 d 的值，然后继续计算，直到计算出的哈希地址不在冲突为止，这 3 种方法为：

• 线性探测法：d=1，2，3，…，m-1
• 二次探测法：d=12，-12，22，-22，32，…
• 伪随机数探测法：d=伪随机数
  例如，在长度为 11 的哈希表中已填写好 17、60 和 29 这 3 个数据（如图 2（a） 所示），其中采用的哈希函数为：H（key）=key MOD 11，现有第 4 个数据 38 ，当通过哈希函数求得的哈希地址为 5，与 60 冲突，则分别采用以上 3 种方式求得插入位置如图 2（b）所示：
  

注释：在线性探测法中，当遇到冲突时，从发生冲突位置起，每次 +1，向右探测，直到有空闲的位置为止；二次探测法中，从发生冲突的位置起，按照 +12，-12，+22，…如此探测，直到有空闲的位置；伪随机探测，每次加上一个随机数，直到探测到空闲位置结束。

链地址法
如果遇到冲突，会在原地址新建一个空间，然后以链表节点的形式插入到该空间。
将大小为M的数组中的每个元素指向一条链表，链表中的每个节点都存储了散列值为该元素索引的键值对。每条链表的平均长度是N/M，N是键值对的总个数。如下图：

哈希函数：

添加操作：

1. 通过hash函数得到hashCode
2. 通过hashcode得到index
3. 如果index处没有链表，建立好新结点，作为新链表的首结点
4. 如果index处已经有链表，先要遍历看key是否已经存在，如果存在直接返回，如果不存在，加入链表头部

删除操作：

1. 通过hash函数得到hashCode
2. 过hashcode得到index
3. 遍历链表，删除结点

上面如果看不懂，可以继续参看如下示例：

将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函数为：H(key)=key MOD 13，使用链地址法所构建的哈希表如图

链地址法的优缺点：

优点：

1. 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
2. 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
3. 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
4. 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

** 再哈希法**
当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，直到冲突不再发生。

建立一个公共溢出区
建立两张表，一张为基本表，另一张为溢出表。基本表存储没有发生冲突的数据，当关键字由哈希函数生成的哈希地址产生冲突时，就将数据填入溢出表。

参考：数据结构与算法之哈希表 HashTable 散列表
哈希表（散列表）及哈希表处理冲突的方法
数据结构与算法(七)-哈希表(HashTable)