哈希的概念
哈希是一种搜索结构，不过哈希搜索不同于顺序搜索和二叉搜索的是：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储方式，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
哈希的搜索效率可高达O(1)。
常见的哈希函数

直接定制法

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

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

适合查找比较小且连续的情况
除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的的质数p作为除数，按照哈希函数：Hash(Key) = Key % p(p<=m),将关键码转换成哈希地址

例：



如果按照上述哈希方式，向集合中插入元素56，会出现什么问题？
哈希冲突
哈希冲突就是不同的关键字计算出了相同的哈希地址，这种现象也称为哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
解决哈希冲突最常见的方法是：闭散列和开散列

今天先来看看闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被填满，说明哈希表中必然还有空位置，那么可以把Key存放到表中“下一个”空位中去。
那如何寻找下一个空余位置

线性探测

当发生哈希冲突时，从冲突的位置开始，依次继续向后探测，直到找到空位置为止。

例：


二次探测

发生哈希冲突时，二次探查法在表中寻找“下一个”空位置的公式为：Hi = H0 + 2*i +1（i = 1，2，3…），H0是通过关键码Key计算得到的位置，Hi是Key实际的存储位置。

例：



已经清楚了解决哈希冲突的一些方法，现在就来看看具体的代码如何实现

哈希表中的位置可以分为三种状态：存在，空，删除，为什么要引入删除状态呢？因为因为删除一个元素后，我们把这个位置的状态置为DELEE，规定这种状态和存在是一样的，不能再在这个位置插入新的元素了，为什么不直接置为空是因为，如果置为空，认为这个位置是没有元素的，那刚刚发生哈希冲突的元素就找不到了。
例：


【插入】

使用哈希函数找到待插入元素在哈希表中的位置
如果该位置中没有元素（是空/删除状态）则直接插入新元素；如果该位置中有元素且和待插入元素相同，则不用插入；如果该位置中有元素但不是待插入元素，则发生哈希冲突，使用线性探测/二次探测找到下一个空位置，插入新元素。

具体代码：

HashTable.h    //头文件

#ifndef __HASHTABLE_H__
#define __HASHTABLE_H__

#include<stdio.h>
#include<assert.h>

#define MAX_SIZE 10

typedef int HTDataType;
typedef enum{EMPTY,EXIST,DELETE}State;
typedef struct HTElem
{
	HTDataType _data;
	State _state;
}HTElem;

typedef struct HashTable
{
	HTElem _ht[MAX_SIZE];
	int _size;//哈希表中有效元素的个数
}HT;

void InitHashTable(HT* pHT);
int InsertHashTable(HT* pHT, HTDataType data);
int DeleteHashTable(HT* pHT, HTDataType data);
int FindHashTable(HT* pHT, HTDataType data);
int EmptyHashTable(HT* pHT);
int SizeHashTable(HT* pHT);
int HashFun(HTDataType data);

#endif //__HASHTABLE_H__

HashTable.c //源文件
#define _CRT_SECURE_NO_WARNINGS 1

#include"HashTable.h"

void InitHashTable(HT* pHT)
{
	assert(pHT);
	int i = 0;
	for (i = 0; i < MAX_SIZE; i++)
	{
		pHT->_ht[i]._state = EMPTY;
	}
	pHT->_size = 0;
}

int InsertHashTable(HT* pHT, HTDataType data)
{
	int i = 0;
	assert(pHT);
	//防止数据堆积
	if (pHT->_size * 10 / MAX_SIZE > 7)
		return 0;

	//1.计算哈希地址
	int hashAddr = HashFun(data);
	//2.找存储位置
	while (EMPTY != pHT->_ht[hashAddr]._state)
	{
		if (pHT->_ht[hashAddr]._state == EXIST && data == pHT->_ht[hashAddr]._data)
			return 0;

		else
		{
			线性探测
			//hashAddr++;
			越界==超过MAX_SIZE
			//if (hashAddr == MAX_SIZE)
			//	hashAddr = 0;

			//二次探测
			i++;
			hashAddr = hashAddr + 2 * i + 1;
			if (hashAddr>MAX_SIZE)
				hashAddr %= MAX_SIZE;  //这次越界了就不能置0了，万一i很大了，2*i就大于MAX_SIZE了，永远都不能进入哈希表中了，但取模又回到原来的位置了
		}
	}
	//3.插入元素
	pHT->_ht[hashAddr]._data = data;
	pHT->_ht[hashAddr]._state = EXIST;
	pHT->_size++;
}

int FindHashTable(HT* pHT, HTDataType data)
{
	int i = 0;
	assert(pHT);
	int hashAddr = HashFun(data);
	while (EMPTY != pHT->_ht[hashAddr]._state)
	{
		if (pHT->_ht[hashAddr]._state == EXIST && data == pHT->_ht[hashAddr]._data)
			return hashAddr;
		/* //线性探测
		hashAddr++;
		if (hashAddr == MAX_SIZE)
			hashAddr = 0;*/
		//二次探测
		i++;
		hashAddr = hashAddr + 2 * i + 1;
		if (hashAddr>MAX_SIZE)
			hashAddr %= MAX_SIZE;
	}
	return -1;
}

int DeleteHashTable(HT* pHT, HTDataType data)
{
	assert(pHT);
	int ret = FindHashTable(pHT, data);
	if (-1 != ret)//找到data了
	{
		pHT->_ht[ret]._state = DELETE;
		pHT->_size -= 1;
		return 1;
	}
	return 0;
}

int EmptyHashTable(HT* pHT)
{
	if (pHT == NULL)
		return 0;
	return 0 == pHT->_size;
}

int SizeHashTable(HT* pHT)
{
	if (NULL == pHT)
		return 0;
	return pHT->_size;
}

int HashFun(HTDataType data)//求哈希地址
{
	return data % MAX_SIZE;
}

test.c //测试文件
#define _CRT_SECURE_NO_WARNINGS 1

#include"HashTable.h"

int main()
{
	HT pHT;
	InitHashTable(&pHT);
	InsertHashTable(&pHT, 23);
	InsertHashTable(&pHT, 33);
	InsertHashTable(&pHT, 44);
	InsertHashTable(&pHT, 43);
	InsertHashTable(&pHT, 54);
	InsertHashTable(&pHT, 3);
	DeleteHashTable(&pHT, 33);
	int ret = FindHashTable(&pHT, 33);
	if (-1 != ret)
	{
		printf("该数在哈希表中\n");
	}
	else
	{
		printf("该数不在哈希表中\n");

	}

	InsertHashTable(&pHT, 33);

	return 0;
}

哈希表是个啥？
小白： 庆哥，什么是哈希表？这个哈希好熟悉，记得好像有HashMap和HashTable之类的吧，这是一样的嘛？😊
庆哥： 这个哈希确实经常见😂，足以说明它是个使用非常频繁的玩意儿，而且像你说的HashMap和HashTable之类的与哈希这个词肯定是有关系的，那哈希是个啥玩意啊，这个咱们还是得先来搞明白啥是个哈希表。😎
我们看看百科解释吧：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

怎么样？看到这个，你知道哈希表是什么了嘛？
小白： 我之前是对哈希表一窍不通啊，不过看了这个百科的解释，我知道如下这些关于哈希表的简单知识点：
1、哈希表其实也叫散列表，两个是一个玩意，英文是Hash Table
2、哈希表是一个数据结构
这两个概念是比较清晰的，至于其他的说什么映射函数叫做散列函数，存放记录的数组叫做散列表这个就有点模糊了，尤其说存放记录的数组称为散列表，那意思是哈希表是个数组？🤣
庆哥： 首先你说的很清晰的两点说的是很准确的，哈希表也叫做散列表，这只不过是叫法而已，英文单词是Hash table，看到这个英文单词基本上就能猜到，哈希表其实就是直接根绝英文单词音译过来的，至此你应该知道了啥是哈希了吧，对于另外一点，那就很重要了，那就是哈希表其实是一种数据结构。
要知道数据结构有很多中，每一种都有各自的特点，那么哈希表既然也是一种数据结构，那它有什么特点呢？按照百科的解释，我们大致能知道：可以根据一个key值来直接访问数据，因此查找速度快
对了，你知道最基本的几个数据结构中，哪个的查询效率是最高的嘛？
小白： 据我所知，应该是数组吧，我们可以直接使用数组下标来访问数据，因此查询效率是很高滴😁
庆哥： 对，非常对，哈希表其实本质上就是一个数组 。
小白： 那为啥还叫哈希表呢？🤣，哈希表肯定有啥特别的吧，为啥本质上是一个数组呢？
哈希表本质是数组？
庆哥： 必须滴啊，哈希表本质上是个数组，只能说它的底层实现是用到了数组，简单点说，在数组的这个基础上再捯饬捯饬，加工加工，变得更加有特色了，然后人家就自立门户，叫哈希表😂
小白： 这是咋个回事啊🤣
庆哥： 为什么说哈希表的本质是个数组呢？那就得看看，哈希表是怎么来实现的了，一般来说啊，实现哈希表我们可以采用两种方法：
1、数组+链表
2、数组+二叉树
简单点就有这么两种方式，其实说白了，无论哪个都是必须有数组啊，都是再数组的基础上取搞其他的，而且比如第一种数组+链表的形式，本质上是出现哈希冲突的一种解决办法，使用链表存放，所以综合起来叫做数组+链表的方式来实现一个哈希表，另外数组中一般就是存放的单一的数据，而哈希表中存放的是一个键值对，这是个区别吧！
小白： 停！！！有点迷糊🤣，什么哈希冲突，什么玩意儿啊😂
庆哥： 🤪，好吧好吧，我说的有点着急了😂，你就记住，哈希表在本质上就是个数组就ok了。
小白： 可是我还是像知道为啥啊？🤣
庆哥： 别着急啊，咱慢慢来讲，另外在百科上有这么一个例子，可以帮助你更好的理解哈希表是个啥，它是这样说的：

怎么样？看的懂嘛？
小白： 反正是有点模糊，这其中提到的函数关系啊，关键字啊，散列函数还有什么函数法则的有点迷迷糊糊的🤣
哈希表的几个概念
啥是散列函数
庆哥： 确实，这都是哈希表中很重要的几个概念，那咱就先搞懂这几个概念吧，我用大白话给你说说这个例子。😎
比如说，我现在给你个电话本，上面记录的有姓名和对应的手机号，我想让你帮我找王二的手机号是多少，那么你会怎么做呢？
小白： 这样啊，那我就挨个找王二呗？😀
庆哥： 确实可以，那么你有没有想过，如果这个王二是在最后几页，那你去岂不是前面几页都白找了，有没有更快的方式呢？
小白： 也是哦，那这样的话，是不是可以按照人名给分个类，比如按照首字母来排序，就abcd那样的顺序，这样根据王二我就知道去找w这些，这样不久快很多了😁
庆哥： 的确，我们可以按照人名的首字母去弄一个表格，比如像这样：

你看，假如现在我让你去帮我找王二的手机号，你一下子就能找到，不用再挨个的去查找了，这效率就高的多了，那么现在重点来了，人家本来叫王二，你为啥用一个w来标记人家呢？让你找王二为啥你不直接找王二而是去找w呢？
小白： 这个？😅，用w可以更快速的去定位到王二啊😂
庆哥： 说的很对，我们取姓名的首字母作为一个标志，就可以很快的找到以这个字母开头的人名了，那么王二也就能更快的被我们找到，我们也不用再费力气去找什么张二和李二的，因为人家的名字首字母都不是w。
小白： 那必须啊，这个方法好吧😁
庆哥： 对对对，你说到点子上了，那就是方法二字，这里我们就是采用一种方法，什么方法呢？那就是取姓名的首字母做一个排序，那么这是不是就是通过一些特定的方法去得到一个特定的值，比如这里取人名的首字母，那么如果是放到数学中，是不是就是类似一个函数似的，给你一个值，经过某些加工得到另外一个值，就像这里的给你个人名，经过些许加工我们拿到首字母，那么这个函数或者是这个方法在哈希表中就叫做散列函数，其中规定的一些操作就叫做函数法则，这下你知道什么是散列函数了吧😎
小白： 嗯呢，这下真的是很清楚了，说白了，不就是给我一个值，经过捯饬一下，变成另外一个值吗？花个图的话就是这个样子：

哈哈，是不是这样？😂
庆哥： 简单来说就是这样滴😎，咋样，这下知道什么是散列函数了吧？
关键值key是啥？
小白： 这下知道了，很清楚😎，那这个关键字key是个啥玩意？
庆哥： 这个也好理解啊，就像你画的这个图，1是怎么得出来得，是不是根据未加工之前得101得出来得，这个加工过程其实就是个散列函数，而丢给它的这个101就是这个关键值啊，为啥叫它关键值嘞，那是因为我们要对它做加工才能得出我们想要的1啊，你说它关不关键😂
小白： 哦哦，原来是这样啊，这下就明白啦！对了，我现在有这样的一个理解，你看看对不对啊，那就是哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值，这个值就是数据存放的位置，我们就可以根据这个值快速的找到我们想要的数据，是不是这样啊？😂
庆哥： 说的很正确😎，那你现在对之前那个百科的例子懂了嘛？
小白： 嗯呢，这下懂了😀
庆哥： 嗯呢，那就好，其实吧，上面的那中情况并不好，为啥嘞？你想啊，王二在那个位置，如果再来个王三呢？人家的首字母也是w啊，这咋办，位置被王二占了，那王三咋办？这就是哈希冲突啊，撞衫啦🤣
小白： 阿西吧，又是哈希冲突，它到底似乎个啥玩意啊😂
庆哥： 不着急，咱们继续来探究哈希表。
再探哈希表
庆哥： 我们在之前已经知道了哈希表的本质其实是个数组，数组有啥特点啊？
小白： 数组嘛，那就是下表从0开始啊，连续的，直接通过下标访问，比如下面这样：

有一个数组a，我们可以直接通过a[1]的形式来访问到数值7，所以查询效率很高。
庆哥： 完全正确，那么哈希表本质上是个数组，那它跟这个类似吗？我们来再深入探究一下，首先看个图：

这张图可是信息量很大啊，你看出来个啥了嘛？
小白： 这个？我看到了哈希函数，这是啥？它跟散列函数有啥区别啊？还有Entry是个什么鬼😂，还有键值对🤣，蒙圈啊😥
哈希函数
庆哥： 别蒙圈啊，我来仔细跟你说说，其实这个哈希函数就是我们之前说的散列函数，为啥嘞？这就跟哈希表也叫做散列表一样啊，你叫作散列表的时候有个散列函数，那你叫哈希表的时候，也得有个哈希函数啊，这样才公平嘛😀，咋样，知道了吧？
小白： 我去，原来是这么回事啊🤣，那键值对跟Entry嘞？
键值对和Entry
庆哥： 这个可是值得好好说道说道，我们知道哈希表本质上是个数组，难道就跟数组的基本使用那样，存个数值，然后通过下表读取之类的嘛？当然不是啦，对于哈希表，它经常存放的是一些键值对的数据，啥是键值对啊，就是我们经常说的key-value啊，简单点说就是一个值对应另外一个值，比如a对应b，那么a就是key，b是value，哈希表存放的就是这样的键值对，在哈希表中是通过哈希函数将一个值映射到另外一个值的，所以在哈希表中，a映射到b，a就叫做键值，而b呢？就叫做a的哈希值，也就是hash值。
咋样，这块明白了嘛？
小白： 嗯嗯，明白的，庆哥继续！😎
庆哥： 那好，我们继续，键值对说的简单点就是有一个key和一个value对应着，比如这张图里的学生信息：

学生的学号和姓名就是一个键值对啊，根据这个学号就能找到这个学生的姓名，那啥是Entry嘞，我们都知道键值对，在很多语言中也许都有键值对，说白了就是个大众脸啊，咋弄，在咱jdk中可不能那么俗气，不能再叫键值对了，叫啥嘞，那就叫Entry吧😂
咋样，知道啥是键值对和Entry了吧！
小白： 必须滴啊，讲的那么生动😁，这张图感觉远不止如此啊，庆哥继续啊😜
哈希表如何存数据
庆哥： 好滴，那咱们就继续，来说说哈希表是如何存放数据的，记得看上面的图啊，我们按照这个图来说，我们已经知道了哈希表本质是个数组，所以这里有个数组，长度是8，现在我们要做的是把这个学生信息存放到哈希表中，也就是这个数组中去，那我们需要考虑怎么去存放呢？
这里的学号是个key，我们之前也知道了，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是用来确定这个Entry要存放在哈希表中的位置的，实际上这个值就是一个下标值，来确定放在数组的哪个位置上。
比如这里的学号是101011，那么经过哈希函数的计算之后得到了1，这个1就是告诉我们应该把这个Entry放到哪个位置，这个1就是数组的确切位置的下标，也就是需要放在数组中下表为1的位置，如图中所示。
我们之前已经介绍过什么是Entry了，所以这里你要知道，数组中1的位置存放的是一个Entry，它不是一个简单的单个数值，而是一个键值对，也就是存放了key和value，key就是学号101011，value就是张三，我们经过哈希函数计算得出的1只是为了确定这个Entry该放在哪个位置而已。
现在我们就成功把这个Entry放到了哈希表中了，怎么样，这块听懂了嘛？
小白： 嗯嗯，听懂了，不过看到这里我产生了一个疑问，那就是这个哈希函数，是不是有一个特定的加工过程，比如可以经过某种计算把101011转换成1，那么有没有可能其他的学号经过哈希函数的计算也得出1呢？那这个时候是不是就撞衫啦😂
哈希冲突
庆哥： 的确，你分析得很正确，我们再来看下面这张图：

你说的这种情况就像图中展示的那样，学号为102011的李四，他的学号经过哈希函数的计算也得出了1，那么也要放到数组中为1的位置，可是这个位置之前已经被张三占了啊，这怎么办？这种情况就是哈希冲突或者也叫哈希碰撞。
既然出现了这情况，不能不管李四啊，总得给他找个位置啊，怎么找呢？
小白： 我猜肯定有什么方法可以给李四找位置🤣
处理哈希冲突
庆哥： 那必须滴啊😄，有什么方法呢？其实关于哈希冲突的解决办法有好几种嘞，但是我这里只介绍两种主要的方法，一个是开放寻址法，一个是拉链法。
那什么是开放寻址法呢？我们继续来看图：

我觉得看图就足以说明问题了，这里所说的开放寻址法其实简单来说就是，既然位置被占了，那就另外再找个位置不就得了，怎么找其他的位置呢？这里其实也有很多的实现，我们说个最基本的就是既然当前位置被占用了，我们就看看该位置的后一个位置是否可用，也就是1的位置被占用了，我们就看看2的位置，如果没有被占用，那就放到这里呗，当然，也有可能2的位置也被占用了，那咱就继续往下找，看看3的位置，一次类推，直到找到空位置。
对了，Java中的ThreadLocal就是利用了开放寻址法。
小白： 啥是ThreadLocal啊😂
庆哥： 咋滴，你不知道啊，没事，给你一篇文章，看了包装你再也不学ThreadLocal了，因为看完这篇，你就再也忘不掉啦，链接直达，走起：再也不学ThreadLocal了，看这一篇就忘不掉了！（万字总结）
小白： 嗯嗯，我会好好看看的。那什么是拉链法啊？
庆哥： 拉链法也是比较常用的，像之前你说的HashMap就是使用了这种方法，那这个方法是怎么个回事呢？我们继续来看图：

之前说的开放寻址法采用的方式是在数组上另外找个新位置，而拉链法则不同，还是在该位置，可是，该位置被占用了咋整，总不能打一架，谁赢是谁的吧😂，当然不是这样，这里采用的是链表，什么意思呢？就像图中所示，现在张三和李四都要放在1找个位置上，但是张三先来的，已经占了这个位置，待在了这个位置上了，那李四呢？解决办法就是链表，这时候这个1的位置存放的不单单是之前的那个Entry了，此时的Entry还额外的保存了一个next指针，这个指针指向数组外的另外一个位置，将李四安排在这里，然后张三那个Entry中的next指针就指向李四的这个位置，也就是保存的这个位置的内存地址，如果还有冲突，那就把又冲突的那个Entry放在一个新位置上，然后李四的Entry中的next指向它，这样就形成了一个链表。
好啦，这就是拉链法，咋样，明白不😎
小白： 信息量不少啊，好在庆哥讲的比较清楚，明白啦😀
庆哥： 明白了就好，那我问你一个问题啊，针对开放寻址和拉链法，你有没有觉得会产生什么问题呢？
小白： 嗯嗯，我还真有问题，首先是这个拉链法啊，如果冲突的很多，那这个增加的链表岂不是很长，这样也不咋好吧😂
庆哥： 的确，如果冲突过多的话，这块的链表会变得比较长，怎么处理呢？这里举个例子吧，拿java集合类中的HashMap来说吧，如果这里的链表长度大于等于8的话，链表就会转换成树结构，当然如果长度小于等于6的话，就会还原链表。以此来解决链表过长导致的性能问题。
小白： 为啥是小于等于6啊，咋不是7嘞😂
庆哥： 这样设计是因为中间有个7作为一个差值，来避免频繁的进行树和链表的转换，因为转换频繁也是影响性能的啊。
小白： 嗯嗯，这个知道了，关于开放寻址也有个疑问，那就是如果一直找不到空的位置咋整啊？🤣
庆哥： 这个不会的，为啥嘞？你这样想，是因为你考虑了一个前提，那就是位置已经被占光了，没有空位置了，但是实际情况是位置不会被占光的，因为有一定量的位置被占了的时候就会发生扩容。
小白： 阿西吧，还有扩容，那这个扩容是咋回事呢？
哈希表的扩容
庆哥： 其实这里不仅仅是因为你说的那种情况才会扩容，还有一个很重要的原因就是当哈希表被占的位置比较多的时候，出现哈希冲突的概率也就变高了，所以很有必要进行扩容。
那么这个扩容是怎么扩的呢？这里一般会有一个增长因子的概念，也叫作负载因子，简单点说就是已经被占的位置与总位置的一个百分比，比如一共十个位置，现在已经占了七个位置，就触发了扩容机制，因为它的增长因子是0.7，也就是达到了总位置的百分之七十就需要扩容。
还拿HashMap来说，当它当前的容量占总容量的百分之七十五的时候就需要扩容了。
而且这个扩容也不是简单的把数组扩大，而是新创建一个数组是原来的2倍，然后把原数组的所有Entry都重新Hash一遍放到新的数组。
小白： 这个重新Hash一遍是啥意思啊？
庆哥： 因为数组扩大了，所以一般哈希函数也会有变化，这里的Hash也就是把之前的数据通过新的哈希函数计算出新的位置来存放。
小白： 嗯嗯，原来是这么回事啊，懂了，对了，那哈希表的数据读取怎么操作的啊？
哈希表如何读取数据
庆哥： 要知道这个读取操作，我们还来看这个图：

比如我们现在要通过学号102011来查找学生的姓名，怎么操作呢？我们首先通过学号利用哈希函数得出位置1，然后我们就去位置1拿数据啊，拿到这个Entry之后我们得看看这个Entry的key是不是我们的学号102011，一看是101011，什么鬼，一边去，这不是我们要的key啊，然后根据这个Entry的next知道下一给位置，在比较key，好成功找到李四。
小白： 哦哦，原来是这么回事啊，那对于开放寻址那种是不是也是这个思路，先确定到这个位置，然后再看这个位置上的key是不是我们要的，如过不是那就看看下一个位置的。
庆哥： 可以的，完全正确，好了现在我们对哈希表的讲解已经差不多了，那么你觉得对于哈希表而言，什么是核心呢？
哈希函数是核心
小白： 我觉得应该是哈希函数吧，经过上面的讲解，我觉得，如果一个哈希函数设计的足够好的话，就会减少哈希冲突的概率，如果设计的不好，那就会经常撞衫😂，那就很影响性能了，比如刚开始我们举的那个例子，拿姓名的首字母来确定位置，这个哈希函数的设计就不咋滴，比如王二，王三，王四什么的，这都会冲突啊😂
庆哥： 的确，在哈希表中，哈希函数的设计很重要，一个好的哈希函数可以极大的提升性能，而且如果你的哈希函数设计的比较简单粗陋，那很容易被那些不怀好意的人捣乱，比如知道了你哈希函数的规则，故意制造容易冲突的key值，那就有意思了，你的哈希表就会一直撞啊，一直撞啊😂
小白： 哈哈😂，那设计哈希函数有什么方法吗？
庆哥： 必须有啊，比如有直接定址法，数字分析法，折叠法，随机数法和除留余数法等等，要不要继续讲啊😀
小白： 我去🤣，还是不要了吧，消化不了啊，这次先到这吧，谢谢庆哥😘
感谢阅读
大学的时候选择了自学Java，工作了发现吃了计算机基础不好的亏，学历不行这是没办法的事，只能后天弥补，于是在编码之外开启了自己的逆袭之路，不断的学习Java核心知识，深入的研习计算机基础知识，所有心得全部书写成文，整理成有目录的PDF，持续原创，PDF在公众号持续更新，如果你也不甘平庸，那就与我一起在编码之外，不断成长吧！
其实这里不仅有技术，更有那些技术之外的东西，比如，如何做一个精致的程序员，而不是“屌丝”，程序员本身就是高贵的一种存在啊，难道不是吗？
非常欢迎你的加入，未来的日子，编码之外，有你有我，一起做一个人不傻，钱很多，活得久的快乐的程序员吧！
回复关键字“PDF”，获取技术文章合集，已整理好，带有目录，欢迎一起交流技术！
另外回复“庆哥”，看庆哥给你准备的惊喜大礼包，只给首次关注的你哦！
任何问题，可以加庆哥微信：H653836923，另外，我有个交流群，我会***不定期在群里分享学习资源，不定时福利***，感兴趣的可以说下我邀请你！
对了，如果你是个Java小白的话，也可以加我微信，我相信你在学习的过程中一定遇到不少问题，或许我可以帮助你，毕竟我也是过来人了！

感谢各位大大的阅读🥰

一、哈希表概述

       首先简单介绍几个概念：哈希表（散列表）、映射、冲突、链地址、哈希函数。

       哈希表（Hash table）的初衷是为了将数据映射到数组中的某个位置，这样就能够通过数组下标访问该数据，提高数据的查找速度，这样的查找的平均期望时间复杂度是O(1)的。

       例如四个整数 6、7、9、12 需要映射到数组中，我们可以开一个长度为13（C语言下标从0开始）的数组，然后将对应值放到对应的下标，但是这样做，就会浪费没有被映射到的位置的空间。



 

       采用哈希表的话，我们可以只申请一个长度为4的数组，如下图所示：



 

       将每个数的值对数组长度4取模，然后放到对应的数组槽位中，这样就把离散的数据映射到了连续的空间，所以哈希表又称为散列表。这样做，最大限度上提高空间了利用率，并且查找效率还很高。

       那么问题来了，如果这四个数据是6、7、8、11呢？继续看图：



       7 和 11 对4取模的值都是 3，所以占据了同一个槽位，这种情况我们称为冲突 （collision）。一般遇到冲突后，有很多方法解决冲突，包括但不限于 开放地址法、再散列法、链地址法 等等。 Redis采用的是链地址法，所以这里只介绍链地址法，其它的方法如果想了解请自行百度。

      链地址法就是将有冲突的数据用一个链表串联起来，如图所示：



       这样一来，就算有冲突，也可以将有冲突的数据存储在一起了。存储结构需要稍加变化，哈希表的每个元素将变成一个指针，指向数据链表的链表头，每次有新数据来时从链表头插入，可以达到插入的时间复杂度保持O(1)。

        再将问题进行变形，如果4个数据是 "are",  "you",  "OK",  "？" 这样的字符串，如何进行映射呢？没错，我们需要通过一个哈希函数将字符串变成整数，哈希函数的概念会在接下来详细讲述，这里只需要知道它可以把一个值变成另一个值即可，比如哈希函数f(x)，调用 f("are") 就可以得到一个整数，f("you") 也可以得到一个整数。

        一个简易的大小写不敏感的字符串哈希函数如下：

unsigned int hashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)5381;                       // hash初始种子，实验值
    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++));          // hash * 33 + c
    return hash;
}

        我们看到，哈希函数的作用就是把非数字的对象通过一系列的算法转化成数字（下标），得到的数字可能是哈希表数组无法承载的，所以还需要通过取模才能映射到连续的数组空间中。对于这个取模，我们知道取模的效率相比位运算来说是很低的，那么有没有什么办法可以把取模用位运算来代替呢？

        答案是有！我们只要把哈希表的长度 L 设置为2的幂（L = 2^n），那么 L-1 的二进制表示就是n个1，任何值 x 对 L 取模等同于和 (L-1) 进行位与（C语言中的&）运算。



        介绍完哈希表的基础概念，我们来看看 Redis 中是如何实现字典的。

二、Redis数据结构定义

     1、哈希表

       哈希表的结构定义在 dict.h/dictht ：

typedef struct dictht {
    dictEntry **table;             // 哈希表数组
    unsigned long size;            // 哈希表数组的大小
    unsigned long sizemask;        // 用于映射位置的掩码，值永远等于(size-1)
    unsigned long used;            // 哈希表已有节点的数量
} dictht;

       table 是一个数组，数组的每个元素都是一个指向 dict.h/dictEntry 结构的指针；

       size 记录哈希表的大小，即 table 数组的大小，且一定是2的幂；

       used 记录哈希表中已有结点的数量；

       sizemask 用于对哈希过的键进行映射，索引到 table 的下标中，且值永远等于 size-1。具体映射方法很简单，就是对 哈希值 和 sizemask 进行位与操作，由于 size 一定是2的幂，所以 sizemask=size-1，自然它的二进制表示的每一个位(bit)都是1，等同于上文提到的取模；

       如图所示，为一个长度为8的空哈希表。



     2、哈希表节点

       哈希表节点用 dict.h/dictEntry 结构表示，每个 dictEntry 结构存储着一个键值对，且存有一个 next 指针来保持链表结构：

typedef struct dictEntry {
    void *key;                  // 键
    union {                     // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     // 指向下一个哈希表节点，形成单向链表
} dictEntry;

       key 是键值对中的键；

       v 是键值对中的值，它是一个联合类型，方便存储各种结构；

       next 是链表指针，指向下一个哈希表节点，他将多个哈希值相同的键值对串联在一起，用于解决键冲突；如图所示，两个dictEntry 的 key 分别是 k0 和 k1，通过某种哈希算法计算出来的哈希值和 sizemask 进行位与运算后都等于 3，所以都被放在了 table 数组的 3号槽中，并且用 next 指针串联起来。



     3、字典

       Redis中字典结构由 dict.h/dict 表示：

typedef struct dict {
    dictType *type;                        // 和类型相关的处理函数
    void *privdata;                        // 上述类型函数对应的可选参数
    dictht ht[2];                          // 两张哈希表，ht[0]为原生哈希表，ht[1]为 rehash 哈希表
    long rehashidx;                        // 当等于-1时表示没有在 rehash，否则表示 rehash 的下标
    int iterators;                         // 迭代器数量(暂且不谈)
} dict;

     type 是一个指向 dict.h/dictType 结构的指针，保存了一系列用于操作特定类型键值对的函数；

     privdata 保存了需要传给上述特定函数的可选参数；

     ht 是两个哈希表，一般情况下，只使用ht[0]，只有当哈希表的键值对数量超过负载(元素过多)时，才会将键值对迁移到ht[1]，这一步迁移被称为 rehash (重哈希)，rehash 会在下文进行详细介绍；

     rehashidx 由于哈希表键值对有可能很多很多，所以 rehash 不是瞬间完成的，需要按部就班，那么 rehashidx 就记录了当前 rehash 的进度，当 rehash 完毕后，将 rehashidx 置为-1；

     4、类型处理函数

      类型处理函数全部定义在 dict.h/dictType 中：

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);                                         // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);                                      // 复制键的函数
    void *(*valDup)(void *privdata, const void *obj);                                      // 复制值的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);                 // 比较键的函数
    void (*keyDestructor)(void *privdata, void *key);                                      // 销毁键的函数
    void (*valDestructor)(void *privdata, void *obj);                                      // 销毁值的函数
} dictType;

       以上的函数和特定类型相关，主要是为了实现多态，看到这个如果懵逼也没关系，下面会一一对其进行介绍。

三、哈希函数

      类型处理函数中的第一个函数 hashFunction 就是计算某个键的哈希值的函数，对于不同类型的 key，哈希值的计算是不同的，所以在字典进行创建的时候，需要指定哈希函数。

      哈希函数可以简单的理解为就是小学课本上那个函数，即y = f(x)，这里的 f(x)就是哈希函数，x是键，y就是哈希值。好的哈希函数应该具备以下两个特质：

       1、可逆性；

       2、雪崩效应：输入值(x)的1位(bit)的变化，能够造成输出值(y)1/2的位(bit)的变化；

       可逆性很容易理解，来看两个图。图(a)中已知哈希值 y 时，键 x 可能有两种情况，所以显然是不可逆的；而图(b)中已知哈希值 y 时，键 x 一定是唯一确定的，所以它是可逆的。从图中看出，函数可逆的好处是：减少冲突。由于 x 和 y 一一对应，所以在没有取模之前，至少是没有冲突的，这样就从本原上减少了冲突。



       雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。

       Redis源码中提供了一些哈希函数的实现：

      1、整数哈希

unsigned int dictIntHashFunction(unsigned int key)
{
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}

       2、字符串哈希

unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)dict_hash_function_seed;
    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
    return hash;
}

       这些哈希函数是前人经过一系列的实验，科学计算总结得出来的，我们只需要知道有这么些函数就行了。当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。MurmurHash 算法最初由 Austin Appleby 于 2008 年发明， 这种算法的优点在于， 即使输入的键是有规律的， 算法仍能给出一个很好的随机分布性， 并且算法的计算速度也非常快。

 

四、哈希算法

     1、索引 

       当要将一个新的键值对添加到字典里面或者通过键查找值的时候都需要执行哈希算法，主要是获得一个需要插入或者查找的dictEntry 所在下标的索引，具体算法如下：

       1、通过宏 dictHashKey 计算得到该键对应的哈希值

#define dictHashKey(d, key) (d)->type->hashFunction(key)

       2、将哈希值和哈希表的 sizemask 属性做位与，得到索引值 index，其中 ht[x] 可以是 ht[0] 或者 ht[1]

index = dictHashKey(d, key) & d->ht[x].sizemask;

      2、冲突解决

        哈希的冲突一定发生在键值对插入时，插入的  API 是 dict.c/dictAddRaw：

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);               // 1、执行rehash
    if ((index = _dictKeyIndex(d, key)) == -1)                // 2、索引定位
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];          // 3、根据是否 rehash ，选择哈希表
    entry = zmalloc(sizeof(*entry));                          // 4、分配内存空间，执行插入
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    dictSetKey(d, entry, key);                                // 5、设置键
    return entry;
}

       1、判断当前的字典是否在进行 rehash，如果是，则执行一步 rehash，否则忽略。判断 rehash 的依据就是 rehashidx 是否为 -1；

       2、通过 _dictKeyIndex 找到一个索引，如果返回-1表明字典中已经存在相同的 key，具体参见接下来要讲的 索引定位；

       3、根据是否在 rehash 选择对应的哈希表；

       4、分配哈希表节点 dictEntry 的内存空间，执行插入，插入操作始终在链表头插入，这样可以保证每次的插入操作的时间复杂度一定是 O(1) 的，插入完毕，used属性自增；

       5、dictSetKey 是个宏，调用字典处理函数中的 keyDup 函数进行键的复制；

 

      3、索引定位

        插入时还需要进行索引定位，以确定节点要插入到哈希表的哪个位置，实现在静态函数 dict.c/_dictKeyIndex 中：

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    if (_dictExpandIfNeeded(d) == DICT_ERR)                            // 1、rehash 判断
        return -1;
    h = dictHashKey(d, key);                                           // 2、哈希函数计算哈希值
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;                               // 3、哈希算法计算索引值
        he = d->ht[table].table[idx];
        while(he) {                          
            if (key==he->key || dictCompareKeys(d, key, he->key))      // 4、查找键是否已经存在
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;                                // 5、rehash 判断 
    }
    return idx;
}

       1、判断当前哈希表是否需要进行扩展，具体参见接下来要讲的 rehash；

       2、利用给定的哈希函数计算键的哈希值；

       3、通过位与计算索引，即插入到哈希表的哪个槽位中；

       4、查找当前槽位中的链表里是否已经存在该键，如果存在直接返回 -1；这里的 dictCompareKeys 也是一个宏，用到了keyCompare 这个比较键的函数；

       5、这个判断比较关键，如果当前没有在做 rehash，那么 ht[1] 必然是一个空表，所以不能遍历 ht[1]，需要及时跳出循环；

    五、rehash

      千呼万唤始出来，提到了这么多次的 rehash 终于要开讲了。其实没有想象中的那么复杂，随着字典操作的不断执行，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。

     1、负载因子

       这里提到了一个负载因子，其实就是当前已使用结点数量除上哈希表的大小，即：

load_factor = ht[0].used / ht[0].size

      2、哈希表扩展

       1、当哈希表的负载因子大于5时，为 ht[1] 分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；

       2、将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个；

       3、当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件， 将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备；

       Redis 中 实现哈希表扩展调用的是 dict.c/_dictExpandIfNeeded 函数：

static int _dictExpandIfNeeded(dict *d)
{
    if (dictIsRehashing(d)) return DICT_OK;
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);          // 大小为0需要设置初始哈希表大小为4
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))                 // 负载因子超过5，执行 dictExpand
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}


      3、哈希表收缩

       哈希表的收缩，同样是为 ht[1] 分配空间， 大小等于 max( ht[0].used, DICT_HT_INITIAL_SIZE )，然后和扩展做同样的处理即可。

     六、渐进式rehash

       扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。

       渐进式 rehash 的详细步骤如下：

       1、为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；

       2、将 rehashidx 设置为0，表示正式开始 rehash，前两步是在 dict.c/dictExpand 中实现的：

int dictExpand(dict *d, unsigned long size)
{
    dictht n;
    unsigned long realsize = _dictNextPower(size);                      // 找到比size大的最小的2的幂
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;                                                 // 给ht[1]分配 realsize 的空间
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    if (d->ht[0].table == NULL) {                                      // 处于初始化阶段
        d->ht[0] = n;
        return DICT_OK;
    }
    d->ht[1] = n;
    d->rehashidx = 0;                                                  // rehashidx 设置为0，开始渐进式 rehash
    return DICT_OK;
}

 

       3、在进行 rehash 期间，每次对字典执行 增、删、改、查操作时，程序除了执行指定的操作外，还会将 哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对 全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表 （遍历很久遇到的都是NULL），从而导致函数阻塞时间太长，这里引入了一个 “最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。

       这一步实现在 dict.c/dictRehash 中：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10;
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;                                      // 设置一个空访问数量 为 n*10
        }
        de = d->ht[0].table[d->rehashidx];                                          // dictEntry的迁移
        while(de) {
            unsigned int h;
            nextde = de->next;
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;                                                            // 完成一次 rehash
    }

    if (d->ht[0].used == 0) {                                                      // 迁移完毕，rehashdix 置为 -1
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    return 1;
}

       4、最后，当 ht[0].used 变为0时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table， 并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。

 

     七、字典API

        1、创建字典

        内部分配字典空间，并作为返回值返回，并调用 _dictInit 进行字典的初始化，时间复杂度O(1)。

dict *dictCreate(dictType *type, void *privDataPtr)

        2、增加键值对

        调用 dictAddRaw 增加一个 dictEntry，然后调用 dictSetVal 设置值，时间复杂度O(1)。

int dictAdd(dict *d, void *key, void *val)

        3、查找键

        利用哈希算法找到给定键的 dictEntry，时间复杂度O(1)。

dictEntry *dictFind(dict *d, const void *key)

        4、查找值

        利用 dictFind 找到给定键的 dictEntry，然后获得值，值的类型不确定，所以返回一个万能指针，时间复杂度O(1)。

void *dictFetchValue(dict *d, const void *key)

        5、删除键

        通过哈希算法找到对应的键，从对应链表移除，时间复杂度O(1)。

int dictDelete(dict *ht, const void *key)

 

 

 

参考链接：数据结构（严蔚敏）
一、什么是Hash表
要想知道什么是哈希表，那得先了解哈希函数

哈希函数
对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。那么，有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就**“预先知道”**key所在的位置，直接找到数据，提升效率。

即

地址index=H（key）

说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表
二、哈希函数的构造方法
根据前人经验，统计出如下几种常用hash函数的构造方法：

直接定制法

哈希函数为关键字的线性函数如 H（key）=a*key+b

这种构造方法比较简便，均匀，但是有很大限制，仅限于地址大小=关键字集合的情况

使用举例：

假设需要统计中国人口的年龄分布，以10为最小单元。今年是2018年，那么10岁以内的分布在2008-2018，20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据，那么关键字应该是2018，2008，1998……

那么可以构造哈希函数H（key）=（2018-key）/10=201-key/10

那么hash表建立如下

   

      
index
      
key
      
年龄
      
人数（假设数据）
   
   

      
0
      
2018
      
 0-10
      
200W
   
   

      
1
      
2008
      
 10-20
      
250W
   
   

      
2
      
1998
      
 20-30
      
253W
   
   

      
3
      
1988
      
 30-40
      
300W
   
   

      
……
      

      

      

   

数字分析法

假设关键字集合中的每个关键字key都是由s位数字组成（$k_1,k_2,……,k_n$）,分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体
使用举例

我们知道身份证号是有规律的，现在我们要存储一个班级学生的身份证号码，假设这个班级的学生都出生在同一个地区，同一年，那么他们的身份证的前面数位都是相同的，那么我们可以截取后面不同的几位存储，假设有5位不同，那么就用这五位代表地址。

H（key）=key%100000

此种方法通常用于数字位数较长的情况，必须数字存在一定规律，其必须知道数字的分布情况，比如上面的例子，我们事先知道这个班级的学生出生在同一年，同一个地区。

平方取中法

如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。

使用举例

比如key=1234 1234^2=1522756 取227作hash地址

比如key=4321 4321^2=18671041 取671作hash地址

这种方法适合事先不知道数据并且数据长度较小的情况

折叠法

如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址

使用举例

比如key=123 456 789

我们可以存储在61524，取末三位，存在524的位置

该方法适用于数字位数较多且事先不知道数据分布的情况

除留余数法用的较多

H（key）=key MOD p （p<=m m为表长）

很明显，如何选取p是个关键问题。
使用举例

比如我们存储3 6 9，那么p就不能取3

因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）
比如key = 7，39，18，24，33，21时取表长m为9 p为7 那么存储如下

   

      
index
      
0
      
1
      
2
      
3
      
4
      
5
      
6
      
7
      
8
   
   

      
key
      
7
      
21（冲突后移）
      

      
24
      
4
      
18（冲突后移）
      
33冲突后移）
      

      

   

**随机数法**
H（key）	=Random（key）
取关键字的随机函数值为它的散列地址
hash函数设计的考虑因素
1.计算散列地址所需要的时间（即hash函数本身不要太复杂）

2.关键字的长度

3.表长

4.关键字分布是否均匀，是否有规律可循

5.设计的hash函数在满足以上条件的情况下尽量减少冲突
三、哈希冲突
即不同key值产生相同的地址，H（key1）=H（key2）

比如我们上面说的存储3 6 9，p取3是

3 MOD 3 == 6 MOD 3 == 9 MOD 3

此时3 6 9都发生了hash冲突
哈希冲突的解决方案
不管hash函数设计的如何巧妙，总会有特殊的key导致hash冲突，特别是对动态查找表来说。

hash函数解决冲突的方法有以下几个常用的方法

1.开放定制法

2.链地址法

3.公共溢出区法

建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。

4.再散列法

准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……

重点了解一下开放定制法和链地址法
开放定制法
首先有一个H（key）的哈希函数

如果H（key1）=H（keyi）

那么keyi存储位置$H_i=(H(key)+d_i)MOD m$m为表长

$d_i$有三种取法

1）线性探测再散列

$d_i=c*i$

2）平方探测再散列

$d_i=1^2,-1^2,2^2,-2^2$……

3）随机探测在散列（双探测再散列）

$d_i$是一组伪随机数列

注意

增量di应该具有以下特点（完备性）：产生的Hi（地址）均不相同，且所产生的s（m-1）个Hi能覆盖hash表中的所有地址

平方探测时表长m必须为4j+3的质数（平方探测表长有限制）
随机探测时m和di没有公因子（随机探测di有限制）

三种开放定址法解决冲突方案的例子


废话不多说，上例子就明白了

有一组数据

19 01 23 14 55 68 11 86 37要存储在表长11的数组中，其中H（key）=key MOD 11

那么按照上面三种解决冲突的方法，存储过程如下：

（表格解释：从前向后插入数据，如果插入位置已经占用，发生冲突，冲突的另起一行，计算地址，直到地址可用，后面冲突的继续向下另起一行。最终结果取最上面的数据（因为是最“占座”的数据））

线性探测再散列

我们取di=1，即冲突后存储在冲突后一个位置，如果仍然冲突继续向后

   

      
index
      
0
      
1
      
2
      
3
      
4
      
5
      
6
      
7
      
8
      
9
      
10
   
   

      
key
      
55
      
1
      

      
14
      

      

      

      

      
19
      
86
      

   
   

      

      

      
23冲突
      
23
      

      

      

      

      

      

      

      

   
   

      

      

      

      
68冲突
      
68冲突
      
68
      

      

      

      

      

      

   
   

      

      
11冲突
      
11冲突
      
11冲突
      
11冲突
      
11冲突
      
11
      

      

      

      

      

   
   

      

      

      

      

      

      
37冲突
      
37冲突
      
37
      

      

      

      

   
   

      
最终存储结果
      
55
      
1
      
23
      
14
      
68
      
11
      
37
      

      
19
      
86
      

   

**平方探测再散列**

   

      
index
      
0
      
1
      
2
      
3
      
4
      
5
      
6
      
7
      
8
      
9
      
10
   
   

      
key
      
55
      
1
      

      
14
      
37
      

      

      

      
19
      
86
      

   
   

      

      

      
23冲突
      
H（23）+1
      

      

      

      

      

      

      

      

   
   

      

      

      
H（68）-1冲突
      
68冲突
      
H（68）+1冲突
      

      

      
H（68）+4
      

      

      

      

   
   

      

      
11冲突
      
H（11）+1冲突
      

      

      

      

      

      

      

      

      
H（11）-1
   
   

      
最终存储结果
      
55
      
1
      
23
      
14
      
37
      

      
68
      

      
19
      
86
      
11
   

**随机探测在散列（双探测再散列）**
发生冲突后
H（key）‘=(H(key)+di)MOD m
在该例子中
H（key）=key MOD 11
我们取di=key MOD 10 +1
则有如下结果：

   

      
index
      
0
      
1
      
2
      
3
      
4
      
5
      
6
      
7
      
8
      
9
      
10
   
   

      
key
      
55
      
1
      
68
      
14
      

      

      

      

      
19
      
86
      

   
   

      

      

      
23冲突
      

      

      

      
H（23）+3+1
      

      

      

      

      

   
   

      

      
11冲突
      

      
H（11）+1+1冲突
      

      
H（11）+1+1+1+1
      

      

      

      

      

      

   
   

      

      

      
（H（37）+8）模11冲突
      

      

      
37冲突
      

      

      
（H（37）+8+8+8）模11
      

      
（H（37）+8+8）模11冲突
      

   
   

      
最终存储结果
      
55
      
1
      
68
      
14
      
23
      

      
11
      
37
      
19
      
86
      

   

链地址法
产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据

上面的例子，用链地址法则是下面这样：


四、hash表的查找
查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：

对于给定的key，计算hash地址index = H（key）

如果数组arr【index】的值为空 则查找不成功

如果数组arr【index】== key 则查找成功

否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null
hash表的查找效率
决定hash表查找的ASL因素：

1）选用的hash函数

2）选用的处理冲突的方法

3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)

一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素

hash表的ASL是处理冲突方法和装载因子的函数

前人已经证明，查找成功时如下结果：


可以看到无论哪个函数，装载因子越大，平均查找长度越大，那么装载因子α越小越好？也不是，就像100的表长只存一个数据，α是小了，但是空间利用率不高啊，这里就是时间空间的取舍问题了。通常情况下，认为α=0.75是时间空间综合利用效率最高的情况。
上面的这个表可是特别有用的。假设我现在有10个数据，想使用链地址法解决冲突，并要求平均查找长度<2

那么有1+α/2 <2

α<2

即 n/m<2 (n=10)

m>10/2

m>5 即采用链地址法，使得平均查找长度< 2 那么m>5
之前我的博客讨论过各种树的平均查找长度，他们都是基于存储数据n的函数，而hash表不同，他是基于装载因子的函数，也就是说，当数据n增加时，我可以通过增加表长m，以维持装载因子不变，确保ASL不变。

那么hash表的构造应该是这样的：


五、hash表的删除
首先链地址法是可以直接删除元素的，但是开放定址法是不行的，拿前面的双探测再散列来说，假如我们删除了元素1，将其位置置空，那 	23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据，比如-1