C++哈希学习

哈希

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较，比如平衡树要不断和节点值进行大小比较。这些结构搜索的效率取决于搜索过程中元素的比较次数。

如果能不经过任何比较，直接从表中得到要搜索的元素，像数组直接访问下标一样，会方便很多。 实现这种结构的关键是通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系。

哈希就是通过哈希函数产生关键码，根据关键码存放数据的一种结构，哈希函数有很多种，这里介绍常见的除留余数法

除留余数法：

当前哈希表容量为10，现插入一个5，让数值模容量即可找到需要存放的位置。

模容量是为了防止越界，如果传入20，模10后得2，仍在哈希容量范围内。

假如待插入的数据取模得到的下标位置已经存放了数据，这种情况被称为哈希冲突，哈希函数设计的越精妙，哈希冲突发生的可能性就越低，但哈希冲突不可避免。

哈希冲突示例：

闭散列（开放定址法）

前面的除留余数法是通用的哈希函数，但得到关键码后如何存储又分为多种方式，其中一种方式叫闭散列

在闭散列中，哈希表的数据附带三种状态，分别是EMPTY（空）,EXIST（存在）,DELETE（被删除）。为什么节点要有状态呢？设想在哈希中查找元素时，必然从关键码对应下标开始找，如果下标处的内容为空，说明可以产生这个关键码数据从来没有被插入，后面更不可能存在相同关键码对应的数据。但“为空“实际上存在两种情况：从未插入过数据或数据被删除，下面示例被删除的数据如何导致误判，找不到6

这时如果将被删除处标记为DELETE,遍历时遇到DELETE就继续往后找，就可以解决此问题

而状态为EMPTY或DELETE的位置，都可以插入，这样子不会浪费状态已经删除数据的空间

负载因子

如果不扩容，哈希表迟早会装满，哈希冲突的解决又导致哈希效率下降，所以引入负载因子用于判断什么时候扩容

负载因子=有效数据个数/当前容量，如负载因子为0.6，当前容量为10，准备存放第7个有效数据时，发现6/10=0.6达到负载因子，扩容，再将原先哈希表中的元素重新插入到扩容后的哈希表中。这样关键码与下标不匹配的数据有机会重新洗牌，从而提高效率。见下图：

下标6因为被15占用，导致6只能存到下标7，所以6、7两个下标处存放的都是关键码不匹配的数据，扩容后出现了下标15，从而让15和6插入到正确的位置，提高了哈希的效率。

然而负载因子并不能随意设定，负载因子越大（尽可能不扩容），空间利用率越高，时间效率越低（如前文所述，存在大量不匹配数据）

拉链法

闭散列最大的缺陷就是空间利用率低（扩容后有些地方没存到数据），这也是哈希的缺陷。

而拉链法空间利用率更高，因为哈希表不再直接用于存储数据，而是存储链表，如此一来，哈希表下标和数据对应的关键码必然匹配，此时效率取决于链表的长短

拉链法的扩容

10个指针即可存储所有无符号整形，但链表也随之增长，查找、删除等操作效率也会很低。所以和闭散列一样，也需要通过扩容进行“洗牌”。拉链法负载因子设置为1，即只要数据个数和桶的数量相同，就进行扩容。按这个定义，平均每个桶可以装一个数据（实际上无法这么理想），这正是时间效率最高的情况（同时空间效率最低）

哈希的模拟实现：

哈希函数定义

根据前文提到的除留余数法，要得到关键码就要让传入值模容量，但并不是所有传入值都支持这样的运算，如string,同时也应当支持用户自定义哈希函数，所以这里让哈希函数作为模板参数，同时为string特别写一份根据ASCII码值生成关键码的哈希函数供用户直接使用

//比较通用的哈希函数 template<typename T> class HashFunc { public: size_t operator()(const T& Key) { return size_t(Key); } }; //为什么除了string以外的多数其它类型也能用上面仿函数呢？因为size_t可以把负数、小数都换成正整数，不然找不到数组索引 template<>//这里通过模板的特化对string做特别处理 class HashFunc<string> { public: size_t operator()(const string& Key) { size_t hash = 0; for (auto i : Key) { hash = 131 * hash + i;//这个操作可以极大降低两个字符串ASCII码值之和结果相同的概率 } return hash; } };

为什么哈希函数不能直接在hash里面定义

如果哈希函数直接在hash中定义，相当于锁死了该函数，用户无法自定义这个函数，哈希函数也无法处理自定义类型,即便不需要处理自定义类型，有时对string比较大小的并不依据ASCII码值之和，可能只需要对首字母进行大小比较，这时也需要给予用户自定义权限。

哈希表节点定义

template<class T> class Hash_Node { public: Hash_Node(const T&kv):_value(kv) , _next(nullptr){} //delete node*会自动调用释放函数，所以node不需要再写析构 Hash_Node() :_next(nullptr){} T _value; Hash_Node<T>* _next; };

哈希表成员变量如下

template<class K, class V,typename hashfunc> class Hashtable { public: typedef Hash_Node<pair<K,V>> node; hashfunc func; private: vector<node*>_table; size_t _n; size_t _capacity; };

查找函数

node* Find(const K& Key) { for (auto i : _table) { node* cur = i; while (cur) { if (cur->_value.first == Key) { return i; } cur = cur->_next; } } return nullptr; }

插入函数

因为拉链法节点顺序无需在意，所以插入节点采用头插的方式，代码简洁，效率高

bool Insert(const pair<K, V>& kv) {//hash的Insert要的是 //先检查是否存在 if (Find(kv.first)) { return false; } //再检查扩容 if (_n==_capacity) {负载因子为1就扩容 vector<node*>temp; temp.resize(_capacity * 2); _capacity = temp.size(); //用头插的方法比尾插快的多 for (auto i : _table) {//遍历原表每一个桶 node* cur = i; while (cur) {//让cur一直往下走，相当于把原表的节点直接拉到新表 node* next = cur->_next; size_t pos = func(cur->_value.first) % temp.size(); cur->_next = temp[pos]; temp[pos] = cur; cur = next;//这里是合理的，不会导致覆盖 } } swap(temp,_table); } size_t pos = func(kv.first) % _capacity; node* input = new node(kv); input->_next = _table[pos]; _table[pos] = input; _n++; return true; }

为什么扩容不复用Insert

复用需要传值，要再拷贝两次，不划算，不如直接把链表节点拿来用

为什么扩容不创建一个新的哈希表，最后直接交换哈希对象的指针?

this指针默认是只读的，不可能作为swap的参数

删除函数

//删除 bool Erase(const K& Key) { //这里无法找到父亲节点，所以不能复用find for (auto i : _table) { node* parent = nullptr; node* cur = i; while (cur) { //如果此桶只有一个节点,不能直接delete，不然会造成断裂，应当由table统一释放 //所以只能让它指向一个空桶（next） if (cur->_value.first == Key) { if (parent==nullptr) { node* temp = cur; cur = cur->_next; delete temp; } else { parent->_next = cur->_next; delete cur; } return true; } parent = cur; cur = cur->_next; } } }

为什么erase不能复用find?find只能找到当前节点，如果要删除当前节点，还要把当前节点的父亲和孩子节点连接起来，所以不能复用。

为什么桶只有一个值且该值为待删除值时不直接delete?

这样做后续遍历哈希表的时候会发生访问错误，因为这个桶的空间被释放了。所以要让待删除节点指向空节点，这样桶里仍然存放有值。

析构函数（特别强调）

//数组里的node*所指向的内容要通过析构函数释放 ~Hashtable() { for (auto i : _table) { node* cur = i; while (cur) { node* temp = cur; cur = cur->_next; delete temp; } } }

为什么需要定义析构函数

闭散列中的vector存储的是data类对象，当哈希表生命周期结束的时候，自动调用哈希表（vector类ing）的析构函数，而哈希表中存储的是自定义data类，又会自动调用data的析构函数。而哈希桶中的vector存储的是节点指针，指针是一个普通类型，系统只会把这些指针本身占用的空间释放，而不会自动释放指针所指向的空间，因此需要自定义析构函数，释放各节点内指针指向的空间。

unordered_map和unordered_set封装

库函数中的unordered_map和unordered_set的使用类似于map和set,但底层结构为哈希

模拟实现比较复杂，需要清楚实现步骤，按顺序走，不然后面bug贼多

实现顺序：

哈希表->unordered_map和unordered_set基本封装（搭外壳,让哈希函数和keyofvalue跑通)->普通迭代器->const迭代器(难)->insert/find返回值->operator[]

unordered_map和unordered_set对hash封装的模拟实现

下面先给出除去函数实现的伪代码

哈希表本身代码

//hash.h #pragma once #include <vector> #include <string> #include <utility> // for pair using namespace std; namespace Hash_Bucket { // --- 1. 哈希函数 --- // 通用哈希函数模板 template<typename T> class HashFunc { public: size_t operator()(const T& Key); }; // string 类型的特化版本 template<> class HashFunc<string> { public: size_t operator()(const string& Key); }; // --- 2. 节点类 --- template<class T> class Hash_Node { public: Hash_Node(const T& kv); // 带值构造 Hash_Node(); // 默认构造 public: T _value; // 存储的数据（对于 map 是 pair，对于 set 是 K） Hash_Node<T>* _next; // 指向下一个节点的指针 }; // --- 3. 哈希表前置声明 --- template<class K, class V, typename keyofvalue, typename hashfunc> class Hashtable; // --- 4. 迭代器类 --- template<class K, class V, class Ptr, class Ref, typename keyofvalue, typename hashfunc> class Hash_Iterator { public: // 类型定义 typedef Hash_Iterator<K, V, Ptr, Ref, keyofvalue, hashfunc> Self; typedef Hash_Node<V> node; typedef Hashtable<K, V, keyofvalue, hashfunc> table; public: // 构造函数 Hash_Iterator(node* Node, const table* Table); Hash_Iterator(const Hash_Iterator& it); // 运算符重载 Self& operator++(); // 前置++ Ptr operator->(); // 箭头运算符 Ref operator*(); // 解引用 bool operator==(const Self& input); bool operator!=(const Self& input); public: // 成员变量 table* _table; // 指向所属的哈希表（用于跨桶跳转） node* _node; // 指向当前节点 }; // --- 5. 哈希表主体 --- template<class K, class V, typename keyofvalue, typename hashfunc = HashFunc<K>> class Hashtable { public: // 友元声明（允许迭代器访问私有成员） template<class K, class V, class Ptr, class Ref, typename keyofvalue, typename hashfunc> friend class Hash_Iterator; // 类型定义 typedef Hash_Iterator<K, V, V*, V&, keyofvalue, hashfunc> iterator; typedef Hash_Iterator<K, V, const V*, const V&, keyofvalue, hashfunc> const_iterator; typedef Hash_Node<V> node; public: // 构造与析构 Hashtable(); ~Hashtable(); // 核心功能接口 pair<iterator, bool> Insert(const V& kv); // 插入数据 iterator Find(const K& Key); // 查找数据 bool Erase(const K& Key); // 删除数据 void Print(); // 打印调试 // 迭代器接口 iterator begin(); iterator end(); private: // 成员变量 vector<node*> _table; // 桶数组（指针数组） size_t _n; // 当前元素个数 size_t _capacity; // 桶的数量（容量） }; }

unordered_map伪代码

// unorder_map.h #pragma once #include "hash.h" namespace unordermap { template<class K, class V> class unorder_map { public: // --- 1. 键值提取仿函数 --- // 用于告诉底层哈希表，如何从 pair<const K, V> 中拿到键 K class KeyOfValue { public: const K& operator()(const pair<const K, V>& kv); }; // --- 2. 类型定义 --- // 复用底层 Hashtable 的迭代器 typedef typename Hash_Bucket::Hashtable<K, pair<const K, V>, KeyOfValue>::iterator iterator; typedef typename Hash_Bucket::Hashtable<K, pair<const K, V>, KeyOfValue>::const_iterator const_iterator; // --- 3. 核心功能接口 --- // 插入键值对 // 返回 pair<迭代器, bool>，bool 表示插入是否成功 pair<iterator, bool> insert(const pair<const K, V>& input); // 下标访问运算符 // 如果键不存在则插入默认值，如果存在则返回已有值的引用 V& operator[](const K& key); // --- 4. 迭代器接口 --- iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: // --- 5. 成员变量 --- // 底层实际维护数据的哈希表 // K: 键类型 // pair<const K, V>: 存储的数据类型 // KeyOfValue: 键值提取策略 Hash_Bucket::Hashtable<K, pair<const K, V>, KeyOfValue> _table; }; }

在实现过程中遇到的问题：

unordered_map和unordered_set的对比：

unordered_map的迭代器

typedef typename Hash_Bucket::Hashtable<K, pair<const K,V>, keyofvalue>::iterator iterator; typedef typename Hash_Bucket::Hashtable<K, pair< const K,V>, keyofvalue>::const_iterator const_iterator;

unordered_set的迭代器

typedef typename Hash_Bucket::Hashtable<K, K, keyofvalue>::const_iterator iterator; typedef typename Hash_Bucket::Hashtable<K, K, keyofvalue>::const_iterator const_iterator;

unordered_map的iterator和const_iterator是有区别的，分别对应哈希中的Iterator和const_iterator，而set中的iterator和const_iterator都是哈希中的const_iterator。这是因为unordered_map根据是否被const修饰选择是否更改值，而unordered_set只有键，且不允许修改键。unordered_map迭代器要对key使用const修饰，因为无论普通还是const迭代器，都不能对键进行修改。

insert为什么要先定义一个pair来接收hash层面的insert的返回值，然后再把这个pair返回给set和map层面呢

pair<iterator,bool> insert(K value) { pair<typename table::iterator,bool> temp= _table.Insert(value); return make_pair(iterator(temp.first), temp.second);//这里要再次转换 }

因为"_table.Insert"定义在hash中，而hash中的insert返回的是一个普通迭代器，回到unordered_set和unordered_map层面：unordered_map没有问题，但unordered_set层面只有const_iterator，所以要对拿到手的普通迭代器进行转换。

hash内定义的迭代器：

typedef Hash_Iterator<K, V, V*, V& , keyofvalue, hashfunc> iterator; typedef Hash_Iterator<K, V, const V*, const V&, keyofvalue, hashfunc> const_iterator;

unordered_set的迭代：

typedef typename Hash_Bucket::Hashtable<K, K, keyofvalue>::const_iterator iterator; typedef typename Hash_Bucket::Hashtable<K, K, keyofvalue>::const_iterator const_iterator;

回到原来的问题：为什么Insert不直接这样写呢？

pair<iterator,bool> insert(K value) { return _table.Insert(value); }

返回值pair是一个类，“iterator,bool”是它的模板参数，如果模板参数不同（传iterator和const_iterator），定义出来的类的类型也是不同的，编译器无法完成自动转换。也就是说类模板相同，实例化对象的类型可以不相同。

可能会想，那iterator不能先被隐式转换成const_iterator吗？同理，iterator也是一个类，定义普通迭代器和const迭代器时传给这个类的模板参数就不一样，所以普通迭代器和const迭代器根本就不是一个类型，所以编译器不会支持隐式类型转换。

typedef Hash_Iterator<K, V, V*, V& , keyofvalue, hashfunc> iterator;

iterator的构造函数为什么是这样写的：

Hash_Iterator( node* Node, const table* Table):_table(Table),//这里为什么不能加const？table应当在成员定义时加上const _node(Node){} Hash_Iterator(const iterator& it) :_table(it._table), _node(it._node) {//这里的构造对于普通迭代器是拷贝构造，对于const迭代器是构造函数 }

如前文所述，普通迭代器并不支持编译器自动转换为const迭代器，所以如果想用普通迭代器构造一个const迭代器，就让普通迭代器作为构造函数的参数，再手动转换，这时问题转变为_table指针和_node指针转换const_table指针和const_node指针了，指针是普通类型，编译器支持自动转换。

方括号重载

实现insert以后，就可以实现方括号重载对其进行复用了，注意,set是没有方括号重载的。

而unordered_map的方括号重载只有非const版本需要实现方括号重载，这时候直接复用insert即可，不用再像unordered_set一样先用一个pair去接收参数

V& operator[](const K& key) { return _table.Insert(make_pair(key, V())).first->second; }

其他问题：

1.在类中内部类、typedef以及static函数受访问限定符的限制吗?

是的，只有友元、struct类是不会受到访问限定符的约束。

2.kov和func为什么要在函数中实例化，而不是直接在类内部实例化成为类的成员呢？这个还是有点说法的

首先，这些仿函数直接实例化为成员，每个类对象被实例化的时候开销肯定会增加，不划算。其次，这些仿函数可能是有状态的，直接实例化相当于不初始化，不支持带参构造的仿函数。所以不如运行期间再实例化，更加灵活且划算。

3.关于什么时候要加typename

之前我只关心模板参数可能需要增加typename,实际上，只要是从别的作用域中调用成员，都应该考虑是否要加typename，因为编译器不能确定你调用的到底是类型还是函数声明。比如在unordered_map中定义的迭代器代码,复用了哈希中的迭代器的定义，此时就需要加上一个typename

typedef typename table::iterator iterator;

4.类定义是分先后的，比如不能在类中宏定义一个后于该类定义的类

5.auto操作的是副本，所以要加上一个引用，直接对auto修改无法改变容器内容

6.用户不允许直接构造一个什么都不指向的迭代器，必须有一个明确指向的对象，所以迭代器不支持默认构造函数

哈希的进一步优化

极端场景下，可能某个桶中存放的数据量过大，这时考虑当桶中数据量达到一定值时，将这个桶转换为一颗红黑树(也就是遍历链表，构造红黑树)然后哈希表中原先的桶的节点指针（链表头节点指针）变成了树指针。

经验总结

这次模拟实现没有循序渐进，比如在unorder_set和unorder_map的初步封装存在漏洞的情况下，又去实现迭代器，导致一直在挖坑找坑填坑，花费的时间远超map和set的封装。在写项目之前要有一个大思路，在每个阶段实现后要多调试。