概念

数据结构中有一类常用于搜索，给定一个元素集合，常见的可用于搜索的算法有
遍历，遍历是十分粗暴简单的手段，对于元素的集合没有特殊要求，时间复杂度是O(N)。效率通常较低。
二分查找，二分查找要求元素集合有序，时间复杂度为O(logN),
二叉搜索树，查找规则简单，但是退化为单支树时间复杂度是O(N),
AVL树和红黑树，时间复杂度都是O(logN).

上面的这些常用的方法无一例外都有一个关键步骤就是元素的比较，通过比较待查找元素和集合中的元素，来确定该元素在集合中的位置。真实的效率取决于比较的次数。

如果有不需要进行元素比较就能查找的方法，就能达到理想的查找。

哈希就是这样一种数据结构，

在存储元素时，通过某些方法，将元素与所存储的位置建立一一对应的关系，则在查找时就可以不需要进行数据的比较。这种方法称为哈希散列方法。元素存储的集合称为哈希表或者散列表，建立映射关系的方法称为哈希函数或者散列函数。通过这个函数来计算元素来计算元素在哈希表中的插入位置。

比如，
元素集合：1 6 7 5 4 9
哈希函数：f(x) = x % capacity

插入元素时，通过哈希函数计算该元素在哈希表中的位置， 1%10 = 1，则1放在1号位置。

查找元素时，通过函数计算该元素在表格中的位置，检测该位置上存储的元素是否是待查找元素。

哈希冲突

如果新增一个元素11，通过哈希函数计算，结果应该插入在1的位置，此时该位置已经有元素了，这就是哈希冲突的产生原因，当不同的元素通过相同哈希函数计算出相同的哈希地址，这种问题成为哈希冲突。

哈希函数的设计

如果哈希函数的设计不合理，则会产生不同元素的哈希地址集中存在与某一段地址范围中，使得哈希冲突产生的概率非常高。因此哈希函数要求
1.函数的定义域必须包含所有要存储的关键码，散列表如果有m个地址，其值域必须在[0,m)之间。
2.哈希函数计算出来的地址要能均匀的分布在哈希表中。
3.哈希函数应尽量简单

常用的方法：
直接定址法，取关键字的某个线性函数作为散列地址， Hash = A*Key+B ，这种函数简单且分布均匀，但是要提前分析关键字的分布情况，适用于元素集合较小且连续的情况。比如查找字符串中只出现一次的字符。就可以采用直接定址法，将字符串中字符的ASCII码值作为数组下标，统计次数。

除留余数法，设散列表中的地址数为m，在不大于m的数中取一个接近或等于m的的素数p，设计
Hash = Key % p这样的方法计算哈希地址。是非常常用的一种方法。

平方取中法，比如关键字为1234，那它的平方就是1522756，取中间3位得到227作为哈希地址，5678的平方Wie23239684，则取中间的3位239或者396作为哈希地址。平方取中法比较适合不知道关键字的分布情况，关键字的位数又不是很大时用。

折叠法，首先将关键字分割成位数相等的几部分，比如关键字12345678，可以分为123,456,78,最后一个可以位数短一点，将分出来的数相加并根据散列表的容量取靠后的位数作为散列表地址。适合用于关键字位数较多的情况。

随机数法，取关键字的随机函数值作为哈希地址，Hash = random(Key),适合用于关键字长度不等的情况。

数学分析法，有n个位数相同的数字，每个位上都有r种不同的符号，出现概率不一定相同，可能在某几位上分布比较平衡，根据散列表的大小，选择符号分布较均匀的几位作为哈希地址，比如手机号码的集合，前三位的分布重复较多都是1几几，不均匀，而后四位分布较均匀。

哈希函数的设计只能尽量降低产生哈希冲突的概率，不论一个哈希函数设计的多么科学，都无法彻底避免哈希冲突的产生。

哈希冲突的解决方式

闭散列

在上面的例子中，如果要继续向哈希表中插入元素54，根据哈希函数算出的地址，应该插入在5的位置，而5的位置上已经有元素了，闭散列的处理方式在5的元素之后开始依次向后查找有没有非空的位置，找到了就将这个元素插入进去，如果找到末尾也没有，则返回表头从表头开始继续找非空的位置。
闭散列中，哈希表中的每个位置都增加了一个标识用来表示状态

EMPTY，表示该位置为空，EXIST，表示该位置上有有效元素，DELETE表示该位置元素被删除了。在插入时，通过哈希函数计算出地址后，先检测该位置有没有发生哈希冲突，如果没有发生就直接插入并将该位置状态修改为EXIST，删除时，先通过哈希函数计算表中的位置，发现该位置有元素，与待删除元素进行比较，如果是则直接删除，但是该位置的状态不能修改成EMPTY，应改为DELETE，因为如果该位置为空，则表明该元素不存在。

这种依次查找空位的方式称为线性探测，线性探测插入和删除的规则比较简单，但是存在一定缺陷，发生哈希冲突时，容易产生数据的堆积，导致堆积的元素占用大量空余的位置，增加查找时的时间消耗影响效率。

另一种方式称为二次探测，不再通过挨个去找空位的方式，下一个位置是通过H(i) = (H0 + i²) 或者H(i) = H0 - i²的方式去计算。与线性探测相比，能解决数据堆积的问题，但是线性探测最差情况下，走完一圈哈希表就能找到，而二次探测不能确定。当表中空位置比较少时，可能需要找很多次。

总的来说，当哈希表中的元素存了非常多的时候，表中的剩余位置越来越少，发生冲突的概率就越来越高，而且会影响探测的效率，哈希是追求高效查找的数据结构，而当哈希表中有效元素很多时，会大大影响效率。解决这个问题就需要哈希表中存储的元素不能太多，达到一定程序就要扩容，所以哈希表一定是不会存满的。具体什么情况下扩容，提到负载因子的概念，负载因子是有效元素/空间总数的值，有研究表明，线性探测负载因子达到70%左右就应该进行扩容，而二次探测负载因子达到50%就应该进行扩容。因此哈希也是一种空间利用率较低的数据结构。

开散列

开散列又称链地址法，相比于闭散列在开发中应用更多，开散列实际上是数据与链表的集合，数组中的每个元素都是单链表，链表上挂载发生哈希冲突的元素。

首先通过哈希函数计算出哈希地址，然后，具有相同哈希地址的元素归为一个集合中，称为一个桶，桶中的元素通过单链表组织起来。哈希表中存放链表的头，这种结构称为哈希桶。

根据哈希桶的规则，插入元素的理想状态，

而实际上，当插入的元素比较特殊时，依然会导致大部分元素集中在一个链表中，导致某些链表特别长，这样一来，在哈希桶中查找元素实际上变成了在链表中查找元素，链表的查询时间复杂度是O(N),因此插入元素也应该避免这种问题的出现。闭散列当中是通过根据负载因子来进行扩容的方式解决问题的。哈希桶也是如此，哈希桶的规则中，当哈希桶中元素的个数与桶的个数相等时，就要考虑扩容，哈希桶的容量改变后，哈希函数计算的地址也改变了，所以要将旧哈希桶中的元素搬移到新的哈希桶中。
有时候会有些更极端的情况，虽然没达到扩容的条件，但是某些链表中挂载的节点已经非常多了，哈希表的性能因此会下降，此时的处理方法是当链表中的节点达到一定的阈值还没有得到扩容时，将链表转换成红黑树。一般设计是当链表中节点的个数等于8的时候，就将链表转换为红黑树，删除时，当红黑树中的节点个数小于6的时候，再将红黑树转换位链表。

除留取余法的设计，除留取余法要取一个不大于表的容量但最接近于它的素数，在SGI-STL3.0版本中，hash_map底层给出了一个和除留取余法有关的确定素数的方法。将常用的28个素数枚举出来。
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
泛型设计：理想的哈希表应该能存储任意元素，但是有些元素不能直接取模运算，比如常见的字符串类型。atoi只能将数字类型的字符串转换为字符串格式，因此要借助一些其他的算法来实现取模的运算，有住专门设计的字符串哈希算法等。

实现一个简单的哈希桶

#pragma once

#include<iostream>
#include"Common.h"
#include<vector>

using namespace std;

template<class T>

struct HashBucketNode {
	HashBucketNode<T>* next;
	T data;

	HashBucketNode(const T& x = T())
		:next(nullptr)
		,data(x)
	{}
};

template<class T>

class T2Intdef {
public:
	const T& operator()(const T& data) {
		return data;
	}
};

//一种字符串转整形的算法
class T2str {
public:
	size_t operator()(const string& s){
		const char* str = s.c_str();
		unsigned int seed = 131;
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
		return (hash & 0x7FFFFFFF);
	}
};


template<class T,class T2Int = T2Intdef<T>>

class HashBucket {
	typedef HashBucketNode<T> Node;
public:
	HashBucket(size_t capacity = 53)
		:table(Getnextprime(capacity))
		,size(0)
	{}
	
	~HashBucket() {
		Destroy();
	}

	bool Insert(const T& data) {
		//检测是否需要扩容
		Checkcapacity();
		size_t bucketloc = Hashfuc(data);
		Node* cur = table[bucketloc];
		while (cur) {
			if (data == cur->data) {
				return false;
			}
			cur = cur->next;
		}//有位置可插入，必是cur走到了空的位置

		cur = new Node(data);

		cur->next = table[bucketloc];
		table[bucketloc] = cur;
		++size;
		//就是链表头插法，本来链表的首节点是table[bucketloc]
		//先把头结点的地址交给cur的next
		//再设置cur称为新的头结点
		return true;
	}

	bool Erase(const T& data) {
		size_t bucketloc = Hashfuc(data);
		Node* cur = table[bucketloc];
		Node* prev = nullptr;
		while (cur) {
			if (data == cur->data) {
				//判断cur是不是头结点
				if (nullptr == prev) {
					table[bucketloc] = cur->next;
				}
				else {
					prev->next = cur->next;
				}
				delete cur;
				--size;
				return true;
			}
			else {
				prev = cur;
				cur = cur->next;
			}
		}
		return false;
	}

	Node* Find(const T& data) {
		size_t bucketloc = Hashfuc(data);
		Node* cur = table[bucketloc];
		while (cur) {
			if (data == cur->data) {
				return cur;
			}
			cur = cur->next;
		}
		return nullptr;
	}

	size_t Size()const {
		return size;
	}

	bool Empty() {
		return 0 == size;
	}

	void Print() {
		for (size_t i = 0; i < table.capacity(); i++) {
			Node* cur = table[i];
			cout << "table[" << i << "]";
			while (cur) {
				cout << cur->data << "--->";
				cur = cur->next;
			}
			cout << "NULL" << endl;
		}
		cout << "=========================================";
	}

	void Swap(HashBucket<T,T2Int>& ht) {
		table.swap(ht.table);
		std::swap(size, ht.size);
	}

private:
	//哈希函数 除留取余法
	size_t Hashfuc(const T& data) {
		T2Int t2int;
		return t2int(data) % table.capacity();
	}

	void Destroy() {
		for (size_t i = 0; i < table.capacity(); i++) {
			Node* cur = table[i];
			while (cur) {
				table[i] = cur->next;
				delete cur;
				cur = table[i];
			}
		}
		size = 0;
	}
	void Checkcapacity() {
		//当有效元素个数存满
		if (size == table.capacity()) {
			//创建一个新的哈希桶
			HashBucket<T, T2Int> newh(Getnextprime(table.capacity()));
			//旧表拆下来
			for (size_t i = 0; i < table.capacity(); i++) {
				Node* cur = table[i];
				while (cur) {
					table[i] = cur->next;
					size_t newloc = newh.Hashfuc(cur->data);
					cur->next = newh.table[newloc];
					newh.table[newloc] = cur;
					newh.size++;
					cur = table[i];
					//先断开cur
				}
			}
			this->Swap(newh);
		}
	}
private:
	std::vector<Node*> table;//哈希表
	size_t size;//有效元素的个数
};

#pragma once


const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
	53ul, 97ul, 193ul, 389ul, 769ul,
	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};

size_t Getnextprime(size_t prime) {
	size_t i = 0;
	for (; i < PRIMECOUNT; i++) {
		if (primeList[i] > prime) {
			return primeList[i];
		}
	}
	return primeList[i];
}

底层为哈希桶的容器：
unordered系列容器
unordered_map
unordered_set
unordered_multimap
unordered_multiset
这些容器底层都是哈希桶结构，在C++11中提出，使用时包含头文件<unordered_map><unorder_set>,查询效率为O(1),应用于不关心元素序列是否有序，追求查找效率的场景中，内部只有正向迭代器。

一、哈希表

1.哈希表概念

可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。它存储的空间叫哈希表。增删查改的时间复杂度都是O(1)。

当向该结构中：

1、插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
2、搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

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

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，时间复杂度为O(1) 。 问题：按照上述哈希方式，若下标4中已经有元素，向集合中插入元素44，会出现什么问题？

2.冲突的概念

冲突是指：不同的关键字key，通过相同的哈希函数，得到了相同的位置，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

3.避免冲突与解决冲突

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

避免冲突的方式有两种，一种是设置合理的哈希函数，另一种是负载因子调节。负载因子越大，则冲突率越大。

3.1 避免冲突的方式1——哈希函数的设计

哈希函数设计原则：
1、哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
2、哈希函数计算出来的地址能均匀分布在整个空间中。
3、哈希函数应该比较简单。

常见哈希函数的设置：

1. 直接定制法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况。
2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
4. 折叠法–(了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
5. 随机数法–(了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
6. 数学分析法–(了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某
   些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
   
   假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

3.2 避免冲突的方式2——负载因子的调节

负载因子和冲突率的关系粗略演示：

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

总结：负载因子的计算公式:当前存入表中的数据个数/表的大小。因此如果要降低负载因子，只能通过增大表的长度来实现。

3.3 解决冲突的方式1——闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。找到下一个空位置的闭散列的方法有两种：

1. 线性探测
   比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入操作：
1、通过哈希函数获取待插入元素在哈希表中的位置。
2、如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

缺点：会把冲突的元素都堆积在一起。

2. 二次探测
   二次探测为了避免线性探测的缺点，它找下一个空位置的方法为：
   
   或者减i的平方。i为冲突的次数，i从1开始。

例如：
当哈希表如下图后，要插入44，但4下标中已经有元素了，此时是第一次冲突，因此计算Hi=(4+1)%10=5 。

此时再插入24，但是4下标已经有元素了，是第一次冲突。再向后一个下标找，此时5下标已经有元素了，是第二次冲突。再向后找，6下标没有元素，则Hi=(4+4)%10=8，则24放入8下标中。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

3.4 解决冲突的方式2——开散列、哈希桶(重要)

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

1. 每个桶的背后是另一个哈希表
2. 每个桶的背后是一棵搜索树(红黑树)

链地址法的图示：当有哈希桶在某个下标下，则哈希表对应下标的值为链表头结点的地址，如果没有则为null。每个结点都由key，value与next组成。

细节操作：
因为是用哈希桶来解决冲突，因此要创建一个每个下标底下都是结点组成的链表的数组Node[] array;，并且用usedSize来记录数组中结点的个数，目的是求出负载因子。而每个哈希桶都是由结点组成的，因此结点类可以定义到哈希桶类里面。

put、resize方法：先根据设计的哈希函数求出对应的下标，找到对应下标后去遍历该下标的链表，**如果已经有相同的key值的结点，则更新完key值中的value后退出。**如果没有，则创建一个哈希桶，设置cur结点从头结点开始，用头插法插入新的结点。当然，插入后要计算出负载因子是否超过了0.75，如果超过就扩容。**扩容后数组的长度会变长，因此每个哈希桶根据新的哈希函数的计算结果跟原来的不同，则要重新哈希。(resize方法)**等全部哈希桶重新哈希完之后，新的数组的引用要赋值给旧的数组的引用。

get方法：首先要根据哈希函数求出对应的下标，再从下标当中去找是否有相同的值的哈希桶，若有，则返回该哈希桶的value值，否则返回-1。

总体代码：

public class HashBucket {

    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node[] array;
    public int usedSize;

    public HashBucket() {
        this.array = new Node[10];
        this.usedSize = 0;
    }


    public void put(int key,int val) {
        //1、确定下标
        int index = key % this.array.length;
        //2、遍历这个下标的链表
        Node cur = array[index];
        while (cur != null) {
            //更新val
            if(cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //3、cur == null   当前数组下标的 链表  没要key
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        //4、判断  当前 有没有超过负载因子
        if(loadFactor() >= 0.75) {
            //扩容
            resize();
        }
    }

    public int get(int key) {
        //以什么方式存储的  那就以什么方式取
        int index = key % this.array.length;
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;//
    }

    public double loadFactor() {
        return this.usedSize*1.0 / this.array.length;
    }

    public void resize() {
        //自己创建新的2倍数组
        Node[] newArray = new Node[2*this.array.length];
        //遍历原来的哈希桶
        //最外层循环 控制数组下标
        for (int i = 0; i < this.array.length; i++) {
            Node cur = array[i];
            Node curNext = null;
            while (cur != null) {
                //记录cur.next
                curNext = cur.next;
                //在新的数组里面的下标
                int index = cur.key % newArray.length;
                //进行头插法
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }


    public static void main(String[] args) {
        HashBucket hashBucket = new HashBucket();
        hashBucket.put(1,1);
        hashBucket.put(4,4);
        hashBucket.put(14,14);
        hashBucket.put(24,24);
        hashBucket.put(34,34);
        hashBucket.put(44,44);
        hashBucket.put(54,54);
        hashBucket.put(64,64);

        System.out.println(hashBucket.get(54));
        System.out.println("ffafas");
    }
}

4.哈希表查找成功与查找失败的求法

查找成功和查找失败是将数据都填入哈希表后再求的。

4.1 查找成功的求法

一个哈希表如下图：

假设现在要查找4，则根据哈希函数Hash(key)=key%array.length，找到了4下标，因为4下标下的数据就是4，则查找一次就成功，1和9数据的查找成功次数求法也是一致。
假设此时要查找24，则先根据哈希函数求出下标为4，但是4下标的数据是4，而不是24，算查找一次。此时往后移一个单位，发现是44不是我们查找的24，则算查找第二次。此时再往后移一个单位，发现是24，算是查找的次数是第三次。

因此上图中查找成功的平均查找长度：(1+1+2+3+1)/5=8/5。

如果找9下标的值查找的不是要查找的数据，则返回到0下标开始找，并且找9下标失败后算查找1次。

4.2 查找失败的求法

一个哈希表如下图：

第一次假如找数据1，则根据哈希函数Hash(key)=key%array.length求得下标为1，假设下标1中的数据不是我们找的数据1，算查找失败了一次，则向后移一个单位去找。此时下标2的值为空，则说明查找失败，算查找失败了两次。

假如此时找数据44，根据哈希函数求得下标为4，但此时下标4下的数据不是44，则没有保证在查找成功的前提下去查找。因此向后移一个单位去找，此时发现下标5的数据是44，则查找失败的次数从此时才开始计算。我们还是要假设当前5下标是查找失败的，算查找失败一次，则再向后移一个单位去找。还是一样，假设下标6的值不是44，查找失败，则向后移一个单位去找。到下标7后，发现该下标的数据为空，则肯定是查找失败，这次也算查找一次，因此查找失败的长度加起来一共有三次。

注：查找失败的操作是从真正找到要找的值开始向后找下一个空的地方。

二、用泛型实现开散列与开散列在源码上的底层实现

1.用泛型实现开散列

用泛型实现哈希表则它的key和val都是引用类型，不能跟上面的一样直接用大于小于号比较。

步骤：首先定义一个类Person创建带有一个参数的构造方法。再将HashBuck类变为泛型类，直接再类名后加<K,V>，并且哈希表中每个下标的值都是一个链表，链表由结点组成，因此要设置public Node<K,V>[] array = (Node<K,V>[])new Node[10];。

因为我们的key是引用类型，不能直接用哈希函数去求下标，那么如何将一个引用转化为一个数值去求下标呢？

此时我们自己实现的类(key)要同时实现equals和hashcode方法，hashcode方法是为了将一个引用类型转换为一个数值从而达到去求它要存储的对应的下标。equals方法是判断两个引用是否是相同的。

如：
当之间用== 比较，则比较的是地址，为false。

class Student {
    public int id;

    public Student(int id) {
        this.id = id;
    }
}
public class Test {
    public static void main(String[] args) {
        Student student1 = new Student(12);
        Student student2 = new Student(12);
        System.out.println(student1==student2);
    }
}
//打印结果：false

但是重写equals方法后，如下例子相当于判断是否是相同的一个人，因为它们的id都相同。

class Student {
    public int id;

    public Student(int id) {
        this.id = id;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
public class Test {
    public static void main(String[] args) {
        Student student1 = new Student(12);
        Student student2 = new Student(12);
        System.out.println(student1.equals(student2));
    }
}
//打印结果：true

面试问题：

1. hashcode和equals的区别？
   答：如果在HashMap中，hashcode的作用是定位当前key值应该存储的下标位置。equals的作用是在经过hashcode定位某个下标后，遍历链表，比较哪个key是相同的。
2. 为什么hashcode和equals要同时出现？
   答：在HashMap中，首先要经过hashcode定位存储的下标，但是如果要获取某个key时，要用到equals方法，因此在HashMap中hashcode和equals是配套使用的。因此以后在hashmap中要存放自己自定义的数据类型，一定要在自定义的数据类型的类里面重新hashcode和equals方法。
3. 当两个数据的equals相同，则hashcode相同吗？那如果两个数据的hashcode相同，equals一定相同吗？如果两个数据的hashcode不同，则equals一定相同吗？
   答：当两个数据的equals相同，hashcode一定相同。如果两个数据的hashcode相同，equals不一定相同。如果两个数据的hashcode不同，则equals一定不相同。

总体代码：

class Person {
    public String id;

    public Person(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
class HashBuck<K,V> {
    static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K,V>[] array = (Node<K,V>[])new Node[10];
    public int usedSize ;

    public void put(K key,V val) {
        int hash = key.hashCode();
        int index = hash%array.length;
        Node<K,V> cur = array[index];
        while(cur!=null) {
            if(cur.val.equals(val)) {
                return;
            }
            cur=cur.next;
        }
        Node<K,V> node = new Node<>(key,val);
        node.next=array[index];
        array[index]=node;
        usedSize++;
        if(loadFactor()>=0.75) {
            resize();
        }
    }
    public void resize() {
        Node<K,V>[] newArray = (Node<K,V>[])new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while(cur!=null) {
                int hash = cur.key.hashCode();
                int index = hash% newArray.length;
                Node<K,V> curNext = cur.next;
                cur.next=newArray[index];
                newArray[index]=cur;
            }
        }
        array=newArray;
    }

    public double loadFactor() {
        return usedSize*1.0/array.length;
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash%array.length;
        Node<K,V> cur = array[index];
        while(cur!=null) {
            if(cur.key.equals(key)) {
                return cur.val;
            }
            cur=cur.next;
        }
        return null;
    }
}
public class Test {
    public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");
        HashBuck<Person,String> hashBuck = new HashBuck<>();
        hashBuck.put(person1,"zjr");
        System.out.println(hashBuck.get(person2));
    }
}

2.开散列在源码上的底层实现

哈希桶的基本原理在3.4小节中已经提到，那么在Java当中它是如何去实现开散列的呢？
注：Java中HashMap和HashSet的底层都是开散列的处理方式。

在存放的时候：
1、找当前位置链表中是否有相同的key。
2、当数组超过64，并且有一个链表超过8时，链表就变成一棵红黑树来处理，它查找的效率更快。
3、JDK1.8后，数组中当有元素插入时链表实现的是尾插法。

点入Java中的HashMap学习它的源码：
1、

在HashMap类当中定义了一个结点类，并且实现了Map.Entry<K,V>，说明HashMap当中有结点的组成。

2、默认的初始容量为16。
3、数组的最大长度为2^30

4、默认的负载因子0.75f

5、变为红黑树的前提是数组的大小超过64

6、HashMap中的数组名为table，初始长度为0。

7、调用无参的构造方法是将负载因子赋值。

2.1 HashMap底层面试题

要想会面试题，必须把下面的图以及参考部分的源码看懂。

第一次put：

第二次put：

冲突时如何去调整：

对应第一题：

1、如果new HashMap(19)，bucket数组多大？ 答：2^5=32 。
2、HashMap什么时候开辟bucket数组占用内存？ 答：第一次put时。
3、hashmap何时扩容？ 答：负载因子为0.75f时。
4、当两个对象的hashcode相同会发生什么？ 答：哈希冲突或碰撞。
5、如果两个键的hashcode相同，你如何获取值对象？ 答：在hashcode的数组位置开始遍历链表。
6、你了解重新调整HashMap大小存在什么问题吗？ 答：重新哈希。

一、哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，通过这种方式，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为 O(1)。
这个映射函数叫做哈希(散列)函数，存放记录的数组叫做哈希(散列)表。

最典型的例子是计数排序，将要排序的数组每个元素和新开辟的数组的下标进行映射。

向哈希表中插入和搜索元素的过程如下：
先用哈希函数将被要插入或查找的键值转化为数组的一个索引。

• 插入元素： 根据索引位置，将元素存放到此位置。
• 搜索元素： 根据索引，找到存储在该索引位置的元素。

在理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。这就是哈希冲突的问题。

二、哈希函数

2.1. 直接定址法(常用)

取关键字的某个线性函数作为散列地址：hash(key)=A*key + B
优点：简单、均匀
缺点：实现需要知道关键字的分布情况，并且只适合查找比较小，且连续分布的情况
适用场景：查找字符串中，第一次出现的单词：构建一个数组 hash[ch-‘a’] 即为对应的地址
不适用场景：给一批数据， 1 5 8 100000 像这数据跨度大，数据元素不连续，很容易造成空间浪费

2.2. 除留余数法(常用)

设散列表中允许的地址数为m，通常是取一个不大于m，但是最接近或者等于m的质数num，作为除数，按照哈希函数进行计算hash(key)= key%num, 将关键码转换成哈希地址
优点：使用场景广泛，不受限制。
缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。

2.3. 几种不常用的方法

1. 平方取中法

hash(key)=key*key 然后取函数返回值的中间的几位，作为哈希地址
比如 25^2 = 625 取中间的一位 2 作为哈希地址

比较适合不知道关键字的分布，而位数又不是很大的情况

2. 折叠法

将关键字从左到右分割成位数相等的几部分(最后一部分可以短些)，然后将这几部分叠加求和，并且按照散列表长度，取最后几位作为散列地址

适用于不知道关键字分布，关键字位数比较多的情况

3. 随机数法

选取一个随机函数，取关键字的随机函数值，作为它的哈希地址，hash(key) = random(key)，random为随机函数

通常用于关键字长度不等的情况

4. 数学分析法

通过实现分析关键字，来获取哈希地址

比如用每个人的手机号码充当关键字，如果采用前三位作为哈希地址，那么冲突的概率是非常大的。如果采用的是中间3位那么冲突的概率要小很多

常用于处理关键字位数比较大的情况，且事前知道关键字的分布和关键字的若干位的分布情况

三、哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希映射地址，这种现象称为哈希冲突或哈希碰撞。

解决哈希冲突通常有两种方法：闭散列（开放地址发）和开散列（链地址法）。

四、闭散列

闭散列也叫做开放地址法，当发生哈希冲突的时候，如果哈希表未被填满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置的"下一个"空位置中去，寻找下一个空位置的方法有线性探测法和二次探测法。

4.1. 线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个位置为止

优点：实现非常简单
缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据"堆积"，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要进行多次比较，导致搜索效率降低。

4.2. 负载因子

随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加。
我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子（载荷因子）：

散列表的载荷因子定义为 α = 填入表中的元素 / 散列表的长度

α是散列表装满程度的标志因子，α越大表明装入表中的元素越多，产生冲突的可能性也就越大，反之填入表中的元素越少，冲突可能性越低，空间利用率也就越低

闭散列：一般将载荷因子控制在 0.7-0.8以下，超过0.8查表时候的缓存不中率会按照指数曲线上升(哈希可能性冲突越大)，因此一般hash库中，都将α设置在0.8以下。 闭散列，千万不能为满，否则在插入的时候会陷入死循环

开散列/哈希桶：一般将载荷因子控制在1。超过1，那么链表就挂得越长，效率也就越低

4.3. 二次探测

线性探测的缺陷是产生哈希冲突，容易导致冲突的数据堆积在一起，这是因为线性探测是逐个的找下一个空位置.
二次探测为了缓解这种问题(不是解决)，对下一个空位置的查找进行了改进(跳跃式查找)：
POS = (H+i²)%m
其中：i=1、2、3…
H是发生哈希冲突的位置
m是哈希表的大小

4.4. 插入和删除操作

插入操作比较简单：通过哈希函数插入元素在哈希表中的位置，如果发生了哈希冲突，则使用线性探测或二次探测寻找下一个空位置插入元素。
但是删除操作比较麻烦，采用闭散列处理哈希冲突时，不能随便删除哈希表中已有的元素，如果直接删除元素，会影响其他元素的搜索（比如原来下标为40的元素因为前面删除了一个元素下标变成了39）。
因此线性探测采用标记的伪删除法来删除下一个元素。

4.5. 扩容操作

为了减少冲突，哈希表的大小最好是素数。为了能够获取每次增容后的大小，将需要用到的素数序列提前用一个数组存储起来，当我们需要增容时就从该数组当中进行获取。

4.6. 代码实现

namespace CloseHash//闭散列
{
	enum State
	{
		EMPTY,
		EXIT,
		DELETE
	};
	template<class K,class V>
	struct  HashData
	{
		pair<K, V> _kv;
		State _state=EMPTY;//节点的状态默认为空
	};
	template<class K>
	struct  Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct  Hash<string>
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			for (auto ch : s)
			{
				value += ch;
				value *= 131;
			}
			return value;
		}
	};
	template<class K, class V,class HashFunc=Hash<K>>
	struct  HashTable
	{
	public:
		size_t GetNextPrime(size_t prime)
		{
			static const int PRIMECOUNT = 28;//给成静态，不用重复生成
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 429496729ul
			};

			size_t i = 0;
			for (; i < PRIMECOUNT; ++i) {
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[i];
		}
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
			{
				return false; //插入失败
			}

			//进行扩容检测
			if (_n == 0 || (_n / _table.size() * 10 > 7))//当前个数为0或者载荷因子超过了,则进行扩容
			{
				//size_t newsize = _size == 0 ? 10 : 2 * _tables.size();//初始化给10，后续扩容两倍

				//选取素数
				size_t newsize = GetNextPrime(_table.size());

				//扩容之后，需要重新计算元素的位置

				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(newsize);

				for (auto& e : _table)
				{
					if (e._state == EXIT)
						newHT.Insert(e._kv);
				}
				_table.swap(newHT._table);//进行交换
			}
	
			HashFunc hf;
			size_t start= hf(kv.first) % _table.size();
			size_t index = start;
			//探测后面的位置，线性探测或二次探测
			size_t i = 1;
			while (_table[index]._state == EXIT)
			{
				index =start+i;
				index %= _table.size();
				++i;
			}
			_table[index]._kv = kv;
			_table[index]._state = EXIT;
			++_n;
			return true;
		}
		HashData<K,V>* Find(const K& key)
		{
			if (_table.size() == 0) return nullptr;

			HashFunc hf;
			size_t start = hf(key) % _table.size();
			size_t index = start;
			size_t i = 1;
			while (_table[index]._state != EMPTY)
			{
				if (_table[index]._state== EXIT
					&&_table[index]._kv.first == key)
				{
					return &_table[index];
				}
				index = start + i;
				index %= _table.size();
				++i;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}

	private:
		vector<HashData<K,V>> _table;
		size_t _n = 0;
	};
}

五、开散列（哈希桶）

开散列又名哈希桶/开链法，首先对关键码集合采用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表串联起来，各个链表的头节点存储在哈希表中

5.1. 开散列扩容

与闭散列不同，开散列需要负载因子达到1的时候才进行扩容。
因为在理想的情况下每个桶下面只有一个节点。哈希桶的载荷因子控制在1，当大于1的时候就进行扩容，这样平均下来，每个桶下面只有一个节点；

与闭散列进行比较： 看起来哈希桶之中存储节点的指针开销比较大，其实不然。闭散列的负载因子需要保证小于0.7，来确保有足够的空间降低哈希冲突的概率，而表项的空间消耗远远高于指针所占的空间效率，因此哈希桶更能节省空间。

5.2. 代码实现

namespace OpenHash//开散列
{
	template<class K,class V>
	struct HashNode
	{
		HashNode<K, V>*_next;
		pair<K, V>_kv;
		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			,_kv(kv)
		{} 
	};
	template<class K>
	struct  Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct  Hash<string>
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			for (auto ch : s)
			{
				value += ch;
				value *= 131;
			}
			return value;
		}
	};
	template<class K, class V, class HashFunc = Hash<K>>
	struct HashTable
	{
	public:
		typedef HashNode<K, V> Node;
		Node* Find(const K& key)
		{
			HashFunc hf;
			if (_table.size() == 0) return nullptr;
			size_t index = hf(key) % _table.size();
			Node* cur = _table[index];
			//在桶中进行查找
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			HashFunc hf;
			if (Find(kv.first)) return false;//列表里已经存在kv

			//负载因子到1时进行增容
			if (_n == _table.size())
			{
				vector<Node*>newtable;
				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
				newtable.resize(newSize);

				//遍历旧表中的节点，重新计算映射位置，挂到新表中
				for (size_t i = 0; i < _table.size(); ++i)
				{
					if (_table[i])
					{
						Node* cur = _table[i];
						while (cur)
						{
							//记录原来cur后面的节点
							Node* next = cur->_next;
							size_t index = hf(cur->_kv.first) % newtable.size();
							//头插
							cur->_next = _table[index];
							_table[index] = cur;
							cur = next;
						}
						_table[i] = nullptr;
					}
				}
				_table.swap(newtable);
			}
			size_t index = hf(kv.first) % _table.size();
			Node* newnode = new Node(kv);
			newnode->_next = _table[index];
			_table[index] = newnode;
			++_n;
		}
		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t index = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[index];
			//在桶中找到对应的节点进行删除
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//头结点的情况
					if (_table[index] == cur)
					{
						_table[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			//要删的节点不存在
			return false;
		}
	private:
		vector<Node*> _table;
		size_t _n=0;//有效数据的个数
	};
}

六、闭散列和开散列的比较

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

资料参考：
哈希表、哈希桶的实现
哈希表底层探索
数据结构之（一）Hash（散列）
哈希之开散列，闭散列