哈希桶算法

通常大家所说的哈希函数也可以称为散列函数，哈希函数的功能只是将你的目标key通过一种映射方法，也可以说是一种函数运算f，最后得到你目标的

hashValue = f(key)，这里的函数f就称为哈希函数/散列函数。

可以看到哈希函数的选择是一个很关键的步骤。为了引进哈希桶算法，必然要介绍一下哈希冲突，因为哈希桶就是为了解决哈希冲突的。举个例子，有一组序列为[10,11,21,31,38,48,55]，使用的哈希函数为f(key) = key mod 10

这个时候就产生了冲突了，也就是不同的key通过映射后得到了同样值的hashvalue。

哈希桶算法其实就是链地址解决冲突的方法

如上面的例子所示，就可以设置桶的个数为10，也就是f(key)集合的个数，而这样的话，hashvalue就可以作为桶的索引，将10,11分别通过f(key)得到0，1则可将这几个key放入桶0， 1的首地址所指的内存中，然后处理值为21的key，得到hashvalue值为1，这个时候需要放入桶1中，但桶1的首地址已经有了元素11，怎么办？那么就可以为每个桶开辟一片内存，内存中存放所有hashvalue相同的key，冲突的key之间用单向链表进行存储，这样就解决了哈希冲突，在查找对应key的时候，只需要通过key索引到对应的桶，然后从桶的首地址对应的节点开始查找，就是链表顺序找到，对比key的值，直到找到对应key的信息，所以，在冲突的时候，特别是冲突率比较高的时候，桶内的链表就会很长，使得查找效率比较低，而在最坏的情况下，所有的key都对应同一个hashvalue，当然这种情况不会出现，这样的哈希函数选取的也没有意义了，假设这种情况出现，那么哈希表就退化成了单链表，其他桶内存浪费，且将查找效率从O(1)直接降到了O(N)，所以上面才说，哈希函数的选择也是很关键的。

如果相同元素过多，元素在一个桶内部链接过长，反而导致时间复杂度上升。解决思路是桶中元素不再指向链表，而指向一个红黑树。

Redis中值的数据结构有String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）五种，使用可参考 https://www.jianshu.com/p/fdd24839f460 。

而底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。在下图中，可以看到，哈希桶中的 entry 元素中保存了 key和 value指针，分别指向了实际的键和值。

哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。毕竟，哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。Redis 解决哈希冲突的方式，就是 链式哈希 。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

如下图所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，导致了哈希冲突。此时，entry1 元素会通过一个 next指针指向 entry2，同样，entry2 也会通过 next指针指向 entry3。这样一来，即使哈希桶 3 中的元素有 100 个，我们也可以通过 entry 元素中的指针，把它们连起来。

其实，为了使 rehash *** 作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

这个过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。为了避免这个问题，Redis 采用了 渐进式 rehash 。

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

对于 String 类型来说，找到哈希桶就能直接增删改查了，所以，哈希表的 O(1) *** 作复杂度也就是它的复杂度了。

一个集合类型的值，第一步是通过全局哈希表找到对应的哈希桶位置，第二步是在集合中再增删改查。首先， *** 作复杂度与集合的底层数据结构有关。例如，使用哈希表实现的集合，要比使用链表实现的集合访问效率更高。其次， *** 作效率和这些 *** 作本身的执行特点有关，比如读写一个元素的 *** 作要比读写所有元素的效率高。

String类型对应的简单动态字符串到后面再说，集合类型的底层数据结构主要有 5 种：整数数组、双向链表、哈希表、压缩列表和跳表。

整数数组和双向链表也很常见，它们的 *** 作特征都是顺序读写，也就是通过数组下标或者链表的指针逐个元素访问， *** 作复杂度基本是 O(N)， *** 作效率比较低；压缩列表和跳表我们平时接触得可能不多，但它们也是 Redis 重要的数据结构。

压缩列表 实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

跳表 在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

Redis 之所以能快速 *** 作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的 *** 作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。不过，集合类型的范围 *** 作，因为要遍历底层数据结构，复杂度通常是 O(N)。

不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的 *** 作复杂度都是 O(N)。因此，因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。

排序过程：

1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶

2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序

3.将各个桶中的数据有序的合并起来

设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

适用于序列比较均匀的情况，否则会很耗空间。

或者特殊的场景，例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。

另，桶排序的瓶颈主要是桶数量的选择。

另此算法为稳定的排序算法。

排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：

1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。

2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length

计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。

设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类推，最后得到的桶的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约，时间上跟桶排序相当。

使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。

另此算法为稳定的排序算法。

---