# 散列表 ## 定义 > 根据键（Key）直接访问在内存存储位置的数据结构 ## 实现原理 > 通过散列函数（也叫哈希函数）将元素的键映射为数组下标（转化后的值叫做散列值或哈希值），然后在对应下标位置存储记录值。当我们按照键值查询元素时，就是用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据： >  > 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。而 PHP 的关联数组干脆就是基于散列表实现。 > 散列技术既是一种存储方法，也是一种查找方法。与之前的查找方法不同的是散列技术的记录之间不存在逻辑关系，因此主要是面向查找的数据结构。最适合求解的问题是查找给定值相等的记录。 ## 散列函数 > 散列函数用于将键值经过处理后转化为散列值。具有以下特性： > * 散列函数计算得到的散列值是非负整数 > * 如果key1 == key2，则hash(key1)==hash(key2) > * 如果key1!=key2,则hash(key1)!=hash(key2) ## 散列冲突 > 简单来说，指的是key1 != key2的情况下，通过散列函数处理，hash(key1)==hash(key2),这个时候，我们说发生了散列冲突。设计再好的散列函数也无法避免散列冲突，原因是散列值是非负整数，总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。 ## 散列冲突解决 > 昨天我们分享了散列表的实现，对 PHPer 来说，应该对散列表很熟悉，因为我们每天用的数组就是基于散列表实现的。比如 $arr\['test'\] = 123 这段代码，PHP底层会将键值 test 通过散列函数转化为散列码，然后将 123 映射到这个散列码上。在不考虑哈希冲突的情况下，散列表查找、删除、插入的时间复杂度都是 O(1)，非常高效。 > > > > 要减少哈希冲突，提高散列表操作效率，设计一个优秀的散列函数至关重要，我们平时经常使用的 md5 函数就是一个散列函数，但是其实还有其他很多自定义的设计实现，要根据不同场景，设计不同的散列函数来减少散列冲突，而且散列函数本身也要很简单，否则执行散列函数本身会成为散列表的瓶颈。我们日常很少会自己去设计散列函数，但是做一些简单的了解还是有必要的。 > 通常有以下几种散列函数构造方法： > 1. 直接定址法：即 f(key) = a\*key + b，f表示散列函数，a、b是常量，key是键值 > 2. 数字分析法：即对数字做左移、右移、反转等操作获取散列值 > 3. 除数留余法：即 f(key) = key % p，p 表示容器数量，这种方式通常用在将数据存放到指定容器中，如何决定哪个数据放到哪个容器，比如分表后插入数据如何处理（此时p表示拆分后数据表的数量），分布式Redis如何存放数据（此时p表示几台Redis服务器） > 4. 随机数法：即 f(key) = random(key)，比如负载均衡的random机制 >以上只是一些比较场景的散列函数设计思路，还有很多其他的设计方法，这里就不一一列举了。 > 我们在上篇分享中提到，设计再好的散列函数也不能完全避免散列冲突，我们只能优化自己的实现让散列冲突尽可能少出现罢了，如果出现了散列冲突，该如何处理呢？下面给出一些思路： > 1. 开放寻址法：该方法又可以细分为三种 —— 线性寻址、二次探测、随机探测。线性寻址表示出现散列冲突之后，就去寻找下一个空的散列地址；线性寻址步长是1，二次探测步长是线性寻址步长的2次方，其它逻辑一样；同理，随机探测每次步长随机。不管哪种探测方法，散列表中空闲位置不多的时候，散列冲突的概率就会提高，为了保证操作效率，我们会尽可能保证散列表中有一定比例的空闲槽位，我们用装载因子来表示空位的多少，装载因子=填入元素/散列表长度，装载因子越大，表明空闲位置越少，冲突越多，散列表性能降低。 > 2. 再散列函数法：发生散列冲突后，换一个散列函数计算散列值 > 3. 链地址法：发生散列冲突后，将对应数据链接到该散列值映射的上一个值之后，即将散列值相同的元素放到相同槽位对应的链表中。链地址法即使在散列冲突很多的情况下，也可以保证将所有数据存储到散列表中，但是也引入了遍历单链表带来性能损耗。 > 介绍完以上内容之后，想必你对如何打造工业级散列表已经心中有数。主要考虑因素包含以下几个方面： > 散列函数设置合理，不能太过复杂，成为性能瓶颈； > > 设置装载因子阈值，支持动态扩容，装载因子阈值设置要充分权衡时间、空间复杂度； > > 如果一次性扩容耗时长，可采取分批扩容的策略，达到阈值后只申请空间，不搬移数据，以后每插入一条数据，搬移一个旧数据，最后逐步完成搬移，期间为了兼容新老散列表查询，可以先查新表，再查老表； > > 散列冲突解决办法：开发寻址法在数据量较小、装载因子小的时候（小于1）选用；链表法可以容忍装载因子大于1，适合存储大对象、大数据量的散列表，且更加灵活，支持更多优化策略