哈希的基本概念（开散列和闭散列）（附代码）

哈希

• 哈希概念
• • 哈希冲突
  • 哈希函数
  • • 常见的哈希函数
  • 哈希冲突的解决
  • • 闭散列
    • 开散列

哈希概念

传统的查找函数，搜索的效率取决于比较的次数。而hash算法：在理想情况下，可以不经过任何比较，一次就能得到要搜索的结果。
存储结构：通过某种（hashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，所以在查找时，通过该映射函数可以很快找到该元素。

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

该方法就是哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表。
大致结构如下图所示：

哈希冲突

不同的关键词通过相同的哈希函数映射到同一个地址，该现象叫做哈希冲突/哈希碰撞。
如：元素11再插入上图中，就会和元素1产生碰撞。
1和11就是同义词

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设置不合理。
哈希函数设计原则：

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

常见的哈希函数

1. 直接定址法（常用）
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key+B
   优点：简单、均匀
   缺点：需要事先知道关键字的分布情况
   使用场景：适合查找比较小的连续的情况

2. 除留余数法（常用）
   设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p (p<=m)，将关键码转成哈希地址

3. 平方取中法
   假设关键字是1234，对它的平方就是1522756,抽取中间3位227作为哈希地址；
   再比如关键字4321，平方是18671041，抽取中间的三位671或者710作为哈希地址。
   平方取中法适合：不知道关键字分布，而位数又不是很大的情况。

4. 折叠法
   折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

5. 随机数法
   选择一个随机函数，去关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机数函数。
   通常应用于关键字不等时采用此法。

6. 数学分析法
   
   

哈希冲突的解决

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

闭散列

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

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
2. 闭散列处理冲突时，不能随便删除物理哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。

闭散列线性探测实现：

enum class State{EMPTY,EXIST,DELETE};template<class K, class V>struct Elem //数据类型{pair<K, V> _data;State _state=State::EMPTY;};template<class K, class V>class Hashtables{public:bool insert(const pair<K, V>& data){if (Find(data.first))return false;//如果不满足负载，就扩容CheckSize();//求地址size_t hashi = data.first % _tables.size(); //不能是capacity，vector天然不支持//插入 while(_tables[hashi]._state == State::EXIST){hashi++; //线性探测法hashi %= _tables.size();}_tables[hashi]._data = data;_tables[hashi]._state = State::EXIST;n++;return true;}不方便删除接口//pair* Find(const K& key)//{//if (_tables.size() == 0)//{//return nullptr;//}//size_t hashi = key % _tables.size();//size_t i = 1;//while (_tables[hashi]._state==State::EXIST||_tables[hashi]._state==State::DELETE)//存在或删除，不影响探测//{//if (_tables[hashi]._state == State::EXIST//&& _tables[hashi]._data.first != key)//{//hashi = hashi + i;//hashi %= _tables.size();//i++;//}//else//{//return &_tables[hashi]._data;//}//if (hashi == key % _tables.size())//转一圈也没找到//{//return nullptr;//}//}////return nullptr;//}Elem<K,V>* Find(const K& key){if (_tables.size() == 0){return nullptr;}size_t hashi = key % _tables.size();size_t i = 1;//逻辑有问题while (_tables[hashi]._state == State::EXIST || _tables[hashi]._state == State::DELETE)//存在或删除，不影响探测{if (_tables[hashi]._state == State::EXIST && _tables[hashi]._data.first == key){return &_tables[hashi];}else//接着查找{hashi = hashi + i;hashi %= _tables.size();}if (hashi == key % _tables.size())//转一圈也没找到，说明全是存在+删除{return nullptr;}}return nullptr;}bool erase(const K& key){auto it = Find(key);if (!it){return false;}//错了！！！！！！！！！！！！！！！//it._state == State::DELETE;it->_state = State::DELETE;n--; //别忘记计数减一return true;}private:void CheckSize(){ if (_tables.size()==0 ||(double)n / (double)_tables.size() > 0.7){int newcapacity = (_tables.size() == 0 " />10 : _tables.size() * 2);vector<Elem<K, V>> newTables(newcapacity);//再次重新插入for (auto& e : _tables){if (e._state == State::EXIST){size_t hashi = e._data.first % newTables.size();while (newTables[hashi]._state == State::EXIST){hashi++;hashi %= newTables.size();}newTables[hashi]._data = e._data;newTables[hashi]._state = State::EXIST;}}swap(_tables, newTables);}}private:vector<Elem<K, V>> _tables; //哈希表size_t n=0;//表示插入数据的大小};

线性探测优点：实现简单
缺点：一旦发生冲突，所有冲突连在一起，容易产生“堆积”数据。

也可以用二次探测解决即：线性探测由hashi = hashi+i -> hashi + i^2。

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

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

开散列

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

namespace HashBucket{template<class K, class V>struct Elem{Elem(const pair<K, V>& data):_data(data),_next(nullptr){}pair<K, V> _data;Elem<K, V> *_next;};template<class K, class V>class HashTables{typedef Elem<K, V> Node;typedef pair<K, V> Data;//typedef HashTables HashTables;public:bool insert(const Data& data){//负载因子过大就扩容CheckCapacity();//散列地址size_t hashi = data.first % _tables.size();//直接插入头插Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;n++;return true;}Node* find(const K& key){size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_data.first == key){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){size_t hashi = key % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_data.first == key){if (!prev) //prev为空，说明是在表上{_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private://扩容有问题，不应该插入一个就扩容，插入一个就扩容！！！！！！！！！！！！void CheckCapacity(){//表为空或者负载因子大于0.7了就扩容//if (!_tables.size() || ((n * 10) / (_tables.size() * 10) > 7))/*if (!_tables.size() || ((n * 10) / _tables.size() > 7))*/if(n==_tables.size()){size_t newCapacity = (_tables.size() == 0 ? 10 : _tables.size() * 2);HashTables* newHashTable = new HashTables;newHashTable->_tables.resize(newCapacity);//将旧表的数据重新映射到新表//遍历旧表for (auto& e : _tables){if (e)//不空，就有数据{Node* cur = e;Node* next; //下一个指针while (cur){size_t hashi = cur->_data.first % newCapacity;next = cur->_next;//暂存下一个cur->_next = newHashTable->_tables[hashi];newHashTable->_tables[hashi] = cur; //头插//newHashTable->n++;cur = next;}}}//swap(*newHashTable, *this);_tables.swap(newHashTable->_tables);}}private:vector<Node*> _tables;size_t n = 0;};}

哈希桶的增容问题：