目录

1.undered系列容器

1.1 undered_map

1.1.1 undered_map特点介绍

1.1.2 undered_map接口介绍

1.2 undered_set

2.底层结构

2.1 哈希概念

2.2 哈希冲突

2.3 哈希函数

2.3.1 哈希函数设计原则：

2.3.2 常见哈希函数

1.直接定值法

2.除留余数法

3.平方取中法

4.折叠法

5.随机数法

6.数学分析法

2.4 哈希冲突的解决

2.4.1 闭散列

1.线性探测

2.二次探测

2.4.2 开散列

---

1.undered系列容器

C++STL库中undered系列容器有undered_map与undered_set等,它们也就是我们常说的哈希表。

1.1 undered_map

1.1.1 undered_map特点介绍

undered_map有以下特点：

• undered_map是存储键值对<key,value>的关联式容器。
• 与map不同，undered_map存储的key没有顺序，但同样是通过key索引得到value。
• undered_map中的键值key不可修改且唯一。
• undered_map支持[ ]访问，下标为键值key。如果key不存在，那么会将key进行插入，对应的value为默认值。
• undered_map的通过key访问value的效率比map快

1.1.2 undered_map接口介绍

函数声明	功能介绍
undered_map	构造不同格式的undered_map对象
bool empty()const	检测undered_map是否为空
size_t size()const	获取undered_map有效元素的个数
begin	返回undered_map第一个元素的迭代器
end	返回undered_map最后一个元素的下一个位置的迭代器
cbegin	返回undered_map第一个元素的const迭代器
cend	返回undered_map最后一个元素的下一个位置的const迭代器
operator[]	返回key对应的value
iterator find(const K& key)	返回key在哈希桶的位置
size_t count(const K& key)	返回键值为key的元素的个数
insert	向容器中插入键值对
erase	删除容器中的键值对

1.2 undered_set

undered_set与undered_map类似，只不过存储的只有键值key，但实际底层仍是储存键值对<key,value>,且key=value。它不支持[]访问。其他参考undered_map。

2.底层结构

undered系列容器的效率高的原因是使用了哈希结构。

2.1 哈希概念

平衡树与顺序结构的搜索方式都是通过比较key进行查找，顺序查找的时间复杂度为O(n)，平衡树查找的时间复杂度为O(logn)。

这里我们提出一种理想的查找方式，也就是哈希（散列）方法：

我们提供一个函数HashFunc来建立key与value一一映射的联系，可以类比数学中的自变量x与因变量y，它们通过函数HashFunc来建立联系，这样就可以一次通过key来得到value,时间复杂度也就成了O(1)。

这里的HashFunc称为哈希（散列）函数，构造出来的结果称为哈希（散列）表。

例如对于数据{1,7,4,5,9}：

2.2 哈希冲突

不同key通过相同哈希函数得到相同的哈希地址，这种情况称为哈希冲突或者哈希碰撞。

以上图为例：

我们发现不同的键值4与14通过相同的哈希函数得到了相同的4号哈希地址，这就是哈希冲突。

2.3 哈希函数

发生哈希冲突的一个原因就是选用的哈希函数不够合理。选取的哈希函数越精妙，哈希冲突的概率就越小，但哈希冲突是不可避免的。

2.3.1 哈希函数设计原则：

• 哈希函数的定义域必须包含所有需要储存的键值key。如果哈希表有n个地址空间，那么哈希函数的值域为0~n-1。
• 哈希函数计算出的地址能均匀分布在整个地址空间中。
• 哈希函数应该比较简单。

2.3.2 常见哈希函数

1.直接定值法

取关键字的某个线性函数作为散列地址：Hash(key)=key*n+m。

优点：简单，均匀。

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

适用场景：适合查找小且集中的情况。

2.除留余数法

如果哈希表中的地址数为n,取一个不大于n但最接近n或者等于n的质数作为除数。

按照哈希函数：Hash(key)=key%p(p<=key)得到哈希地址。

3.平方取中法

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

适用于不知道关键字分布情况，而位数不是很大的场景。

4.折叠法

将关键字从左到右分成位数相同的几部分（最后一部分位数可以短一些），然后将这几部分叠加求和，根据哈希表地址个数取最后几位作为哈希地址。

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

5.随机数法

选择一个随机函数，关键字通过随机函数得到的函数值作为哈希地址。

Hash(key)=random(key)(random为随机函数)。

适用于关键字长度不等时的情况。

6.数学分析法

设有n个d位数，每位上有r种不同的符号，每种符号出现的频率不一定相同，可能在某几位上分布均匀，每种符号出现的机会均等，在某几位上分布不均匀，某几位符号反复出现，这时可根据哈希表的长度来选取分布均匀的若干位作为哈希地址。

例如以手机号作为关键字，手机号的前几位可能相同（即“在某几位上分布不均匀，某几位符号反复出现”），后几位不同（即“可能在某几位上分布均匀，每种符号出现的机会均等”）。这时就可以手机号后几位作为哈希地址。

适用关键字位数比较大，知道关键字分布且若干位分布均匀的情况。

2.4 哈希冲突的解决

解决哈希冲突的两种常见解决方法为：开散列、闭散列。

2.4.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未填满，就说明哈希表中还有空余位置，就可以把发生哈希冲突的key存到“下一个”空位置。如何寻找下一个位置呢？

这里提出荷载因子的概念：有效数据个数/哈希表长度，荷载因子越大，代表哈希表中的元素越多，发生哈希冲突的概率就越大，开放定址法的荷载因子应在0.7~0.8左右。超过了就要扩容。

1.线性探测

从发生冲突的位置开始，依次往后开始寻找空位置。

代码实现：

// 哈希函数采用除留余数法
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};
//状态表示增加了DELETE，因为在查找发生哈希冲突的元素时，我们会从冲突位置开始往后找，直到找到或者遇到空位置，此时如果我们删除了处于两个发生哈希冲突的元素之间的元素时，如果我们直接将状态改为空，那么就找不到第二个发生哈希冲突的元素了，因为中间有空位置。
enum State
{EXIST,EMPTY,DELETE};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first) != nullptr) return false;//扩容if (_n * 10 / _tables.size() == 7){HashTable<K, V> newtable;newtable._tables.resize(_tables.size() * 2);for (int i = 0; i < _tables.size();i++){if(_tables[i]._state==EXIST)newtable.Insert(_tables[i]._kv);}swap(newtable._tables, _tables);}Hash t;int n = _tables.size();int pos = t(kv.first) % n;while (_tables[pos]._state != EMPTY){pos++;pos %= n;}_tables[pos]._kv = kv;_tables[pos]._state = EXIST;_n++;return true;}HashData<K, V>* Find(const K& key){Hash t;int n = _tables.size();int pos = t(key) % n;while (_tables[pos]._state!=EMPTY){if (key == _tables[pos]._kv.first&&_tables[pos]._state==EXIST) return &_tables[pos];pos++;pos %= n;}return nullptr;}bool Erase(const K& key){HashData<K, V>* target = Find(key);if (target == nullptr) return false;target->_state = DELETE;_n--;return true;}private:vector<HashData<K, V>> _tables;size_t _n = 0;  // 表中存储数据个数
};

优点：实现简单

缺点：一旦方式哈希冲突，所有的冲突连在一起，就容易发生数据的“堆积”，前一个元素因为哈希冲突而占了后一个元素的位置，以此发生堆积。

2.二次探测

Hash(key)=(key+d)%n,d={1^2,-1^2,2^2,-2^2,3^2,-3^2,……}。

发生哈希冲突时，先往后隔2个位置找，如果还是冲突，就往前隔2个位置找，如果还是冲突，就往后隔2^2个位置找，依次类推（按照d中的元素进行查看）。

开放定址法的缺陷就是空间利用率低，这也是哈希的缺陷。

2.4.2 开散列

开散列又叫链地址法（拉链法），我们将发生哈希冲突的元素挂在同一个哈希地址上。

这里具有相同哈希地址元素的集合称作桶，每个桶中的元素通过单链表连接。

闭散列的荷载因子为1。

代码实现：

// 哈希函数采用除留余数法
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};// K 为 T 中key的类型
// T 可能是键值对，也可能是K
// KeyOfT: 从T中提取key
// Hash将key转化为整形，因为哈希函数使用除留余数法
template<class K, class T,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public:HashTable(){_tables.resize(10, nullptr);}// 哈希桶的销毁~HashTable(){for (int i = 0; i < _tables.size(); i++){Node* tmp = _tables[i];while (tmp){Node* next = tmp->_next;delete tmp;tmp = next;}}}// 插入值为data的元素，如果data存在则不插入bool Insert(const T& data){KeyOfT kot;if(Find(kot(data))) return false;Hash t;int n = _tables.size();//扩容if (_n / n == 1){HashTable newtable;newtable._tables.resize(n * 2);for (int i = 0; i < n; i++){Node* tmp = _tables[i];while (tmp){Node* next = tmp->_next;tmp->_next = newtable._tables[t(kot(tmp->_data)) % (n * 2)];newtable._tables[t(kot(tmp->_data)) % (n * 2)] = tmp;tmp = next;}_tables[i] = nullptr;}swap(_tables, newtable._tables);}int pos = t(kot(data)) % n;Node* newnode = new Node(data);newnode->_next = _tables[pos];_tables[pos] = newnode;_n++;}// 在哈希桶中查找值为key的元素，存在返回true否则返回falsebool Find(const K& key){Hash t;KeyOfT kot;int n = _tables.size();Node* tmp = _tables[t(key) % n];while (tmp){if (key == kot(tmp->_data)) return true;tmp = tmp->_next;}return false;}// 哈希桶中删除key的元素，删除成功返回true，否则返回falsebool Erase(const K& key){Hash t;KeyOfT kot;int n = _tables.size();int pos = t(key) % n;Node* cur = _tables[pos];Node* pre = nullptr;while (cur){if (kot(cur->_data) == key) break;pre = cur;cur = cur->_next;}if (cur == nullptr) return false;if (pre == nullptr){_tables[pos] = cur->_next;}else{pre->_next = cur->_next;}delete cur;_n--;return true;}private:vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数
};

开散列相比闭散列更节省空间。