简单散列函数算法

1. 问题

设有10个非负整数，用不多于20个的储存单元来存放，如何存放这10个数，使得搜索其中的某一个数时，在储存单元中查找的次数最少？

问题类似于，有10个带号码的球，放到编号为{0, 1, 2, …, 19}共20个盒子中，每个盒子最多放一个，问如何放，使能够用最少的次数打开盒子，知道任一个球所在的盒子编号？

2. 分析

2.1 最简单的情况

设10个球的号码分别是 ： {1, 2, 3, …, 10}

那么我们只要10个盒子，按顺序依次将球放入{1, 2, 3, …, 10}中，那么任一个球的所在的盒子就是球的号码，打开对应编号的盒子，一次即可找到这个球

当然，我们还可以这样放：

设球的号码 = n, 盒子的编号 = k (k ∈ {0, 1, 2, …., 9})

球放入盒子的方式 f(n) = (n +  x) % m = （n + x） % 10

即将每个球偏移x个位置，当x = 1时，则如：1号球放到2号盒子，2号球放到3号盒子，依次类推，最后10号球将在0号盒子

很类似于古代西方国家流行的一种加密方式，将每个字母都往后顺移x个位，如good，都顺移一个位，则变成hppe了，即使密报被截获，不懂的人根本不知道是个啥意思，接收方的人只要把每个字母往后回移一位即可得原文。

这种方法简单，好用，但对于10个数不连续或者没有规律的情况下，就无法处理了，如{0, 1, 2, 7, 9, 15, 19, 20, 77, 38}，因为最大的数出现了77，除非有77个盒子，才能用上述方法，当有球号码是10000时，就得10000个盒子来放10个球，严重浪费空间

2.2 改进的方案

因为有20个盒子，我们可以用2.1的方法先放一部分球到编号为{0, 1, 2, …, 9}的盒子中，为了简单，这里设x = 0：

f(n) = n % 10

则{0, 1, 2, 7, 9, 15, 19, 20, 77, 38}分别可以放到对应编号为如下的盒子中：

  {0, 1, 2, 7, 9, 5,   9,   0,  7,   8}

我们看到0号球和20号球都需要放入0号盒子，这就产生了一个冲突（因为一个盒子最多只能放一个球，类似一个内存地址只能放一个数），为了解决这种冲突，我们把有冲突的球放到第2组编号为{10, 11, 12, …, 19}的10个盒子中，则这10个存放的情况如下：

剩下的冲突的球{19, 20, 77}从小到大依次放入第2组盒子：

当要查找某一个球x时，先计算f(x) = (x % 10)，如果f(x)对应的盒子中就是这个球，则只要1次就能找到，和2.1的方法一样

但当球x不在f(x)盒子中时，则往第2组盒子中查找，因为第2组盒子是有序的，我们用二分查找，可在log2(n)次内找到其对应的球(n = 第二组盒子中球的数量)

那么这种算法的最坏情况是什么呢？

我们可以看出，只要不能在第一组盒子中找到该球，则其需要log2(n)次才能找到，当n最大时，即n = 10（因为最多只有10个球），表示10个球都在第2组盒子中

此时，需要的次数 = log2(10) = 3，加上在第一组盒子中找的一次，共需要4次

3. 有没有更好的方法？

从2.2的算法中，我们可以看到，其最终还是用到了二分查找，最坏的查找次数为log2(n)，当球的数量增加时，则需打开盒子的次数也要增加，这就不是散列函数了，如用来做STL中的map容器，查找某个key对应的值也将不是常量时间，那么有没有更好的算法使其时间复杂度降为常量呢？方法2.2的问题主要是由于有冲突，从而会导致需要二分查找，如果能有一种方法能解决掉该冲突问题，那么即可将时间复杂度降为常量范围。

简单散列函数算法

原文：http://www.cnblogs.com/organic/p/6262240.html