【C++学习篇】哈希表的实现

1.哈希的概念

1.1 直接定址法

1.1.1 例题字符串中的第一个唯一字符

1.2 哈希函数

1.2.1除法散列法/除留余数法

1.2.2 乘法散列法

1.3 哈希冲突

1.4 负载因子

1.5 处理哈希冲突

1.5.1 开放定址法

1.5.1.1 线性探测

1.5.1.2 二次探测

1.5.1.3 双重探测

1.哈希的概念

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

注意！！！哈希表不代表就是哈希，哈希表只是哈希衍生出来的一个一个东西。

那接下来，我开始介绍哈希思想

1.1 直接定址法

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。

1.1.1 例题字符串中的第一个唯一字符

一道题让你明白直接定址法-》力扣--字符串中的第一个唯一字符https://leetcode.cn/problems/first-unique-character-in-a-string/description/

但是，直接定址法，只适合元素范围比较集中的整形或者字符。像浮点数，字符串这些，就处理不了。所以这里我们需要引出一个东西，就是哈希函数，通过哈希函数，将关键字Key跟存储位置建⽴⼀个映射关系。

1.2 哈希函数

⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计。

1.2.1除法散列法/除留余数法

1. 除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

2. 当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是 2^X ，那么key % 2^X本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是 2^4 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。

3. 当使⽤除法散列法时，建议M取不太接近2的整数次冥的⼀个质数(素数)。
4. 需要说明的是，实践中也是⼋仙过海，各显神通，Java的HashMap采⽤除法散列法时就是2的整数次冥做哈希表的⼤⼩M，这样玩的话，就不⽤取模，⽽可以直接位运算，相对⽽⾔位运算⽐模更⾼效⼀些。但是他不是单纯的去取模，⽐如M是2^16次⽅，本质是取后16位，那么⽤key’ =
ey>>16，然后把key和key' 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建议M取不太接近2的整数次冥的⼀个质数的理论是⼤多数数据结构书籍中写的理论吗，但是实践中，灵活运⽤，抓住本质，⽽不能死读书。

1.2.2 乘法散列法

1.2.3 全域散列法

1.3 哈希冲突

直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间。

这⾥存在的⼀个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案