1哈希表1.1哈希概念哈希hash又叫“散列”是一种组织数据的方法。本质就是通过哈希函数把关键字key和存储位置建立一个映射关系查找时通过这个哈希函数计算出key的存储位置进行快速查找。可以举一个简单的例子对‘a’~‘z’进行哈希映射建立一个哈希表那么此时可以通过利用ASCII码表来建立映射比如对于‘a’ASCII码值为97那么映射可以是97-‘a’那么对应便是下标为0的位置。依次类推得到往后的所有映射。那么所谓的哈希函数便是hash(x)x-97 对应的key便是‘a’--‘z’ 。当然由此可以看出上述的哈希表其实也是一个“数组”。那么此时可以看出所谓的key值若不是整数则可以通过一定手段将其转化为整数再映射那么这也是对于key的要求----必须可以转化为整型。那么上述所使用的可以总结成“直接定址法”。1.2直接定址法直接定址法就如同上述所示的每个映射都是通过关键字直接计算出一个绝对或相对的位置。当关键字的范围比较集中时直接定址法是非常简单高效的。但不可避免的就是会产生哈希冲突。1.3哈希冲突哈希冲突就是关于两个不同的key也可能映射到同一个位置的现象。实际场景是当数据范围在[0,9999]的N个值映射到M个空间的数组中去MN)那么需要借助哈希函数完成映射可以假定哈希函数h(key)key%M那么在一定范围内所得的必然有重复的结果此时现象就称为哈希冲突。哈希冲突不可避免那么关于哈希冲突已经产出了一系列解决方案。1.4负载因子负载因子表示着一个哈希表的空间利用率和哈希冲突的概率。假设哈希表已经存储了N个值哈希表的大小为M负载因子N/M。负载因子越大表示哈希冲突概率越大空间利用率越高那么根据此也可以得出一个解决哈希冲突的方向当负载因子到达一定大小时及时扩容以降低哈希冲突概率。我感觉这里的思想和插入vector的空间占比达到一定数量时就扩容有异曲同工之妙1.5哈希函数一个理想的哈希函数应该是让N个关键字被等概率的均匀的分配到哈希表的M个空间但实际上哈希冲突难以避免只能尽量选择合适的方法映射设计出较为好的哈希函数。1.5.1除法散列法/除留余数法哈希函数h(key)key%M假设哈希表的空间为M个通过key除以M的余数作为映射位置的下标。对于该方法需要注意M的取值建议取不太接近2的整数次幂的一个质数素数当M取2的幂或10的幂时总是更容易出现哈希冲突如2^x那么此时的h(key)就相当于保留key的后x位那么对于后x位相同的值计算的结果也就相同了。但实践中总是有各种各样的应用和场景也不能把话说的太死~1.5.2乘法散列法哈希函数h(key)floor(M*((A*key)%1.0))其中floor表示对表达式进行向下取整A(0,1)关于A的值普遍公认黄金分割点比较好A((√5 - 1)/2)0.618033……乘法散列法的思路是用关键字key乘上常数A并抽出其小数部分再用M乘以小数部分向下取整。该方法对于M没有要求。1.5.3全域散列法哈希函数h(key)((a*keyb)%P)%MP是一个足够大的质数a是[1,p-1]之间随机一个整数b是[0,p-1]之间随机一个整数这些函数构成了一个p*(p-1)组全域散列函数组。每次初始化哈希表时都会随机分配函数组中的一个散列函数使用后续就会固定该函数不会再改变。这种情况就大大增加了散列函数的随机性也拥有了更高的安全性和加密性。以上就是常见的哈希函数以及方法实践中一般选择除法散列法作为哈希函数但无论什么方法都避免不了哈希冲突 所以针对哈希冲突时需要有专门的解决方法。1.6处理哈希冲突1.6.1开放定址法在开放定址法中当出现哈希冲突则会按照某种规则找到一个没有存储数据的位置再存储那么对于负载因子必然的较小的。这里对应的规则有三种线性探测二次探测双重探测。线性探测从发生冲突的位置开始依次线性向后探测直到找到没有存储数据的位置。若h(key)key%M若hash0冲突则线性探测公式为hc(key,i)hashi(hash0i)%M, i{1,2,3…M-1}负载因子一定小于1则最多探测M-1次一定能找到。线性探测有明显弊端容易占用还未计算映射的数据的位置而导致后续数据都出现抢占的问题效率在一定程度上降低所以也就有了二次探测。二次探测从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个空位置。若向右为表末尾则跳到表头向左同理。若h(key)key%M若hash0冲突则二次探测公式为hc(key,i)hashi(hash0i^2)%M, i{1,2,3…M/2}当hashi0时需要hashiM。双重散列该方法运用两个哈希函数当第一个哈希函数计算发生冲突时使用第二个哈希函数计算出一个与key相关的偏移量不断往后探测直到找到空位置。但并不是特别常用。若h1(key)key%M若hash0冲突则双重探测公式为hc(key,i)hashi(hash0 i*h2(key))%M, i{1,2,3…M/2}要求h2(key)M且h2(key)与M互为质数有两种简单的取值方法a.当M为2的整数幂时h2(key)从[0,M-1]任选一个奇数b.当M为质数时h2(key)key%(M-1)11.6.2链地址法开放定址法中所有元素都放在哈希表里链地址法中所有数据不再直接存放在哈希表中而是通过链表形式挂起哈希表中只存储一个指针这样的方法比开放地址法少一步计算更加方便高效。连地址法也叫哈希桶。2unordered_set和unordered_map简介unordered_set和unordered_map都是STL已经封装好的容器底层就是哈希表哈希桶。那么两者和mapset的区别在于“unordered”unordered_map和unordered_set是无序存储通过哈希函数计算“key”的存储位置平均查找为O(1)非常高效而map和set底层是红黑树的有序存储。2.1unordered_set对于unordered_set的使用基本和set没有太大差别不过多赘述。只叙述差异1对key的要求不同。set对于key要求支持小于比较。unordered_set要求key支持转成整型且支持等于比较。对于其要求不同可以理解为应用场景的不同在set中的红黑树要求有序插入所以只要求可以比较。在unordered_set中的哈希表是通过哈希函数来计算key的位置且需要解决哈希冲突等问题所以需要转成整型计算且要求支持等于。2迭代器差异。set的迭代器是双向迭代器unordered_set是单向迭代器。set底层是红黑树也就是二叉搜索树所以底层迭代器是走中序便有序迭代且去重。unordered_set底层是哈希表那么迭代器遍历是无序且同样去重。3性能差异。绝大多数的情况unordered_set的效率快于set。红黑树的增删查改效率为O(logN)而哈希表的效率是O(1)。2.2unordered_map对于unordered_map和map的差异与上述的set和unordered_set差异没有太大区别不过多赘述。1对key的要求不同。map对于key要求支持小于比较。unordered_map要求key支持转成整型且支持等于比较。2迭代器差异。map的迭代器是双向迭代器unordered_map是单向迭代器。3性能差异。绝大多数的情况unordered_map的效率快于map。红黑树的增删查改效率为O(logN)而哈希表的效率是O(1)。
