在日常工作开发中，使用Redis缓存MYSQL热数据提升数据查询速度，这是典型的以空间换时间思想。

在内存有限的单片机运行程序，通常会使用压缩数据的方式节省空间占用，这就是以时间换空间的思想。

如今在面向更多用户数据，使用更多的空间建立数据索引，加快数据访问速度，则是我们常用的管理大数据的手段之一。

索引有很多类型，哈希表、红黑树、B树都可以，但是如果我们要在上亿的数据中提供纳秒级的查询速度，那么作为最快的索引，哈希表将是第一选择。



时间复杂度

时间复杂度可以很好的反映算法运行时间随着规模的增长的变化趋势。





用O表示描述时间复杂度，哈希表就是常量级的O(1)，所以Memcached、Redis均是使用哈希表管理缓存数据。



哈希表如何做到O(1)时间复杂度呢？

我们都知道数组的查询速度非常快，由于数组在内存中是连续的，符合CPU时间、空间局部性原理，因此访问速度会非常快。而哈希表又是基于数组实现的，哈希函数（Redis使用MurmurHash2算法,PHP7使用time33算法）将查询KEY转换为哈希值，接着通过相应计算得到数组下标，再通过数组的索引获取数据。





这样，哈希函数的执行时间是常量，数组的随机访问也是常量，时间复杂度就是 O(1)。



哈希表的冲突

哈希表因为其本身的结构使得查找对应的值变得方便快捷，但也带来了一些问题，以上面的图为例，查询KEY转换为哈希值，但是那如果字典中有两个KEY计算得到的哈希值是相同呢？例如，假设我们要查找 “tal” 与“qingke”这两个词得到的哈希值一样，就会跳到 “28” 的位置，这就是典型的哈希冲突问题。这个时候用公式表达就是：即K1!=K2，但f(K1)=f(K2),这种现象称为哈希冲突，在实际代码中冲突是不可避免的，一般我们有两种办法解决，第一个办法是调优哈希函数，第二个办法就是扩容。



哈希函数

我们先看调优哈希函数。什么是好的哈希函数呢？首先它的计算量不能大，其次应尽量降低冲突概率。



PHP HashFunction DJBX33A/Time33

PHP7.1.0 Zend/zend_string.h:325(zend_inline_hash_func)

PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, Perl和Berkeley DB等. 对于字符串而言这是目前所知道的最好的哈希算法，原因在于该算法的速度非常快，而且分类非常好(冲突小,分布均匀).

算法核心思想



     hash(i) = hash(i-1) * 33 + str[i]




Redis HashFunction MurmurHash

Redis在实现字典时用到了两种不同的哈希算法，MurmurHash便是其中一种（另一种是djb），在Redis中应用十分广泛，包括数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。发明算法的作者被邀到google工作，该算法最新版本是MurmurHash3，基于MurmurHash2改进了一些小瑕疵，使得速度更快，实现了32位（低延时）、128位HashKey，尤其对大块的数据，具有较高的平衡性与低碰撞率。



哈希表扩容

随着数据不断的被写入或删除执行，哈希表保存的键值对会逐渐地增多或减少，为了让哈希表的负载维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

Redis的核心数据结构就是字典(dict),dict在数据量不断增大的过程中，就会遇到上面提到的哈希碰撞问题，如果dict不够大，碰撞的概率就会增大，这样单个hash 桶存储的元素会越来愈多，查询效率就会变慢。如果数据量从几千万变成几万，不断减小的过程，DICT内存却会造成不必要的浪费。Redis的dict在设计的过程中充分考虑了dict自动扩容和收缩。



Redis扩容





Redis缩容





Redis渐进式rehash

在"Redis扩容"和"Redis收缩" 两幅动图中每幅图的第四步骤“将ht[0]中的数据利用哈希函数重新计算，rehash到ht[1]”，并不是一步完成的，而是分成N多步，循序渐进的完成的。 因为hash中有可能存放几千万甚至上亿个key，毕竟Redis中每个hash中可以存 2^32-1 键值对（40多亿），假如一次性将这些键值rehash的话，可能会导致服务器在一段时间内停止服务，毕竟哈希函数就得计算一阵子呢。



PHP阻塞式rehash

由于PHP主要应用于WEB场景，在WEB场景针对单次请求数据之间是隔离的，并且哈希的数量是有限的，那么进行一次rehash也是很快的。所以PHP内核使用阻塞形式rehash，即rehash进行中将不能对当前哈希表进行任何操作。

在来看Redis，常驻进程，接收客户端请求处理各项事务，并且操作的数据是相关且数据量较大的，如果使用PHP内核的那种方式就会出现：对哈希表进行rehash时，此时将阻塞所有客户端请求，并发性能会大大下降。



总结

实际上并非只有哈希表的时间复杂度是 O(1)，另一种索引“位图”，它的时间复杂度也是 O(1)。不过本质上，位图属于哈希表的变种，只是限制每个桶只有1个比特位，所以，虽然它消耗的空间更少，但仅用于辅助数据的主索引，快速判断对象是否存在。位图常用于解决缓存穿透的问题。（参考Redis数据结构bitmap）

哈希表本身没办法找到KEY相邻的下一个元素，所以哈希表适合做等值KV形式的查询，不支持范围查询与遍历。

最后来一张数据结构复杂度对比度。





参考

[1] PHP中的Hash算法 https://www.laruence.com/2009/07/23/994.htm