郑州外贸网站建设公司,浙江网站建设品牌设计,国外营销网站,网站建设和维护要学多久个人对哈希数据结构学习总结 -- 理论篇 引言哈希表设计思考哈希冲突Hash Functions冲突解决开放地址法(Open Addressing)分离链表法(Separate Chaining)Two-way Chaining Dynamic Hash Tableschained Hashingextendible hashinglinear hashing说明 spiral storage 使用场景小结… 个人对哈希数据结构学习总结 -- 理论篇 引言哈希表设计思考哈希冲突Hash Functions冲突解决开放地址法(Open Addressing)分离链表法(Separate Chaining)Two-way Chaining Dynamic Hash Tableschained Hashingextendible hashinglinear hashing说明 spiral storage 使用场景小结 引言
哈希表这个数据结构相信各位都不陌生无论是高级语言还是各大数据库底层实现都不离开它所以本文我想来聊聊我个人对哈希表的一些看法同时也是对哈希表这个知识点做一次系统性的梳理和总结。
本文主要会分为两大部分:
哈希表设计思考(偏理论)最佳实践(结合Java,Go,redis等热门技术来谈谈其中使用到的哈希设计原则) 哈希表设计思考
对于哈希表这个数据结构而言有这样四个维度的指标是我们需要考虑的:
所有数据集合 S哈希表存储的数据集合 U所有哈希桶的下标集合 R映射函数 h
S的大小一般远大于R但是哈希表存储的数据集合 U 与 R 大小相差不会太大如果存在 x!y h(x) h(y) ,则称x与y冲突。
如果h可以将U单射到R上那么我们称这种情况为完美哈希(perfect hashing) , 并且如果此时U的大小与R的大小相等则称此种情况为最小完美哈希(minimal perfect hashing)。
如果U的大小是固定的并且预先可知那么称这种情况为静态哈希表否则称之为动态哈希表。 哈希冲突
解决哈希冲突有两个着眼点
在冲突没发生前尽量避免冲突在冲突发生后解决冲突 Hash Functions
要避免冲突我们需要从哈希函数h这个维度下手
对于静态哈希表我们总是可以找到一个h来达成最小完美哈希对于动态哈希表由于集合U是不可控的所以我们的思路是尽可能减少冲突发生也就是选择一个尽可能少冲突的哈希函数h
关于如何设计一个完美的哈希函数并不是本文重点但是比较出名的哈希函数有以下这些大家可以自行查阅资料了解各自适用场景:
MurmurHash (2008)Google CityHash (2011)Google FarmHash (2014)CLHash (2016) 冲突解决
动态哈希表很难达成完美哈希的情况因此我们必须考虑如何解决发生的哈希冲突常见的冲突解决策略有:
开放地址法(Open Addressing)分离链表法(Separate Chaining)Two-way Chaining 开放地址法(Open Addressing)
开放地址法(Open Addressing)下面又细分了好几种策略:
线性探测法Linear Probing发生哈希冲突时将会在哈希表中线性地往后查找直到找到一个空槽来插入元素或执行查找操作。 这种方法可能导致聚集clustering现象即冲突的元素会聚集在一起影响性能。 二次探测法Quadratic Probing 发生冲突时会使用二次函数来计算下一个探测位置以尝试寻找下一个空槽或者目标元素。 这种方法相对于线性探测法来说能够更均匀地分散元素但仍然可能会出现二次探测路径相交的情况。 双重散列Double Hashing双重散列使用两个哈希函数当发生冲突时首先使用第一个哈希函数得到一个偏移量然后在第二个哈希函数的值处查找下一个位置。 这个方法可以有效地减少聚集问题但需要选择合适的哈希函数和冲突解决策略。
其中 Linear probing 由于对缓存友好性能最高比较常用。Linear probing 可能带来冲突聚集的情况为了避免这一现象有时也会使用 Quadratic probing 策略。使用 Quadratic probing 也会遇到一些恶意操作或者特定的输入数据从而导致性能下降或其他问题因此有时也会使用 Double hashing 配合 Universal hashing 获得更好的效果。 1.“线性探测对缓存友好” 指的是线性探测法在某些情况下能够更好地利用计算机的缓存机制从而在内存访问方面表现较好。这主要是因为线性探测法在哈希冲突时会沿着一个连续的内存地址序列进行探测这有助于提高数据的局部性从而更好地适应现代计算机的缓存体系结构。 2.通用哈希(Universal hashing)的主要思想是从一组可能的哈希函数中随机选择一个函数来哈希每个键这样可以使得不同的键在不同的哈希函数下分布减少冲突的概率。 Robin Hood Hashing:
Linear Probe Hashing 的变种为了防止 Linear Probe Hashing 出现连续区域导致频繁的 probe 操作。基本思路是 “劫富济贫”即每次比较的时候同时需要比较每个 key 距离其原本位置的距离越近越富余越远越贫穷如果遇到一个已经被占用的 slot如果它比自己富余则可以直接替代它的位置然后把它顺延到新的位置。 Robin Hood Hashing 也是为了解决线性探测法冲突聚集的问题 这样做的好处是什么呢最大的好处就是各个键值对离自己的理想位置的距离变得“均衡”了或许对查询的平均时间复杂度有一定的优化但是一定复杂化了插入操作的时间复杂度。
实际上经过实验发现这种方法的效率不如线性探测法不过这种方法的思想还是很有价值的。 分离链表法(Separate Chaining)
开放地址法(Open Addressing) 在装载因子较高时性能会急剧下降为了应对这一情况也常使用 Separate Chaining 策略。Separate Chaining 一般使用链表有时也会使用查找树结构。 Two-way Chaining
Two-way Chaining 就像是 Double hashing区别在于 Double hashing 使用一个哈希表而 Two-way Chaining 使用两个哈希表 T1 和 T2。在插入时T[h1(x)] 和 T[h2(x)] 中哪个装载的元素更少就插入到哪儿。查找时需要访问两个哈希表。
还有一种和Two-way Chanining思想类似的算法Cuckoo Hashing (布谷鸟哈希) 要理解该算法我们首先需要理解布谷鸟的行为这也是算法的核心:
布谷鸟妈妈从不筑巢它将自己的鸟蛋生在其他鸟类的巢穴里要别的鸟给它孵蛋新出生的布谷鸟会本能地将巢穴里的其他蛋踢开kick out 推出鸟巢以确保自己在鸟巢里可以独享宠爱
布谷鸟哈希有几种变种下面介绍一个哈希桶和两个哈希函数的版本 Insert 若值x已存在哈希表中则直接返回若insert后哈希表空间会不够则先进行扩容再rehash再继续3、4、5用哈希函数h1(x)计算出下标i1当bucket[i1]为空时说明鸟巢可用插入x若bucket[i1]非空用新值x将bucket[i1]上的老值x’踢开kick out对应小布谷鸟将老蛋踢出巢穴老蛋当然也不能坐以待毙继续kick out别的蛋老值x’的下一个位置用哈希函数h2(x)寻找重复2直到达到最大循环次数MaxLoop插入失败或者所有被踢开的值都找到新位置插入完成 lookup 查找逻辑非常简单去可能的两个巢穴里寻找即去下标h1(x)和h2(x)寻找若没有匹配上则不存在从这里可以发现查找是非常快的且时间复杂度稳定是O(1)
下图展示的是两个哈希函数两个哈希桶的版本:
为了防止我们不会陷入一个无限循环中一旦我们发现了一个死循环或者达到最大循环次数我们就需要对现有的hash table进行扩容
如果使用两个hash function那么我们大概只需要当hash table达到50%容量左右时才需要进行扩容重建如果使用三个hash function那么我们大概需要当hash table达到90%容量的左右时才需要进行扩容重建 Dynamic Hash Tables
随着哈希表的装载因子上升哈希冲突的概率会不断上升直到装载因子超过 1 时必然发生哈希冲突。对于动态哈希表由于U 的大小不能预先得知所以必然需要动态调整哈希表的大小。常见的策略:
当装载因子超过某一阈值后线性扩展哈希表的大小为原来的若干倍当装载因子低于某一阈值时线性收缩哈希表的大小为原来的若干分之一
使用两个阈值的原因是为了避免抖动。
由于R发生变化对应的哈希函数也必须发生变化同时分配一个块更大的内存将原哈希表中所有元素rehash到新的哈希表中这种策略称为Copy All策略该策略的坏处就是会产生较长时间的停顿因此下面来介绍几种改进的策略:
Chained Hashingextendible hashinglinear hashingspiral storage 哈希表不能够均匀地增长其根本原因在于 rehash只要能够不 rehash 但是调整 R就可以解决这一问题。 chained Hashing
Chained Hashing 是 Dynamic Hash Tables 的 HelloWorld 实现每个 key 对应一个链表每个节点是一个 bucket装满了就再往后挂一个 bucket。需要写操作时需要请求 latch:
在查找元素时根据元素的哈希键计算出对应的槽位并遍历该槽位的链表桶搜索具有相同哈希键的元素对于插入和删除操作也可以看作是查找操作的一般化。在插入元素时需要进行查找并确定插入位置在删除元素时也需要查找并删除相应元素
这么做的好处就是简单坏处就是最坏的情况下 Hash Table 可能降级成链表使得操作的时间复杂度降格为 O(n)。
当然如果桶中只有一个元素那么可以将其视为链表可以在链表长度到达指定阈值后变成二叉查找树提升查询效率。并且当负载因子达到指定阈值后可以对哈希表进行扩容此时如果不考虑性能可以采用copy all策略如果考虑性能可以考虑渐进式扩容策略。 extendible hashing
在Chained Hashing中一种可行的方法是在链表变得过长时将桶bucket进行分割而不是让链表无限增长。这种方法可以避免链表过长导致的性能问题并且需要进行分割时只需要对特定的桶进行重新分配。
可扩展哈希方式包含一个slot数组和一系列的buckets每个slot中保存对应bucket的指针。对于slot数组有一个全局bit位记录在这个哈希表中需要多少位才能找到对应bucket对于每一个bucket有一个本地bit位记录找到本地的bucket需要多少位。 extendible hash像一种结合hash与redix前缀树的技术的哈希方法 Extendible Hashing 的基本思路是一边扩容一边 rehash如下图所示 可拓展哈希允许插入哈希值相同的记录。所以当插入4条哈希值一样的记录一个桶就一定放不下假设桶的容纳上限是3条。这种情况被叫做overflow而解决方法是用指针指向overflow bucket也就是人为增加桶。这种方式看上去不美也暴露了可拓展哈希的局限性但一个方法在实际应用中确实无法确保永远的统一性总是会需要“补丁”。实际应用中可拓展哈希也不是最普遍的方法更多则是B-Tree。 linear hashing 本部分参考文章 线性哈希是可扩展哈希的改进可扩展哈希有一个小的性能瓶颈在bucket分裂且需要扩展slot array时需要对整个slot array加锁直到bucket分裂完成。为了解决这个问题提出了线性哈希方式。哈希表维护一个指针指向下一个准备分裂的bucket并且线性哈希采用多个哈希函数来寻找正确的bucket。
线性哈希的数学原理:
假定key 5 、 9 、13
此时所有 key % 4 1现在我们对8求余
5 % 8 59 % 8113 % 8 5由上面的规律可以得出
(任意key) % n M(任意key) %2n M或 (任意key) %2n M n
线性哈希的具体实现如所示:
我们假设初始化的哈希表如下: 为了方便叙述我们作出以下假定:
为了使哈希表能进行动态的分裂我们从桶0开始设定一个分裂点。一个桶的容量为listSize 3当桶的容量超出后就从分裂点开始进行分裂。hash函数为 h0 key %4 h1 key % 8h1会在分裂时使用。整个表初始化包含了4个桶桶号为0-3并已提前插入了部分的数据。
分裂过程如下:
现在插入key 27 进行哈希运算h0 27 % 4 3 将key 27插入桶3但发现桶3已经达到了桶的容量所以触发哈希分裂 由于现在分裂点处于0桶所以我们对0桶进行分割。这里需要注意虽然这里是3桶满了但我们并不会直接从3桶进行分割而是从分割点进行分割。这里为什么这么做在下面会进一步介绍。 对分割点所指向的桶(桶0)所包含的key采用新的hash函数(h1)进行分割。
对所有key进行新哈希函数运算后将产生如下的哈希表 虽然进行了分裂但桶3并不是分裂点所以桶3会将多出的key放于溢出桶.,一直等到桶3进行分裂。进行分裂后将分裂点向后移动一位。 一次完整的分裂结束
key的读取:
采用h0对key进行计算。如果算出的桶号小于了分裂点表示桶已经进行的分裂我们采用h1进行hash运算算出key所对应的真正的桶号。再从真正的桶里取出value如果算出的桶号大于了分裂点那么表示此桶还没进行分裂直接从当前桶进行读取value。 说明 如果下一次key插入0、1、2、4桶是不会触发分裂没有超出桶的容量, 如果是插入桶3用户在实现时可以自己设定可以一旦插入就触发也可以等溢出桶达到listSize再触发新的分裂。 现在0桶被分裂了新数据的插入怎么才能保证没分裂的桶能正常工作已经分裂的桶能将哪部分插入到新分裂的桶呢? 只要分裂点小于桶的总数我们依然采用h0函数进行哈希计算。 如果哈希结果小于分裂号那么表示这个key所插入的桶已经进行了分割那么我就采用h1再次进行哈希而h1的哈希结果就这个key所该插入的桶号。 如果哈希结果大于分裂号那么表示这个key所插入的桶还没有进行分裂。直接插入。 这也是为什么虽然是桶3的容量不足但分裂的桶是分裂点所指向的桶。如果直接在桶3进行分裂那么当新的key插入的时候就不能正常的判断哪些桶已经进行了分裂。 如果使用分割点就具备了无限扩展的能力。当分割点移动到最后一个桶(桶3)。再出现分裂。那么分割点就会回到桶0到这个时候h0作废h1替代h0, h2(key % 12)替代h1。那么又可以开始动态分割。那个整个初始化状态就发生了变化。就好像没有发生过分裂。那么上面的规则就可以循环使用。 线性哈希的论文中是按上面的规则来进行分裂的。其实我们可以安装自己的实际情况来进行改动。
假如我们现在希望去掉分割点一旦哪个桶满了马上对这个桶进行分割。
可以考虑了以下方案 为所有桶增加一个标志位。初始化的时候对所有桶的标志位清空。 一旦某个桶满了直接对这个桶进行分割然后将设置标志位。当新的数据插入的时候经过哈希计算h0发现这个桶已经分裂了那么就采用新的哈希函数(h1)来计算分裂之后的桶号。在读取数据的时候处理类似。
采用此种方案实现的LinerHash简易代码如下所示:
/*** lineHash简单实现模型*/
public class LineHash {/*** 单桶最多容纳元素个数*/public final int bucketMaxSize;/*** 分裂点索引*/public int overPoint 0;/*** 每一轮的哈希桶数组初始大小*/private int initSize;/*** 哈希桶数组*/public Bucket[] buckets;public LineHash(int bucketMaxSize) {this.bucketMaxSize bucketMaxSize;// 初始桶数组大小为4buckets new Bucket[4];initSize 4;}public String get(int key) {int index calculateIndex(key);return buckets[index].get(key);}public void put(int key, String val) {int index calculateIndex(key);Bucket bucket buckets[index];// 判断当前桶是否满了if (bucket.size() bucketMaxSize) {bucket.put(key, val);} else {//满了就进行分裂bucket.put(key, val);splitHash();}}private int calculateIndex(int key) {//根据分裂轮数调用不同的哈希函数int index hashFun(key, 1);//当前桶产生了分裂if (index overPoint) {//采用新的哈希函数进行计算index hashFun(key, 2);}lazyInitIfNeed(index);return index;}private void lazyInitIfNeed(int index) {if (buckets[index] null) {buckets[index] new Bucket(bucketMaxSize);}}public int hashFun(int key, int round) {return key % (initSize * round);}public void splitHash() {// 待分裂的旧桶Bucket oldBucket buckets[overPoint];//分裂产生的新桶Bucket newBucket new Bucket(bucketMaxSize);// 对旧桶中的元素进行rehashSetInteger keySet oldBucket.keySet();ListInteger removeKeyListnew ArrayList(oldBucket.size()/2);keySet.forEach(key - {int index hashFun(key, 2);// 说明当前key需要被rehash到新桶中if (index buckets.length) {newBucket.put(key, oldBucket.get(key));removeKeyList.add(key);}});removeKeyList.forEach(oldBucket::remove);// 将新桶添加进哈希桶数组中addBucket(newBucket);// 分裂点前移overPoint;// 分裂点移动了一轮就更换新的哈希函数if (overPoint initSize) {initSize initSize * 2;overPoint 0;}}private void addBucket(Bucket newBucket) {Bucket[] temp new Bucket[buckets.length 1];System.arraycopy(buckets, 0, temp, 0, buckets.length);temp[buckets.length] newBucket;buckets temp;}/*** 桶*/private static class Bucket {private final MapInteger, String map;private Bucket(int bucketMaxSize) {this.map new HashMap(bucketMaxSize);}public void put(Integer key, String val) {map.put(key, val);}public String get(Integer key) {return map.get(key);}public int size() {return map.size();}public SetInteger keySet() {return map.keySet();}public void remove(Integer key) {map.remove(key);}}
}这段代码逻辑不完全正确本人目前能力所限对liner hash理解还不够透彻如果有大佬有补充可以在评论区留言。 关于Linear Hashing的更多内容大家可以阅读论文学习:
Linear Hashing Paper spiral storage
Spiral Storage 总是将负载更多的放在哈希表靠前的位置上而非均匀地将负载分配到整个哈希表中。这样尽管是像 Linear Hashing 一样总是从哈希表的头部开始进行 bucket 的分裂也不会有不及时处理非常满的 bucket 的问题。
Spiral Storage 的思路是这样的。哈希表的负载从前向后逐渐降低扩展大小时需要将表头的 bucket 中的元素分配到多个新 bucket 中并添加到哈希表的末尾并且依然保持负载从前向后逐渐下降的性质。假设每去掉表头的一个 bucket 就添加 d 个新 bucket称 d 为哈希表的增长因子。考虑到哈希表是非线性增加大小的应该采用一个非线性增长的哈希函数族将 U 映射到 R。易发现指数函数满足这样的性质。
spiral storage本节讲解的比较模糊具体可以参考Google的开源实现:
https://github.com/sparsehash/sparsehash 使用场景
单机场景:
对于静态哈希表而言如果预先知道哈希表需要存储的数据集合U那么我们要力求实现Minimal Perfect Hashing。对于动态哈希表而言如果可以预先知道部分数据的分布那么可以针对性的设计哈希函数尽可能达到Perfect Hashing。如果没有关于数据的额外信息我们可以在保证负载因子较低的情况下尽量选择线性探测法(Linear Probing)来较好的利用CPU缓存。在不能保证负载因子的情况下如果需要考虑最坏情况的话应该考虑使用分离链表法(Separate Chaining)配合平衡树搜索策略。如果希望获得比较高的装载因子同时又不希望性能下降太严重并且可以接受一定的长尾的话可以考虑布谷鸟哈希策略(Cuckoo Hashing)。哈希表的动态大小调整一般选择Copy All策略一方面实现简单另一方面对哈希函数限制最小。
分布式场景:
分布式场景下更多的问题在于如何快速将请求匹配到实际存储数据的节点该场景下基本被一致性哈希所统治。对于局域网(LAN)环境下的快速查找场景如果期望常数级别的时间复杂度最简单的方式就是缓存所有节点的映射信息。
因为哈希表一般需要保持比较低的负载因子所以在哈希表较大的时元素会非常稀疏如果需要支持SCAN操作的话需要考虑在非空bucket之间建立联系。 小结
本篇作为笔者个人对哈希数据结构的学习总结的理论篇主要和大家探讨了一下哈希数据结构的相关理论性基础知识由于笔者个人能力有限所以其中很多知识点笔者个人也仍然处在探索之路上无法使用简单直白的语言表达出来望各位见谅
本文讲述内容其中可能含有大量理解偏差如有大佬发现可以在评论区指出或者给出个人观点
下一篇中我将结合Java,Go,redis等热门技术来谈谈其中使用到的哈希设计原则。
