哈希函数 估计是一个程序员都知道这个概念，可以将一串数据变成一串特定的散列值，如果看过我之前的一致性哈希那篇文章应该会很清楚工作原理。这篇文章将讲解如何去设计一个工业级的哈希表，哈希表本身概念和工作原理没有什么难的，主要还是存储方式选择和负载因子带来的扩容和哈希冲突问题。

哈希表属于数据结构的范围了，日常开发过程中经常会使用到哈希表例如Java的HashMap、Go内置的map，这些都是哈希表，还有知名的缓存中间件例如Redis也是采用哈希的方式数据分区，也可以看成是一个超大的哈希表，大部分都在使用，而设计一个工业级哈希表要考虑的因素有很多：存储方式、负载因子、缩容和扩容问题等。

存储方式

哈希表是一种映射数据结构key-value，这种形式的存储，键可以是任何数据只要经过hash function就能得到一串哈希序列值。而值的存储方式有很2种：开放式存储，链表式存储，两种方式都用来存储值数据的，区别就是存储方式和取值方式不同罢了。

开放式寻址： 上来我们可以申请一块大的连续内存空间，数组就可以满足，然后把经过哈希计算的值放到对应的数组下标位置上，但是问题就是哈希函数可能不同的键算出来的值有可能相同发送哈希冲突了，这时怎么解决位置被占用的就是一个问题？

开放寻址工作原理如上图，如果发生了位置占用就往下一个下标位置找，看看是不是为空的，如果是空的那么就存储，循环这个过程。删除操作是不直接删除数据的，而是直接标记存储位置的下标，假性删除。但是这种也会有扩容带来的问题，删除的数据越多那么被标记的位置越多而且还是一样占用内存，所以不能再删除和插入一起操作，如果直接删除了位置上的内容，下次插入值时被存储到这个位置可能会发生数据错乱的现象。

链式存储： 链式存储是最简单的方式了，数据结构存储头节点是指向一个根数组的，然后如果发生了数据冲突那么的，数据会以链表的方式对接下去，这样的好处就是数据槽位固定的，但是数据元素可以在每个槽位上以链表的方式存储下去，动态分配存储，这个最常用的没有什么好说的原理图我也不画了。

负载因子

负载因子针对的是链式存储的方式，上面我讲过链式存储解决哈希冲突的问题是把数据分槽位，然后在对应的槽位上以链表的方式存储数据。但是这样的话如果数据越来越多，每个链表上的数据也很越来越多导致本来查询很快的时间复杂度变成了O(n)，怎么解决这样的问题，那就是要对数据较多的时候进行扩容操作，扩容操作就是针对分区槽位的扩容，把数据能确保分摊到所有的槽位上，那触发槽位扩容条件是什么？

需要扩容条件，那就要确定存储空间在什么条件下才能发生扩容操作，看了上面图，很容易看出来我们哈希函数是针对的槽位数，在哈希确定到槽位编号了之后，然后就是把数据放到链表上存储，和槽位上其他节点对接上。熟悉链表的朋友应该知道链表查找是要从头开始扫描查找数据的，所以时间复杂度为O(n)，所以链表上的数据不能太多，为了解决这个不能多的办法就是对槽的个数发生更新。

数据少的时候可能默认几个槽位就可以够用了，但是如果数据多了动态添加和删除数据多了，那么就要扩容了，扩容条件按照上面的推理完全可以推导出来那就是把目前哈希表所有存储的数据对槽位取平摊值，这个值就是每个槽位上的负载因子，公式我已经在图上画出来了，当负载因子越大的时候可能每个槽位上的链表数据就越多，查询性能也会有影响，越小就越快，所以在设计一个哈希表时负载因子很重要，使用的时候，可以在预估需要处理的数量积，先计算出负载因子然后初始化一个哈希表，这样就能满足需求。

扩容问题

解决了什么时候发生扩容的问题之后，另外一个问题就是怎么迁移数据到新的存储地址上，当数据太多时候，一般的扩容策略都在分配一个原始大小1.25的存储空间或者原始存储大小的两倍空间来存储老的数据和新的数据。

但是问题来了，如果老的哈希表里面有很多数据一次性迁移会带来很大问题，例如迁移的过程中哈希表还在并发操作的，并且有可能还有数据在写入，怎么保证数据一次性迁移呢？并且在扩容之后我们的哈希函数也要跟着更新的，原来的槽位数和新的扩容之后的槽位数是不一致的，所以老的哈希函数是不能正常访问到新的数据，这也是一个问题？

很多时候一次性迁移数据会发生性能损耗，哈希槽位上的链表数据越多那么迁移的数据就越多，这个就会带来性能问题。我看过一些比较好的迁移策略就是间接性迁移，也可以理解为被动迁移，那是怎么工作的呢？

针对上面的两个扩容的问题，哈希函数我们可以保留两个哈希函数，当有新的数据来的时候我们使用新的哈希函数计算存储到新的空间里面，如果有请求来查询我们可以先把老哈希函数计算一遍看看有没有数据，如果老哈希函数在老的地址里面没有找到新的数据，就用的新的哈希函数查找，每次有新的数据插入时就触发一次老的数据迁移，直到老的数据全部被迁移完成，销毁老的存储空间即可，在数据没有迁移完成之前可能内存消耗比较大，但是能使用空间换取时间和性能。

所以哈希扩容和迁移要注意的问题就是性能问题，渐进式迁移，每次一小部分发送迁移，不要一次性全部迁移，有新的数据请求如果在老的存储空间内没有命中，就直接存储到新的空间里面，这个设计就非常巧妙的解决问题。

注意项

开放寻址： 如果是通过数组分配存储空间可以享受CPU缓存机制因为数组空间是连续存储空间，可以把数据序列化存储，不涉及反序列化之后的指针地址不一致问题。开放寻址法的负载因子不能过大，如果过大那么每个数据空间存储的数据发生冲突概率加大影响性能，会发生命中位置被占用而重新寻址情况。

链式存储： 链式存储的好处就是每次存储的时候需要找到尾指针，在分配空间存储时需要额外的指针存储空间，存储空间不需要一次性分配连续的，不能发挥CPU缓存机制，其次负载因子可以大一点，解决数据冲突或者哈希冲突可以使用红黑树。例如Java默认负载因子是0.75，当存储数据每个槽位元素个数超过8个机会使用红黑树存储，而小于6的时候默认链表存储，这种多模式存储策略可以根据数据大小进行调整，还换取性能。

小结

设计一个工业级哈希表，并非难事，要分析哈希表解决了什么样的问题?然后针对每个问题一一击破，这就是系统设计的美学，我看过Go语言的map设计非常巧妙，有兴趣的朋友在看到我这篇博客时可以去读读Go的map设计相关的文章。

一些关于散列算法的应用有：MD5、SHA等...数据加密领域、区块链领域、服务负载均衡集群、路由分发、数据分片分布式存储、分布式系统里面的一致性哈希算法，这些全部是散列算法延伸出来的。