C++：哈希表的模拟实现

哈希

在顺序结构和平衡树中，元素的Key和存储位置之间没有必然的联系，在进行查找的时候，要不断的进行比较，时间复杂度是O(N)或O(logN)

而有没有这样一种方案，可以直接不经过比较，从表中得到所需要的元素呢？直接进行获取就可以，如果存在这样的结构，那么对它而言的查找效率是很高的

插入元素

根据上面的原理，在插入元素的时候，根据插入元素的Key，找到一个可以映射到一个表中的具体位置，并进行存放

搜索元素

在对元素的Key进行计算后，就可以直接找到它被映射到了表中的哪一个位置，从而可以直接找到它在表中的位置，如果找到了就返回true

上面的这个原理，就叫做哈希，也叫做散列，而在哈希中使用的这个转换函数就叫做哈希函数，也叫做散列函数，构造出来的结构就叫做哈希表，也叫做散列表

下面用一个例子来举例：

例如数据集合有{1, 7, 6, 4, 5, 9}

那么就可以把根据一个哈希转换函数：hash(key) = key % capacity，得到一个专属于它的下标，把这个值存到下标的位置：

通过这样的方法就可以对元素和下标建立一种关系，在寻找的时候可以直接寻找到，在进行数据的存储和查找的过程拥有相当高的效率

但依旧有问题，如果存储的元素正好已经被存储过了呢？

哈希冲突

所谓哈希冲突，简单来说就是不同的Key值经过计算，得到了一个相同的hash值，此时再向表中填写数据就会有问题，这个过程就叫哈希冲突，也叫做哈希碰撞，那为什么会引起哈希碰撞？如何解决？

哈希函数

通常来说，引起哈希碰撞的一个原因是哈希函数有问题

常见的哈希函数定义：

1. 直接定址法：取Key值的某个线性函数作为散列地址，例如Hash（Key）= A*Key + B
2. 除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法
4. 折叠法
5. 数学分析法

哈希函数设计的越好，出现哈希冲突的可能性就越低，但无法避免哈希冲突，也就是说，哈希冲突是一定会发生的

解决哈希冲突

解决的方法通常有两种，闭散列和开散列

闭散列：

当发生哈希冲突的时候，如果哈希表没有被装满，那么就说明哈希表中肯定还有空余位置，那么就放到冲突位置的下一个位置当中去

1. 线性探测

从发生哈希冲突的位置开始，依次向后进行探测，直到探测到了一个空位置为止

那么下面模拟实现一下线性探测的实现过程

	bool insert(const pair<K, V>& kv){// 考虑扩容问题if (_n * 10 / _t.size() == 7){size_t newsize = _t.size() * 2;vector<HashData<K, V>> newV;newV.resize(newsize);size_t _newn = 0;// 把原来的数据放到新表中 遍历一次旧表for (int i = 0; i < _t.size(); i++){// 如果旧表中这个位置的值存在 就准备放到新表中if (_t[i]._s == EXIST){size_t newhashi = _t[i]._kv.first % newsize;while (newV[newhashi]._s == EXIST){newhashi++;newhashi %= newsize;}newV[newhashi]._kv = _t[i]._kv;newV[newhashi]._s = EXIST;_newn++;}}_t.swap(newV);_n = newsize;}// 正常插入逻辑size_t hashi = kv.first % _t.size();while (_t[hashi]._s == EXIST){// 如果插入元素的位置有内容，就插入到下一个位置hashi++;hashi %= _t.size();}_t[hashi]._kv = kv;_t[hashi]._s = EXIST;_n++;return true;}

但是闭散列的缺陷是很明显的，比如当插入数据是12,22,32,42…这样的数据的时候，就会导致不停地触发哈希冲突，这样会产生堆积的效应，为了避免出现这样的问题，又提出了开散列的方案

开散列

开散列也叫做哈希桶，也叫做拉链法，原理就是把具有相同地址的Key值放到一起，每一个子集就叫做一个桶，每个桶的元素通过单链表来进行链接，每个链表的头结点在哈希表中

开散列中每个桶中放的都是哈希冲突的元素

namespace opened_hashing
{// 定义节点信息template<class K, class V>struct Node{Node(const pair<K, V>& kv):_next(nullptr), _kv(kv){}Node* _next;pair<K, V> _kv;};template<class K, class V>class HashTable{typedef Node<K, V> Node;public:// 构造函数HashTable():_n(0){_table.resize(10);}// 析构函数~HashTable(){//cout << endl << "*******************" << endl;//cout << "destructor" << endl;for (int i = 0; i < _table.size(); i++){//cout << "[" << i << "]->";Node* cur = _table[i];while (cur){Node* next = cur->_next;//cout << cur->_kv.first << " ";delete cur;cur = next;}//cout << endl;_table[i] = nullptr;}}// 插入元素bool insert(const pair<K, V>& kv){// 如果哈希表中有这个元素，就不插入了if (find(kv.first)){return false;}// 扩容问题if (_n == _table.size()){HashTable newtable;int newsize = _table.size() * 2;newtable._table.resize(newsize, nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 把哈希桶中的元素插入到新表中int newhashi = cur->_kv.first % newsize;// 头插cur->_next = newtable._table[newhashi];newtable._table[newhashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable._table);}// 先找到在哈希表中的位置size_t hashi = kv.first % _table.size();// 把节点插进去Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return true;}Node* find(const K& Key){// 先找到它所在的桶int hashi = Key % _table.size();// 在它所在桶里面找数据Node* cur = _table[hashi];while (cur){if (cur->_kv.first == Key){return cur;}cur = cur->_next;}return nullptr;}void print(){for (int i = 0; i < _table.size(); i++){cout << i << "->";Node* cur = _table[i];while (cur){cout << cur->_kv.first << " ";cur = cur->_next;}cout << endl;}cout << endl;}private:vector<Node*> _table;size_t _n;};
}

上面的实现看似没有问题，实际上依旧有问题，如果要传入的数据是string类，那么在比较的过程中会出现错误，因此要写一个仿函数用以处理这些情况

这里利用版本模板中的特化进行处理即可，处理细节比较巧妙

	template<class T>struct _Convert{T& operator()(const T& key){return key;}};template<>struct _Convert<string>{size_t& operator()(const string& key){size_t sum = 0;for (auto e : key){sum += e * 31;}return sum;}};

那么下一步就要进行对于哈希表的封装了，详情见模拟实现篇章