哈希知识详解

目录

一、哈希

二、哈希函数

  1、直接定值法

  2、除留余数法

三、哈希冲突

四、哈希冲突解决

1、闭散列(开放定值法)

         闭散列代码

 2、哈希桶

          哈希桶的结构

         查找方法

        插入方法

        删除方法

         析构

        迭代器 

        完整哈希桶代码 

五、通过哈希桶封装 unordered_map 和 unordered_set

---

一、哈希

以前，在面对海量数据的查找时，最快就是红黑树 logN，无法满足需求。

于是探索出了另一种用关键字 key 值与其存储位置建立映射的思想，让查找效率提升到 O(1) ，这个就是哈希。

二、哈希函数

  1、直接定值法

        ①、直接定值法：用当前的值与数组建立一一对应的关系。

        例如，a,b,c,d 在数组 v 上的映射为 v[0],v[1],v[2],v[3]

        ②、直接定值法的缺点：如果给的值直接跨度较大就非常消耗空间。

        例如：1,1000 在数组 v 上的映射为 v[1] v[1000] 。为了存两个数开了1000多空间，十分浪费。

  2、除留余数法

        除留余数法就是：映射位置为 key 值模上空间大小。( i = key % 空间大小 )

三、哈希冲突

        用上述方法可能会有哈希冲突的问题(也就是不同的 key 值 映射到了同一个地方)

        如：除留余数法，空间大小为7,key值 1 和 8 会映射在同一个地方(1%7 = 8%7 = 1)

四、哈希冲突解决

1、闭散列(开放定值法)

        假设空间大小为 N

        线性探测：假设用除留余数法，i = key % N，如果找到的当前位置有值了，那就向后找，直到找到空位置，放进去。

        查找：执行 i = (i + 1) % N，不断向后查找(后面找完了，就从第一个位置开始继续找)，直到找到空位置。

        可以看到，哈希冲突越多，我们查找的效率越低。因此，我们可以想办法让数据的个数和空间大小维持在一个比例，降低哈希冲突。也就是维持 负载因子 / 载荷因子 的大小

        (负载因子 / 载荷因子 = 数据个数 / 空间大小 )。

        闭散列(开放定值法) 一般将这个比例维持在 0.7 左右。

        删除：如上图，如果我们删除 8，那么查找 16 的时候就找到空位置 2，无法找到 16。因此，我们删除不能只是简单的将值删除，还应该将表的每个位置增设标志位。

 

         闭散列代码

        插入：

        1、判断当前 负载因子 / 载荷因子 是否超过 0.7，如果超过，就扩容。

        2、因为扩容后的空间大小变化了，因此，所有的数据需要重新插入，我们可以定义一个临时对象 HashTable temp，把当前所有数据插入 temp 中，再将 temp 中的数据换出来，完成重新插入。

        3、根据新的空间大小和 key 值，找到映射位置。如果当前位置有值，就向后查找空闲位置(标志位不为 EXIST)，找到就插入

        查找：

        1、先判断当前 key 值的映射位置 keyi 是否正确，如果不对，继续向后查找

        2、 如果查找到了，返回下标；如果没找到，找了一圈回到 keyi ，则返回 -1

        删除：

        1、通过 key 用 Find 找到 keyi，如果不存在，就返回

        2、如果存在，则将标志位设为 DELETE 并 --_size  

// 定义的状态
enum Status
{EMPTY,EXIST,DELETE
};// 哈希表中的数据
template<class K, class V>
struct HashData
{typedef HashData<K, V> self;
public:HashData():_status(EMPTY){}/*HashData(const std::pair<K, V>& value){_data = value;_status = EXIST;}self& operator=(const self& val){_data = val._data;_status = val._status;return *this;}*/
public:std::pair<K, V> _data; // 数据Status _status; // 状态
};template<class K, class V>
class HashTable
{
public:static const double rate;
public:HashTable(int n = 0){_table.resize(n);}void Insert(const std::pair<K, V>& value){// 空间大小int n = _table.size();// 如果比例超过 rate 就扩容if (_size >= rate * n){// 扩容为原来的 2 倍 (哈希表的大小最好为素数，这里就简化一下)int newcapacity = n == 0 ? 4 : 2 * n;// 因为扩容后空间大小变了，因此每个数据的映射位置也会变化，所以要重新插入// 定义一个临时的哈希表HashTable<K, V> temp(newcapacity);// 把原来的数据重新插入新表中for (auto e : _table){if(e._status == EXIST)temp.Insert(e._data);}// 将新表换出来_table.swap(temp._table);_size = temp._size;n = newcapacity;}// 通过除留余数法 找到对应下标int keyi = value.first % n;// 找到第一个标记位不为 EXIST 的位置，放入while (_table[keyi]._status == EXIST){keyi = (keyi + 1) % n;}_table[keyi]._data = value;_table[keyi]._status = EXIST;_size++;}// 找到了就返回下标，没找到返回 -1int Find(const K& key){int n = _table.size();// 通过除留余数法 找到对应下标int keyi = key % n;if (_table[keyi]._data.first == key){return keyi;}// 从第 2 个位置继续查找int pos = (keyi + 1) % n;while (_table[pos]._status != EMPTY){// 转一圈回来了，全是 DELETE 和 EXISTif (pos == keyi)break;if (_table[pos]._data.first == key){return pos;}pos = (pos + 1) % n;}return -1;}void Erase(const K& key){int n = _table.size();// 如果没找到，就直接返回int pos = Find(key);if (pos == -1) return;// size-- 并设置标志位_table[pos]._status = DELETE;_size--;}private:std::vector<HashData<K, V>> _table; // 哈希表int _size; // 当前负载
};
template<class K, class V>
const double HashTable<K, V>::rate = 0.7; // 比例为 0.7

---

 2、哈希桶

        与闭散列不同，哈希桶(也叫做拉链法) 是在对应位置放单链表，当有哈希冲突的时候，就把值尾插挂在对应位置的单链表下。

        优化：当一个位置的单链表的节点个数超过 8 个时，可以考虑挂红黑树。

---

          哈希桶的结构

// 哈希表下挂的 单链表的节点
template<class T>
struct HashNode
{HashNode(){}HashNode(const T& val):_val(val){}HashNode<T>* _next = nullptr; // next 指针，指向下一个位置T _val = T(); // 值
};// K 表示 key(关键字) 的类型
// T 表示 值 的类型
// KOFT 表示通过 T 找到对应的 key 的仿函数(封装map和set就可以一起使用了)
// map 的值是 pair<K, T>，set 的值和 key 一样，因此，通过传入仿函数就可以让它们一起使用
// HASH 表示哈希函数，如，string 就需要通过哈希函数转化才能求位置
template<class K, class T, class KOFT, class HASH>
class HashBucket
{// typedefusing node = HashNode<T>;// 设置 负载因子 / 载荷因子 的比例static const double rate;// 静态成员变量，类内定义，类外初始化public:HashBucket(int n = 0){// 将数组的大小开为 n_table.resize(n, nullptr);}private:std::vector<node*> _table;// 哈希表，每个位置存一个单链表size_t _size;// 数据个数
};
template<class K, class T, class KOFT, class HASH>
const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;// 初始化比例

         查找方法

        1、先判断哈希表是否为空

        2、通过哈希函数得到值，用除留余数法得到对应的下标

        3、通过下标找到单链表 _table[keyi] ，在这个单链表中遍历查找即可

iterator Find(const K& key)
{// 如果表是空的，那么不需要查找if (_table.size() == 0)return end();// 通过哈希函数，除留余数法 得到对应下标 keyiHASH hashfunc;int keyi = hashfunc(key) % _table.size();KOFT kot;// 从单链表中查找值node* head = _table[keyi];while (head){// 找到返回if (kot(head->_val) == key){return iterator(head, this);}head = head->_next;}// 没找到返回 end()return end();
}

        插入方法

        1、先判断 key 值是否已经存在，存在就不插入了

        2、如果 负载因子 / 载荷因子 的比例超过 定义的 rate，扩容

                扩容思想和上面的闭散列类似，因为哈希桶的大小发生变化，要重新插入原有值。我们可以先定义一个临时的大小为 newcapacity 的哈希桶，再将原本的数据插入新的临时哈希桶中，只要把临时桶的资源换出来，就完成了重新插入。

        3、通过哈希函数和 key 找到对应下标，通过下标找到该插入的单链表

        4、创建新节点，头插到单链表中，将 _size++ 完成插入 

// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器
std::pair<iterator, bool> Insert(const T& val)
{// 拿到 key 值KOFT kot;const K& key = kot(val);// 通过Find判断是否存在对应的 keyiterator it = Find(key);if (it != end())return std::make_pair(it, false);int n = _table.size();if (_size >= n * rate){// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍int newcapacity = _size == 0 ? 4 : 2 * n;// 设置临时对象HashBucket temp(newcapacity);for (node* head : _table){// 因为容量发生变化，所以所有数据的映射位置发生变化// 将所有数据重新插入 tempwhile (head){temp.Insert(head->_val);head = head->_next;}}// 将 temp 中的资源换出来_table.swap(temp._table);_size = temp._size;n = newcapacity;}// 得到对应下标 keyiHASH hashfunc;int keyi = hashfunc(key) % n;// 创建新节点node* newnode = new node(val);// 头插newnode->_next = _table[keyi];_table[keyi] = newnode;// ++size++_size;return std::make_pair(iterator(newnode, this), true);
}

        删除方法

        1、和插入一样，先进行查找，如果没找到 key，就直接返回

        2、通过 key 和哈希函数得到对应的下标，找到对应单链表

        3、问题转化为在单链表中查找节点，找到返回即可

bool Erase(const K& key)
{// 先进行查找，没找到直接返回iterator iter = Find(key);if (iter == end())return false;// 通过 key 得到下标HASH hashfunc;int keyi = hashfunc(key) % _table.size();KOFT kot;node* prev = nullptr;node* cur = _table[keyi];while (cur){if (kot(cur->_val) == key){if (prev == nullptr)_table[keyi] = cur->_next;elseprev->_next = cur->_next;delete cur;break;}prev = cur;cur = cur->_next;}return true;
}

         析构

        遍历哈希表，将所有单链表释放。 

~HashBucket()
{// 释放所有单链表的节点for (node* head : _table){while (head){node* next = head->_next;delete head;head = next;}}
}

        迭代器 

        1、迭代器基本结构 

        哈希桶的迭代器需要节点，因为进行++操作时，需要查找表的下一个非空节点，因此还需要这个哈希桶的指针。

         哈希桶的 operator== 和  operator!= 判断节点的地址是否相同即可

        解引用*和->，* 返回值引用，-> 返回值的地址

        注意：因为通过哈希表指针使用了私有成员 _table ，因此要把迭代器设为友元，或设置 GetTable() 函数返回。

// 声明
template<class K, class T, class KOFT, class HASH>
class HashBucket;template<class K, class T, class KOFT, class HASH>
class __HashIterator
{
public:typedef HashNode<T> node;typedef HashBucket<K, T, KOFT, HASH> HT;typedef __HashIterator<K, T, KOFT, HASH> self;__HashIterator(node* node, HT* ht):_node(node),_ht(ht){}bool operator!=(const self& iter){return _node != iter._node;}bool operator==(const self& iter){return _node == iter._node;}T& operator*(){return _node->_val;}T* operator->(){return &(_node->_val);}node* _node;HT* _ht;
};

        2、迭代器 ++

        ++iterator，前置++，返回自己

        思路：找到下一个不为空的节点，因为是++，所以不需要回到开头，后面都为空就返回。

self& operator++()
{// 如果 _node 为空，说明在 end() 位置，直接返回if (_node == nullptr)return *this;// 如果该节点的 next 不为空，返回它的下一个节点if (_node->_next){_node = _node->_next;return *this;}// 如果它是该链表的最后一个节点，找下一条链表的头//  获取当前节点的映射位置 keyiKOFT kot;HASH hashfunc;const K& key = kot(_node->_val);int keyi = hashfunc(key) % _ht->_table.size();// 向后查找哈希表中不为空的链表while (++keyi < _ht->_table.size()){// 找到，_node 为当前链表的头，也就是 _table[keyi]if (_ht->_table[keyi]){_node = _ht->_table[keyi];break;}}// 没找到，_node 返回空if (keyi == _ht->_table.size())_node = nullptr;return *this;
}

        完整哈希桶代码 

namespace bucket
{// 哈希表下挂的 单链表的节点template<class T>struct HashNode{HashNode(){}HashNode(const T& val):_val(val){}HashNode<T>* _next = nullptr;T _val = T();};// 声明template<class K, class T, class KOFT, class HASH>class HashBucket;template<class K, class T, class KOFT, class HASH>class __HashIterator{public:typedef HashNode<T> node;typedef HashBucket<K, T, KOFT, HASH> HT;typedef __HashIterator<K, T, KOFT, HASH> self;__HashIterator(node* node, HT* ht):_node(node),_ht(ht){}bool operator!=(const self& iter){return _node != iter._node;}bool operator==(const self& iter){return _node == iter._node;}T& operator*(){return _node->_val;}T* operator->(){return &(_node->_val);}self& operator++(){// 如果 _node 为空，说明在 end() 位置，直接返回if (_node == nullptr)return *this;// 如果该节点的 next 不为空，返回它的下一个节点if (_node->_next){_node = _node->_next;return *this;}// 如果它是该链表的最后一个节点，找下一条链表的头//  获取当前节点的映射位置 keyiKOFT kot;HASH hashfunc;const K& key = kot(_node->_val);int keyi = hashfunc(key) % _ht->_table.size();// 向后查找哈希表中不为空的链表while (++keyi < _ht->_table.size()){// 找到，_node 为当前链表的头，也就是 _table[keyi]if (_ht->_table[keyi]){_node = _ht->_table[keyi];break;}}// 没找到，_node 返回空if (keyi == _ht->_table.size())_node = nullptr;return *this;}node* _node;HT* _ht;};template<class K, class T, class KOFT, class HASH>class HashBucket{using node = HashNode<T>;static const double rate;public:using iterator = __HashIterator<K, T, KOFT, HASH>;friend iterator;HashBucket(int n = 0){_table.resize(n, nullptr);}// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器std::pair<iterator, bool> Insert(const T& val){// 拿到 key 值KOFT kot;const K& key = kot(val);// 通过Find判断是否存在对应的 keyiterator it = Find(key);if (it != end())return std::make_pair(it, false);int n = _table.size();if (_size >= n * rate){// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍int newcapacity = _size == 0 ? 4 : 2 * n;// 设置临时对象HashBucket temp(newcapacity);for (node* head : _table){// 因为容量发生变化，所以所有数据的映射位置发生变化// 将所有数据重新插入 tempwhile (head){temp.Insert(head->_val);head = head->_next;}}// 将 temp 中的资源换出来_table.swap(temp._table);_size = temp._size;n = newcapacity;}// 得到对应下标 keyiHASH hashfunc;int keyi = hashfunc(key) % n;// 创建新节点node* newnode = new node(val);// 头插newnode->_next = _table[keyi];_table[keyi] = newnode;// ++size++_size;return std::make_pair(iterator(newnode, this), true);}iterator begin(){// 找到第一个非空单链表的头for (auto head : _table){if (head)return iterator(head, this);}return iterator(nullptr, this);}iterator end(){// 为空代表走到了结尾return iterator(nullptr, this);}iterator Find(const K& key){if (_table.size() == 0)return end();// 得到对应下标 keyiHASH hashfunc;int keyi = hashfunc(key) % _table.size();KOFT kot;// 从单链表中查找值node* head = _table[keyi];while (head){// 找到返回if (kot(head->_val) == key){return iterator(head, this);}head = head->_next;}// 没找到返回 end()return end();}bool Erase(const K& key){// 先进行查找，没找到直接返回iterator iter = Find(key);if (iter == end())return false;// 通过 key 得到下标HASH hashfunc;int keyi = hashfunc(key) % _table.size();KOFT kot;node* prev = nullptr;node* cur = _table[keyi];while (cur){if (kot(cur->_val) == key){if (prev == nullptr)_table[keyi] = cur->_next;elseprev->_next = cur->_next;delete cur;break;}prev = cur;cur = cur->_next;}return true;}~HashBucket(){// 释放所有单链表的节点for (node* head : _table){while (head){node* next = head->_next;delete head;head = next;}}}private:std::vector<node*> _table;size_t _size;};template<class K, class T, class KOFT, class HASH>const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;
}

五、通过哈希桶封装 unordered_map 和 unordered_set

        1、封装 unordered_set

        

// 设置哈希函数
template<class K>
class HashFunc
{
public:int operator()(const K& val){return val;}
};
// 特化，string
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{int key = 0;for (char ch : str){key += ch;}return key;
}// 通过 值 找 key
// 对于 unordered_set 关键字和值都是 key
template<class K>
class KOfT
{
public:const K& operator()(const K& key){return key;}
};// 哈希函数给了默认的，也可以外面传
// unordered_set<int> 第一个模版参数是 key
template<class K, class HASH= HashFunc<K>>
class unordered_set
{
public:// typedefusing iterator = typename bucket::HashBucket<K, K, KOfT<K>, HASH>::iterator;// 插入、修改、查找等函数直接调用 哈希桶的接口即可std::pair<iterator, bool> Insert(const K& val){return _ht.Insert(val);}bool Erase(const K& key){return _ht.Erase(key);}iterator Find(const K& key){return _ht.Find(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:// 关键字为 K, 值为 kbucket::HashBucket<K, K, KOfT<K>, HASH> _ht;
};

        2、封装 unordered_map

        哈希桶的 T 为值，在 unordered_set 中为 K，在 unordered_map 中为 pair<K, T> 

        unordered_map 中的 T 为第二个类型，如 unordered_map<string, int> 中，代表的是 int

// 设置的默认哈希函数
template<class K>
class HashFunc
{
public:int operator()(const K& val){return val;}
};// 特化
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{int key = 0;for (char ch : str){key += ch;}return key;
}// 对于 unordered_map 关键字为 K, 值为 pair<K, T>
// 通过 KOfT 就可以实现 unordered_map 和 unordered_set 使用同一个类封装
template<class K, class T>
class KOfT
{
public:const K& operator()(const T& val){return val.first;}
};// unordered_map<string, int>
// K 为key，类型为string 
// T 类型为int
template<class K, class T, class HASH = HashFunc<K>>
class unordered_map
{
public:using iterator = typename bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH>::iterator;std::pair<iterator, bool> Insert(const std::pair<K, T>& val){return _ht.Insert(val);}bool Erase(const K& key){return _ht.Erase(key);}iterator Find(const K& key){return _ht.Find(key);}T& operator[](const K& key){// 运算符[] 就是如果存在，返回值引用；如果不存在，插入{key, 0}，并返回值引用// 因此，我们只要插入{key, 0} 即可std::pair<iterator, bool> ret = Insert(std::make_pair(key, 0));return ret.first->second;}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}
private:// 调用哈希桶时，key 为 K，值为pair<K, T>bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH> _ht;
};

        感谢观看♪(･ω･)ﾉ