3. 哈希函数
哈希结构最关键的点就是哈希函数的设置
哈希函数的设置原则
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见的哈希函数设置方法
1、直接定址法常用
直接定址法是最常用的哈希函数，就是根据key直接取到存储位置，这里的位置可能是绝对位置也可能是相对位置。
哈希函数：Hash(Key)= A*Key + B
例如对于统计字符串中某种字符出现的次数，key的范围比较小，所以这里可以直接映射
Hash(key) = 1 * ‘a’ - ‘a’,这里就把a映射给0，所以显而易见z映射给了26。
但是如果数据比较分散的话，就不适合使用直接定址法了，比如对于集合{1, 2, 3, 4,99, 999},就会造成很大的空间浪费
2、除留余数法常用
为了应对直接定址法中的数据较为分散造成空间浪费的情况，有人设计出了除留余数法，用于集中数据。设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照哈希函数，将关键码转换成哈希地址。
**哈希函数：**Hash(key) = key % p (p<=m)
3、平方取中法了解
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址; 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
适合:不知道关键字的分布，而位数又不是很大的情况
4、折叠法了解
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5、随机数法了解
选择一个随机函数，取关键字的随机函数值为它的哈希地址，
**哈希函数：**Hash(key) = random(key),其中 random为随机数函数。
通常应用于关键字长度不等时采用此法
6、数学分析法了解
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。
例如:假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同 的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还 可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
4. 哈希冲突
上面那个例子，使用哈希的方式解决，看起来这样的算法非常棒，但是，如果数据集中还有一个44需要被插入，怎么办呢？44对应的hashkey也是4，和4产生了冲突。这就是哈希冲突，也叫哈希碰撞。
对于两个数据元素的关键字ki和kj
即:不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突/哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
哈希函数的设置决定了哈希冲突的产生可能性，哈希函数设置的越巧妙，越能够减小哈希冲突，但是哈希冲突是不可能被完全避免的
5. 哈希冲突的解决——开散列和闭散列
由于哈希冲突是不可避免的，所以当然要总结哈希冲突的解决方案，一般来说，解决方案分为两种——闭散列和开散列。
5.1 闭散列
闭散列也叫开放定址法：当发生哈希冲突的时候，如果哈希表还没有被装满，那么就有空余的位置存放，那么就可以把key存放到冲突位置的“下一个空位置”中。
那么，怎么寻找下一个空位置呢？
这里同样有很多种方式，最经典的就是线性探测
同样的，针对上述的哈希冲突的例子，现在需要插入元素44，通过哈希函数计算出哈希地址为4，因此44理论上插入的位置是4，但是由于该位置已经存放了值为4的元素，出现哈希冲突，所以依次向后探测，直到寻找到下一个空位置为止。
所以，针对线性探测的插入和删除算法如下：
1、插入
- 通过哈希函数获取到待插入元素在哈希表中的为止
- 如果该位置没有元素就直接插入新元素，如果该位置有元素就继续找下一个空位置，插入新元素
2、删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
所谓伪删除法就是用一个状态标志来代表此位置的状态
enum State {EMPTY, EXIST, DELETE}; // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
闭散列线性探测的哈希表代码实现插入删除查找
首先对于闭散列的哈希表，有以下的结构设计
1、由于伪删除法的存在，所以需要让表里面存放的数据中增加一个状态变量，这里使用一个枚举来给出状态情况
enum State { EMPTY, EXIST, DELETE };
2、表中的元素类型是一个KV结构的pair和一个状态变量state，所以哈希数据结构体设计如下
//HashData数据结构体 template<class K, class V> struct HashData { std::pair<K, V> _kv; State _state = EMPTY; }
3、由于KV结构中的key是一个泛型，当我们在进行哈希映射的时候，需要先让其映射成为整型，然后才能够映射到哈希地址，所以这里提供一个仿函数，用于将key映射到整型家族
//仿函数，映射到整型 template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } };
由于string类型在哈希映射中使用的频率非常高，所以有人对string的哈希算法做了一些研究与总结，这里附上链接，有兴趣的小伙伴可以去看一看 [字符串哈希算法](各种字符串Hash函数 - clq - 博客园 (cnblogs.com)),下面是hash映射的string类型的特化
//模版特化，针对string类型 template<> struct HashFunc<std::string> { size_t operator()(const std::string& key) { //采用了特殊方法把各元素的值放在一起 size_t hash = 0; for (auto ch : key) { hash *= 131; hash += ch; } return hash; } };
4、闭散列哈希表的结构
- 由于哈希表是KV模型，所以模板参数中肯定要有KV，除此之外，由于哈希映射的key要求是整型，所以一定需要提供一个仿函数来把key映射给整型
- 哈希表本身使用一个vector来管理，再加上一个整型的n用来存放哈希表中的有效数据个数
所以哈希表的结构就显而易见了
template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable()//由于哈希表需要根据容量来判断哈希地址，所以_tables必须要先初始化，所以这里显示写构造函数 :_n(0) { _tables.resize(10); } private: std::vector<Data> _tables;//表里面存储的是HashData，HashData内部是一个KV结构和一个状态 size_t _n = 0;//存储表中的有效数据个数 };
5、插入
//插入 bool Insert(const std::pair<K,V>& kv) { if(Find(kv.first))//如果已经存在，插入失败返回false return false; //扩容:判断是否扩容的方式是判断负载因子大小 负载因子 = 存放有效个数/哈希表容量（一般对于线性探测来说都是小于1的） if(_n * 10 / _tables.size() >= 7)//负载因子大于0.7时扩容 { //这里采用二倍的方式扩容，实际上不是这样扩容的，在上文中说明按照 HashTable<K, V, Hash> newTable; newTable._tables.resize(2 * _tables.size());//重新创建一个哈希表，大小是原表的二倍 for(auto& e : _tables)//遍历原表，如果有数据的话就在新表中插入 { if(e._state == EXIST) { newTable.Insert(e._kv); } } _tables.swap(newTable._tables);//交换二者的表（vector对象），这里调用的是vecotr库里的swap } //插入数据 size_t hashi = Hash()(kv.first) % _tables.size();//通过Hash的匿名对象映射出一个整形，通过这个整型除留余数从而定址 while(_tables[hashi]._state == EXIST)//映射的位置已经有值，出现哈希冲突，进行线性探测 { ++hashi; hashi %= _tables.size();//++之后可能大于size，所以需要 模等一下 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; }
删除
//删除 bool Erase(const K& key) { //由于直接删除该位置的值会引发后面的值的映射错误（会导致在找的时候提前找到空，所以不能直接删除，要使用伪删除法删除，即给一个DELETE状态） Data* ret = Find(key); if(ret)//找到值 { //将该位置的值状态置为DELETE，然后n-- ret->_state = DELETE; --_n; return true;//返回true表示删除成功 } else//哈希表中没有该值，返回false { return false; } }
查找
//查找 Data* Find(const K& key) { //按照哈希函数的方式计算，得到哈希地址 size_t hashi = Hash()(key) % _tables.size(); //从该地址向后寻找，由于线性探测的问题，所以该地址不一定是实际存放要找的位置的值，所以需要继续向后找，直到遇到EMPTY为止 while(_tables[hashi]._state != EMPTY) { if(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) return &_tables[hashi];//找到了返回地址 else//否则++hashi继续寻找 { ++hashi; hashi %= _tables.size(); } } return nullptr;//最终遇到EMPTY都没找到，返回空指针 }
