C++哈希(一)

1.底层结构

顺序结构以及平衡中，元素关键码与其存储位置之间没有相对应的关系，因此在查找一个元素时，要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。

理想的搜索方法：可以不经过比较，依次直接从表中直接搜索到指定元素，如果构造一种数据结构，通过某种函数使元素的存储位置与它的关键码之间能够建立----映射关系，就可以很快的查找到指定的元素。

插入元素：根据插入元素的关键码，用函数计算出这个元素的存储位置并存放

查找元素：对元素的关键码进行计算，得到的函数值去取出此位置的存储元素，并把输入的元素与此元素进行比较，若关键码相等，则查找成功

该方式为哈希(散列)方法，哈希方法中的转换函数为哈希函数，构造出来的结构为哈希表

一般是用关键码膜上该结构的总容量，得到的值就为映射后的位置下标。

2.哈希冲突

对于俩个数据元素的关键码通过哈希函数后得到的值一样，不同关键字通过相同哈希函数计算出相同的哈希值地址，该现象称为哈希冲突或哈希碰撞。

3.哈希函数

引起哈希冲突的原因可能：哈希函数设计不够合理

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，则值域必须在[0 m-1]之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数形式相对简单

除留余数法

设散列表中允许存储的地址数位m个，取一个不大于m的数p，且p最接近或者等于m的质数作为除数，Hush(key)=key%p(p<m) ,将关键码转换为哈希地址

补充：

key%2^16表示的是取后十六位，然后key>>（32-n）（假设n=16）是把前16位移到后16位，最后把前16位和后16位异或的结果作为哈希值(key的前16位和后16位都到同一位置也就是后16位上了)，把key的每一位都参与到计算，这样得出的哈希值冲突会更少一些。

哈希冲突解决

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被填满，说明哈希表中心必然还有空位置，那么可以把key存放到冲突位置的下一个位置去。

找到空位置

1.线性探测

如下图要插入元素44，先通过哈希函数计算出哈希地址，44%10=4，应在4的位置，但是这个位置已经放了数据了，所以要从发生冲突的位置开始依次向后找，直到寻找到空位置为止

2.删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其它元素的搜索，比如删除4，那么查找44时根据计算的哈希地址就是4的位置，当44不在4位置在后面。所以通过枚举用标记的方式来删除元素。

enum State

{

        EMPTY,

        EXIST,

        DELETE

};

3.哈希表扩容

散列表的载荷因子定义：a=填入表中的个数/散列表的长度

对于开放定址法， 载荷因子应该限制在0.7~0.8以下，

线性探测优点：实现简单

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积，在查找时需要进行多次比较，导致搜索效率降低。

二次探测

线性探测的缺陷是产生冲突的数据堆积到一块，这与其找找的下一个位置有关，从发生冲突的位置向后找空位置可能会发生的问题，二次探测就是为了避免该现象的出现。

hash=hash0+i^2 or hash=hash0+i^2

 

代码实现

1.枚举定义状态

设置三个状态存在，空，删除

enum State
{EXIST,EMPTY,DELETE
};

2.定义存在哈希表里面的数据

pair模板，first表示键值，second表示值

template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};

3.哈希表的构造

内联函数里面提供的数字就是质数，有28个，这里lower_bound是选一个大于等于n的数字，这里的n也就是哈希表的存储个数，返回处使用了三目操作符，如果不是最后一个就是pos，如果是最后一个就要返回最后一个的前一个。

HashTable():_tables(__stl_next_prime(0)),_n(0)
{}
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

4.哈希表的插入

首先要判断插入的元素是否已经存在，接着是判断载荷因子是否超过0.7，这里把_n*10所以和7比较，如果大于7就要扩容了，哈希表扩容则原来的存储位置在新的里面是不一样的，因为之前的存储是旧的size，扩容后是新的size，哈希函数得出的值改变了，所以存储位置要重新计算，这里newht的空间还是去之前的28个里面选，这里+1是因为28个数字对应不同区间，所以只需要加一就会到下一个区间，还要判断旧表每一个位置的状态是否是存在的，说明之前是由元素在这个位置上，则把此处的元素再作为Insert的参数重新插入，最后交换地址，如果没超过0.7，则就正常插入，通过模来得到哈希值，然后还要线性检测是否此位置为空位置，while循环后就找到了空位置，则插入并改变状态为存在，并把已经存储的个数n++。

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

5.哈希表的查找

这里查找需要注意的是位置被占了，可能在哈希函数得出的值的后面或者前面，先得到要查找的键的哈希值，然后用循环来寻找，先看是否为空，空说明不存在，如果不为空还要判断键值是否一样，不一样就线性检测去遍历，找到就返回此处的地址。

HashData<K, V>* Find(const K& key)
{size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;
}

6.哈希表的删除

前面已经提到不能删除，只改变状态为删除状态就行，先用Find去找到指定位置，判断是否找到，找到就只改变状态变量。

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}
}

总代码

HashTable.h

#pragma once#include<vector>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 HashTable
{
public:HashTable():_tables(__stl_next_prime(0)),_n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n;
};

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<set>
#include<unordered_set>using namespace std;
#include"HashTable.h"
int main()
{//int a[] = { 19,30,52,63,11,22 };int a[] = { 19,30,5,36,13,20,21,12 };HashTable<int, int> ht;for (auto e : a){ht.Insert({ e, e });}//ht.Insert({ 15, 15 });ht.Erase(30);if (ht.Find(20)){cout << "找到了" << endl;}if (ht.Find(30)){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}return 0;
}