哈希表(散列表) -- 概念原理以及代码实现

心已赠人 2023-07-07 15:58 48阅读 0赞

**目录**

什么是哈希表?

哈希函数

1. 闭散列

线性探测

闭散列的扩容

两个小问题

闭散列的简单实现

2.开散列

开散列的增容

开散列与闭散列比较

有迭代器的开散列实现

开散列实现unordered\_map

哈希的应用

--------------------

# 什么是哈希表? #

> 在常见的线性表(顺序表, 链表, 栈, 队列), 二叉搜索树, AVL树, 红黑树等这些数据结构中, 想要查找某一个元素时, 免不了的要
> 
> 进行遍历比较. 在时间复杂度上, 线性结构为O(n), 二叉搜索树在O(log₂N)~O(n), AVL和红黑树打倒O(log₂N). 虽然AVL和红黑
> 
> 树这两个平衡树的时间复杂度已经达到了O(log₂N), 但当数据量特别庞大时, 还是比较慢的. 而哈希表在查找方面就显得非常
> 
> 高效了.

> 哈希的思想和我们常用的数组有着异曲同工之处, 数组中知道要想访问某个元素, 只需要知道这个元素的下标即可, 通过下标
> 
> 就可以直接访问这个元素. 因此可以这样访问的效率可达到O(1) . 
> 
> 在哈希结构中, 存储的是键值对Key-Value,  通过建立Key与Value的映射关系, 我们可以直接通过Key值, 访问到Value,
> 
> 就如同数组中, 通过下标访问到元素的值, 所以哈希表在不考虑**哈希冲突**的情况下, 查询效率为O(1). (后面说什么是哈希冲
> 
> 突).   再来看其哈希表的概念也就好理解了.

> **散列表 (Hash table, 也叫哈希表)**, 是根据关键码值Key而直接进行访问对应数据Value的**一种数据结构**也就是说, 它通过把关
> 
> 键码值Key映射到表中一个位置来访问数据Value, 以加快查找的速度. 这个映射函数叫做**散列函数**,  存放数据的数组叫做散
> 
> 列表 . 在C++ 11后的STL中的unordered系列的关联式容器底层实现都是哈希表, 包括 unordered\_map, unordered\_set
> 
> unordered\_multimap, unordered\_multiset .
> 
> 哈希函数的功能简单说就是:  地址 = HashFun(Key), 通过这个地址, 就能访问到Key所对应的Value或者知道这组Key-Value
> 
> 需要存在哪个位置, 下面来详细看哈希函数.

--------------------

# 哈希函数 #

当向哈希表中:

> **插入元素时**, 根据待插入元素的关键码Key, 用哈希函数计算出(HashFunc(Key))该元素的哈希地址(存储位置)并按此位置进
> 
> 行存放.
> 
> **查找元素时,** 对元素的关键码进行同样的计算HashFunc(Key)，把求得的函数值当做元素的哈希地址 在哈希表中按此位置取
> 
> 元素比较, 若关键码相等, 则查找成功

哈希结构中, 能根据Key计算出哈希地址的的函数就是哈希函数 .

举个栗子:

对于数据集合 \{ (1, 10), (7, 20), (6, 30), (4, 40), (5, 50) \};  小括号元素是(Key, Value)

HashFunc(Key) = key % capacity ; 这里的Key是整数, 无需转换(言外之意是Key还能是其他数据类型), capacity 假设为 10, 则有,

![20200224142828347.png][]

例如插入(1, 10)时, key % capacity = 1 % 10 = 1, 所以(1, 10)存储在了哈希地址为1的位置 .

那如果再插入(11, 56)呢, key % capacity = 11 % 10 = 1.  我们发现, 当插入(11, 56)时, 哈希地址为1的位置已经有了(1, 10).

那么,称这种现象为 **哈希冲突(或哈希碰撞). **即, 具有不同关键码的元素(也就是不同元素)通过哈希函数得到了同一个哈希地址.

哈希冲突是**无法完全避免**的, 也就是说是一定会存在的, 但是可以尽量减少的,  方法就是**设计一个****更加合理的哈希函数. **

但就算哈希函数再合理也会有一定概率会发生哈希冲突, 那么当哈希冲突发生了该怎么办呢?

解决办法常见的有两种: **闭散列**( 开放定址法 )和**开散列**( 链地址法或开链法 ).

闭散列和开散列下面再说, 先来看看哈希函数的设计方法 .

首先, 哈希函数的设计必须遵循下面几个准则:

> 1. 哈希函数的定义域必须包括需要存储的全部关键码, 散列表有m个地址时, 其值域必须在0到m-1之间.
> 
> 2. 哈希函数计算出来的地址能均匀分布在整个空间中(减少哈希冲突).
> 
> 3. 哈希函数应该比较简单. (如果需要大量复杂的计算, 反而拖慢了效率)

**常见方法**

**1. 直接定制法--(常用)**

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

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

**2. 除留余数法--(常用)**

设散列表中允许的地址数为m, 取一个不大于m, 但最接近或者等于m的质数p作为除数, 按照哈希函数:

HashFunc(key) = key% p (p<=m), 将关键码转换成哈希地址.

值得注意的是, 当p是质数(素数)时, 除留余数法发生哈希冲突的概率会大大减少 .

**3. 平方取中法--(了解)**

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址 .

再比如关键字为4321，对它平方就18671041，抽取中间的3位671(或710)作为哈希地址.

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

**4. 折叠法--(了解)**

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，

取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

**5. 随机数法--(了解)**

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数.

通常应用于关键字长度不等时采用此法

**6. 数学分析法--(了解)**

有学生的生日数据如下：

年.月.日  
                                     75.10.03  
                                     75.11.23  
                                     76.03.02  
                                     76.07.12  
                                     75.04.21  
                                     76.02.15  
                                           ...

经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好 .

最后, 还是要强调一点, 哈希函数设计的**越精妙**，产生**哈希冲突的可能性就越低**，但是**无法避免哈希冲突.**

--------------------

# 1. 闭散列 #

> **闭散列, **也叫开放定址法, 当发生哈希冲突时, 如果哈希表未被装满, 说明在哈希表中必然还有空位置, 那么可以把要存的元素
> 
> 存放到冲突位置中的 “下一个” 空位置中去. 那如何寻找"下一个"空位置呢？

方法有两种, **线性探测**和**二次探测,** 先来看线性探测 .

### **线性探测** ###

> 顾名思义, 线性探测是线性的, 从发生冲突的位置开始往后寻找空位置, 存到找到的第一个空位置. 当找到哈希表的末尾
> 
> 还没找到时, 从开头往后再找.

**插入**

接着上面的例子, 再插入(11, 56), key % capacity = 11 % 10 = 1. 从冲突位置往后找, 找到第一个空位置则填入 .

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

**删除**

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索. 比如删除元素

(1, 10), 如果直接删除掉, (11, 5) 查找起来可能会受影响. 因此线性探测采用标记的伪删除法来删除一个元素.  即, 哈希表每个空间

给个标记, EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除.

enum State {
        EMPTY, 
        EXIST, 
        DELETE
    };

例如现在已经删掉了(1, 10), 又要删除(11, 5), 如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]

哈希函数通过11计算出的哈希地址还是1, 当找到1位置时, 发现原来的元素已经删了, 说明原来这个位置存在过元素, 那就有这种可

能, 当插入Key值为11的元素时, 可能发生了哈希冲突, 所以可能找"下一个" 空位(EMPTY)再存储, 所以还会向后寻找, 直到找到并

删除或者碰到下一个空位置EMPTY, 则就是没找到.

**优点 : **实现非常简单

**缺点:** 一旦发生哈希冲突, 所有的冲突连在一起, 容易产生数据 “堆积”, 即：不同关键码占据了可利用的空位置，使得寻找某关键码

的位置需要许多次比较，导致搜索效率降低. 如何缓解呢？二次探测可以缓解这个问题.

**二次探测**

线性探测的缺点是数据容易"堆积", 这与其找 "下一个"空位置的方法有关,  线性探测是从冲突发生位置依次往后找. 所以容易堆积.

而二次探测改变了找空位的方法, 即 Hi = (H0 + i²)% m, 或者Hi = (H0 - i²)% m . 其中: i = 1,2,3…,  H0是通过散列函数Hash(x)对元

素的关键码 key 进行计算得到的位置，m是表的大小 .

--------------------

那么问题来了, 线性探测或是二次探测要是找不到下一个空位置呢, 或者说存满了呢?

### **闭散列的扩容** ###

其实是一定会找到的, 为什么呢?   原因如下:

> **散列表的载荷因子** α = **存储的元素个数 / 散列表的长度**
> 
> α 越大, 表明当前散列表中的元素越多, 产生哈希冲突的可能性也就越大, 所以说为了尽量避免哈希冲突, α 的大小是需要控制
> 
> 的. 对于闭散列来说, 载荷因子 α 必须控制在0.8 一下, 当超过0.8后, 哈希冲突的发生几率会大幅增加.  因此一些采用闭散列
> 
> 的Hash库,如java的系统库, α 就为 0.75, 当超过0.75时必须扩容.

所以说, 当插入一个新元素时, 至少还有20%的空间没有利用, 所以一定会找到"下一个"空位置 .

> 对于二次探测来说, 当表的长度为质数(素数)且表装载因子 α 不超过0.5时, 每次哈希冲突, 二次探测的位置, 都不会重复, 比
> 
> 起线性探测, 效率更高,  但空闲的空间比线性探测更多, 空间利用率更低.

那么如何扩容呢?

> 当insert一个元素时, 函数内部首先要检测器载荷因子是否小于限定, 如小于则不需要扩容, 如不小于, 则扩容, 另外申请一个
> 
> 更大的空间, 将旧表中的元素一个一个重新insert. 所以说闭散列扩容是非常耗时的 .

其实闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷.

说了这么多, 其实在C++11之后的STL中的unordered系列的四个容器, 底层虽然是哈希, 但却不是闭散列实现的, 底层实现是开散

列. 所以先实现一个简单的闭散列.

### 两个小问题 ###

**1. Key非整形**

哈希函数只能接受整型的key值, 例如除留余数法, 但其实Key-Value键值对Key和Value类型可以是任意的, 那么当Key不是整型

时, 又该如何处理呢?

这时候就可以我们自己来定义一个方法, 将非整型的Key值转换成唯一对应的无符号整型, 将这个方法给到我们的哈希结构, 那么怎

么让哈希结构获取到我们的自定义方法呢? 我们可以将自定义方法以仿函数的形式或函数指针的形式作为模板参数传给哈希结构.

例如:

template<class T> // 整形数据不需要转化, 直接返回
    class DefHashF {
    public:
        size_t operator()(const T& val) {
            return val;
        }
    };
    class StrInt {// key为字符串类型，需要将其转化为整形
    public:
        size_t operator()(const string& s) {
            const char* str = s.c_str();
            unsigned int seed = 131; // 31 131 1313 13131 131313
            unsigned int hash = 0;
            while (*str) {
                hash = hash * seed + (*str++);
            }
            return (hash & 0x7FFFFFFF);
        }
    };
    //在哈希结构内部, 就可以直接使用模板参数HF将key转换成无符号整型
    template<class K, class V, class HF>
    class HashTable {
    // ……
    private:
        size_t HashFunc(const K& key) {
            return HF()(key)%_ht.capacity();
        }
    };

当Key的类型是string时, 只需要在第三个模板参数传入StrInt

**2. 对于哈希函数常用的除留余数法, 如何快速获取下一个素数**

前面说到, 对于除留余数法, 模数时素数时, 哈希冲突的概率更小. 所以散列表的长度都是素数, 当需要扩容时, 扩容的大小就为下一

个素数的大小, 如果每次都计算得出素数, 未免太麻烦, 那么我们在写代码时可以直接将能用到的素数都给出来, 当发生扩容时直接

取用就行了, 如下 :

template<class K, class V, class HF>
    class HashTable {
    // ……
    private:
        static size_t s_m_primeTable[30];
    // ……   
    };
    size_t HashTable<K, V, SW>::s_m_primeTable[30] = {
    		11,         23,         47,         89,        179,
    		353,        709,       1409,       2819,       5639,
    		11273,      22531,      45061,      90121,     180233,
    		360457,     720899,    1441807,    2883593,    5767169,
    		11534351,   23068673,   46137359,   92274737,  184549429,
    		369098771,  738197549, 1476395029, 2952790016ul, 429496729ul
    };

## 闭散列的简单实现  ##

***Hash.h***

#pragma once
    #include<vector>
    using namespace std;
    enum State {
    	EMPTY,
    	EXIST,
    	DELETE
    };
    class dealInt {
    public:
    	int operator()(const int key) {
    		return key;
    	}
    };
    template <class K, class V, class SW = dealInt>
    class HashTable {
    	struct elem {//哈希表元素, pair包含键值与数据, m_state为标志位
    		pair<K, V> m_val;
    		State m_state;
    
    		elem(const K& key = K(), const V& val = V(), State state = EMPTY) :
    			m_val(key, val),
    			m_state(state)
    		{}
    	};
    	vector <elem> m_table;
    	size_t m_size;
    	static size_t s_m_primeTable[30];
    	int m_prime;
    	//并没有记录哈希表的capacity的值, 因为m_table的size值就为其容量, 详见构造函数
    
    	size_t HashFun(const K& key) {//哈希函数,使用除留余数法
    		return SW()(key) % capacity();//仿函数先求出能够计算的整型(因为key值不一定是整型)
    	}
    
    	void reserve() {
    		vector<elem> tmp;
    		m_table.swap(tmp);
    		m_table.resize(s_m_primeTable[++m_prime]);
    		m_size = 0;//交换后的m_table的为空
    
    		for (auto& e : tmp) {
    			if (e.m_state == EXIST) {
    				insert(e.m_val);
    			}
    		}
    	}
    
    public:
    	HashTable(size_t capacity = s_m_primeTable[0]) :
    		m_table(capacity),
    		m_size(0),
    		m_prime(0)
    	{}
    
    	size_t capacity() {
    		return m_table.size();
    	}
    
    	bool insert(const pair<K, V>& val) {
    		if (m_size * 10 / capacity() > 7) {//数据所占总容量70%以上时, 需要扩容
    			//因为此时哈希冲突发生的概率变得非常大, 所以需要扩容
    			reserve();
    		}
    		int k = HashFun(val.first);
    
    		while (m_table[k].m_state == EXIST) {//若发生冲突, 此处运用线性探测法解决
    			//即, 依次往后找, 知道找到空位置
    			if (m_table[k].m_val == val) {//若已有相同的, 即插入失败
    				return false;
    			}
    			++k;
    			if (k == capacity()) {//当找到最后(最后已经判断完), 需要重头再来
    				k = 0;
    			}//此处不会出现重复循环判断的, 因为在70%时就会扩容, 所以一定会有空闲的位置
    		}
    
    		m_table[k].m_val = val;
    		m_table[k].m_state = EXIST;
    		++m_size;
    		return true;
    	}
    
    	int find(const K& key) {
    		int k = HashFun(key);
    		while (m_table[k].m_state != EMPTY) {//如果等于空直接跳出循环, 没找到返回-1
    			if (m_table[k].m_state == EXIST && m_table[k].m_val.first == key) {
    				return k;
    			}
    			++k;
    
    			if (k == capacity()) {
    				k = 0;
    			}
    		}
    		return -1;
    	}
    
    	bool erase(const K& key) {
    		int k = find(key);//先找有没有
    
    		if (k != -1) {//有
    			--m_size;
    			m_table[k].m_state = DELETE;
    			return true;
    		}
    
    		return false;//没有则删除失败
    	}
    
    	size_t size() {
    		return m_size;
    	}
    
    	bool empty() {
    		return m_size == 0;
    	}
    
    	void Swap(const HashTable& ht) {
    		m_table.swap(ht.m_table);
    		size_t tmp = m_size;
    		m_size = ht.m_size;
    		ht.m_size = tmp;
    	}
    	void clear() {
    		m_size = 0;
    		m_table.clear();
    		m_table.resize(s_m_primeTable[0]);
    		m_prime = 0;
    	}
    };
    template <class K, class V, class SW>
    size_t HashTable<K, V, SW>::s_m_primeTable[30] = {
    		11,         23,         47,         89,        179,
    		353,        709,       1409,       2819,       5639,
    		11273,      22531,      45061,      90121,     180233,
    		360457,     720899,    1441807,    2883593,    5767169,
    		11534351,   23068673,   46137359,   92274737,  184549429,
    		369098771,  738197549, 1476395029, 2952790016ul, 429496729ul
    };

测试入口 main.cpp, 由于只是简单实现, 我们通过调试来看是否完成了基本的功能.

#include<iostream>
    #include"Hash.h"
    using namespace std;
    
    int main() {
    	HashTable<int, int> ht;
    
    	ht.insert(pair<int, int>(1, 5));
    	ht.insert(pair<int, int>(2, 7));
    	ht.insert(pair<int, int>(5, 6));
    	ht.insert(pair<int, int>(6, 8));
    	ht.insert(pair<int, int>(12, 9));
    	ht.insert(pair<int, int>(16, 4));
    	ht.insert(pair<int, int>(23, 11));
    	ht.insert(pair<int, int>(27, 13));
    	ht.insert(pair<int, int>(33, 13));
    	ht.insert(pair<int, int>(36, 13));
    	ht.insert(pair<int, int>(27, 13));
    	ht.insert(pair<int, int>(33, 13));
    	ht.insert(pair<int, int>(36, 13));
    	ht.erase(33);
    	int n = ht.find(27);
    	int m = ht.find(222);
    	ht.clear();
    	ht.insert(pair<int, int>(1, 5));
    	ht.insert(pair<int, int>(2, 7));
    	ht.insert(pair<int, int>(5, 6));
    	ht.insert(pair<int, int>(6, 8));
    	ht.insert(pair<int, int>(12, 9));
    	ht.insert(pair<int, int>(16, 4));
    	ht.insert(pair<int, int>(23, 11));
    	ht.insert(pair<int, int>(27, 13));
    	ht.insert(pair<int, int>(33, 13));
    	ht.insert(pair<int, int>(36, 13));
    
    	ht.insert(pair<int, int>(27, 13));
    	ht.insert(pair<int, int>(33, 13));
    	ht.insert(pair<int, int>(36, 13));
    	system("pause");
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]

# 2.开散列 #

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

HashFunc(key) = key % capacity    , capacity = 10;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3][]                        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 4][]

图1                                                                                                      图2

插入数据集合 \{ (1, 10), (7, 20), (6, 30), (4, 40), (5, 50) \}如上图1.                          再插入新元素(11, 5), 如上图2

## 开散列的增容 ##

> 桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非
> 
> 常多，这会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那这个条件要怎么确认呢？开散列最好的情
> 
> 况是: 每个哈希桶中刚好挂一个节点，此时再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的
> 
> 个数时，可以给哈希表增容。
> 
> 当扩容后, 旧的数据要重新一个一个的insert到新的哈希桶中, 比较耗时.

### 开散列与闭散列比较 ###

> 开散列中增加了一个指针数组, 每个节点中又增加了指向下一个节点的指针, 似乎增加了存储开销. 事实上, 由于闭散列必须
> 
> 保持大量的空闲空间以确保搜索效率，如闭散列要求载荷因子a <= 0.7~0.8, 而表项所占空间又比指针大的多，所以使用链
> 
> 地址法反而比开地址法节省存储空间.

## 有迭代器的开散列实现 ##

***HashBucket.h***

#pragma once
    #include<vector>
    using namespace std;
    
    template <class V>
    class HashBucketNode {//元素节点
    public:
    	V m_val;
    	HashBucketNode * m_next;
    	HashBucketNode(const V& val = V()) :
    		m_val(val),
    		m_next(nullptr)
    	{}
    
    	template<class K, class V, class KeyOfVal, class HF>
    	friend class Iterator;
    
    	template<class K, class V, class KeyOfVal, class HF>
    	friend class HashBucket;
    };
    class dealInt {
    public:
    	int operator()(const int& key) {
    		return key;
    	}
    };
    // K:关键码类型
    // V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是unordered_set,V 为 K
    // KeyOfValue: 因为V的类型不同，通过value取key的方式就不同, 所以可能需要传入自定义的方法
    // HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
    template<class K, class V, class KeyOfVal, class HF = dealInt>
    class Iterator {
    public:
    	HashBucket<K, V, KeyOfVal, HF>* m_hbpos;//直到桶在哪儿, 方便找上一个或下一个桶
    	HashBucketNode<V>* m_node;//具体节点
    	Iterator(HashBucket<K, V, KeyOfVal, HF>* hbpos = nullptr, HashBucketNode<V>* node = nullptr) :
    		m_hbpos(hbpos),
    		m_node(node)
    	{}
    
    	Iterator(const Iterator& it) :
    		m_hbpos(it.m_hbpos),
    		m_node(it.m_node)
    	{}
    
    	V& operator*() {
    		return m_node->m_val;
    	}
    
    	V* operator->() {
    		return &(m_node->m_val);
    	}
    
    	Iterator operator++() {
    		HashBucketNode<V>* t = m_node;
    		m_node = m_node->m_next;
    		if (!m_node) {//为空
    			size_t tmp = m_hbpos->HashFunc(KeyOfVal()(t->m_val)) + 1;//下一个桶的下标
    			for (; tmp < m_hbpos->capacity(); ++tmp) {
    				if (m_hbpos->m_table[tmp]) {
    					m_node = m_hbpos->m_table[tmp];
    					break;
    				}
    			}
    		}
    		return *this;
    	}
    
    	Iterator operator++(int) {
    		Iterator tmp = *this;
    		this->operator++();
    		return tmp;
    	}
    
    	bool operator==(const Iterator& data) const {
    		return m_node == data.m_node;
    	}
    
    	bool operator!=(const Iterator& data) const {
    		return m_node != data.m_node;
    	}
    };
    template<class K, class V, class KeyOfVal, class HF = dealInt>
    class HashBucket {
    	vector<HashBucketNode<V>*> m_table;
    	size_t m_size;
    	static size_t s_m_primeTable[30];
    	size_t m_primePos;
    
    	template<class K, class V, class KeyOfVal, class HF>
    	friend class Iterator;
    
    	typedef Iterator<K, V, KeyOfVal, HF> Iterator;
    
    	size_t HashFunc(const K& key) {
    		return HF()(key) % capacity();
    	}
    
    	void checkCapacity() {//检查是否需要扩容, 若需要, 则扩容
    		int oldcapacity = capacity();
    		if (oldcapacity == m_size) {//此时哈希冲突发生概率100%, 此时扩容
    			vector<HashBucketNode<V>*> tmp(s_m_primeTable[++m_primePos]);
    			m_table.swap(tmp);
    			m_size = 0;
    
    			for (auto e : tmp) {
    				for (; e; e = e->m_next) {
    					insert(e->m_val);
    				}
    			}
    		}
    	}
    public:
    	HashBucket(const size_t capacity = s_m_primeTable[0]) :
    		m_table(capacity, nullptr),
    		m_size(0),
    		m_primePos(0)
    	{}
    
    	~HashBucket() {
    		clear();
    	}
    
    	size_t capacity() {
    		return m_table.size();
    		//return s_m_primeTable[m_primePos];
    	}
    	Iterator begin() {
    		for (size_t i = 0; i < capacity(); ++i) {
    			if (m_table[i]) {
    				return Iterator(this, m_table[i]);
    			}
    		}
    		return Iterator(this, nullptr);
    	}
    	Iterator end() {
    		return Iterator(this, nullptr);
    	}
    	pair<Iterator, bool> insert(const V& val) {
    		checkCapacity();//首先检查是否需要扩容
    		int k = HashFunc(KeyOfVal()(val));
    		HashBucketNode<V>* cur = m_table[k];
    		while (cur) {
    			if (KeyOfVal()(cur->m_val) == KeyOfVal()(val)) {
    				return pair<Iterator, bool>(Iterator(this, cur), false);
    			}
    			cur = cur->m_next;
    		}
    		cur = new HashBucketNode<V>(val);
    		cur->m_next = m_table[k];
    		m_table[k] = cur;
    		++m_size;
    		return pair<Iterator, bool>(Iterator(this, m_table[k]), true);//因为是头插, 所以返回头
    	}
    
    	Iterator find(const K& Keyval) {
    		int k = HashFunc(Keyval);
    		HashBucketNode<V>* cur;
    		for (cur = m_table[k]; cur; cur = cur->m_next) {
    			if (KeyOfVal()(cur->m_val) == Keyval) {
    				break;
    			}
    		}
    		return Iterator(this, cur);
    	}
    
    	pair<Iterator, bool> erase(const K& Keyval) {
    		Iterator f = find(Keyval);
    		int n = HashFunc(Keyval);
    		if (f.m_node) {
    			Iterator tmp = f;
    			if (m_table[n] == f.m_node) {
    				m_table[n] = m_table[n]->m_next;
    			}
    			else {
    				for (HashBucketNode<V>* cur = m_table[n]; cur->m_next; cur = cur->m_next) {
    					if (cur->m_next == f.m_node) {
    						cur->m_next = cur->m_next->m_next;
    						break;
    					}
    				}
    			}
    			++tmp;
    			delete f.m_node;
    			--m_size;
    			return pair<Iterator, bool>(tmp, true);
    		}
    		return pair<Iterator, bool>(Iterator(this, nullptr), false);
    	}
    
    	size_t size() {
    		return m_size;
    	}
    	bool empty() {
    		return 0 == m_size;
    	}
    	void clear() {
    		HashBucketNode<V>* tmp;
    		m_size = 0;
    		for (auto head : m_table) {
    			while (head) {
    				tmp = head;
    				head = head->m_next;
    				delete tmp;
    			}
    		}
    		for (auto& e : m_table) {
    			e = nullptr;
    		}
    	}
    	size_t bucket_count()const {//返回哈希桶中桶的个数
    		size_t count = 0;
    		for (auto& i : m_table) {
    			if (i != nullptr) {
    				++count;
    			}
    		}
    		return count;
    	}
    	size_t bucket_size(size_t n)const {//返回n号桶中的元素个数
    		size_t count = 0;
    		for (HashBucketNode<V>* i = m_table[n]; i; i = i->m_next) {
    			++count;
    		}
    		return count;
    	}
    	size_t bucket(const K& key) {//返回key对应几号桶
    		return HashFunc(key);
    	}
    };
    template<class K, class V, class KeyofValue, class HF>
    size_t HashBucket<K, V, KeyofValue, HF>::s_m_primeTable[30] = {
    	11, 23, 47, 89, 179,
    	353, 709, 1409, 2819, 5639,
    	11273, 22531, 45061, 90121, 180233,
    	360457, 720899, 1441807, 2883593, 5767169,
    	11534351, 23068673, 46137359, 92274737, 184549429,
    	369098771, 738197549, 1476395029, 2952790016ul, 429496729ul
    };

测试***main.cpp***

#include"HashBucket.h"
    using namespace std;
    
    class KeyofValueint {
    public:
    	int operator()(int key) {
    		return key;
    	}
    };
    
    void test() {
    	cout << "test1:\n";
    	HashBucket<int, int, KeyofValueint> hb;
    	hb.insert(6);
    	Iterator<int, int, KeyofValueint> q = hb.insert(9).first;
    	hb.insert(17);
    	hb.insert(16);
    	hb.insert(19);
    	hb.insert(27);
    	hb.insert(61);
    	hb.insert(98);
    	hb.insert(26);
    	hb.insert(63);
    	hb.insert(39);
    	hb.insert(28);
    	pair<Iterator<int, int, KeyofValueint>, bool> p = hb.insert(100);
    	pair<Iterator<int, int, KeyofValueint>, bool> p2 = hb.insert(100);
    	cout << *p.first << endl;
    	p = hb.erase(9);
    	p2 = hb.erase(10101);
    	cout << *p.first << endl << endl;
    	for (auto & e : hb) {
    		cout << e << endl;
    	}
    }
    
    int main() {
    	test();
    	system("pause");
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 5][]

## 开散列实现unordered\_map ##

写在另一篇博客中, [戳链接（￣︶￣）↗https://blog.csdn.net/qq\_41071068/article/details/104361724][https_blog.csdn.net_qq_41071068_article_details_104361724]

# 哈希的应用 #

先写到这,  还会更新

[20200224142828347.png]: https://img-blog.csdnimg.cn/20200224142828347.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200224172856379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200224200348697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200224204202992.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200224213549638.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020022421344723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200224215551435.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_qq_41071068_article_details_104361724]: https://blog.csdn.net/qq_41071068/article/details/104361724