哈希查找算法的基本原理，以及一个简单实例

过节了，小贩为了能够更好的卖出商品，把商品做了包装，每个包装包含不同数目的商品，这样可以尽量满足顾客购买不同数量的需求。小贩比较聪明，顾客常买的数量商品，都能通过 2 个包装组合得到。因为包装太多了，小贩记不住每个包装中的商品数量，所以小贩对每个包装从 0 到 n 编了号，并且统计了每个包装中的商品数量。为了搭配出 m 个商品，你能编写程序帮助小贩快速挑选出两个包装的编号吗？

帮助小贩的问题可以简化为如下编程模型：有一个数组 nums 包含若干整数，给定目标值 m，从 nums 找到两个整数，这两个整数之和等于 m，返回这两个整数在 nums 数组中的下标。下面是示例：

给定 nums = [2, 7, 11, 15]，m = 9
因为 nums[0] + nums[1] = 9
所以返回 [0, 1]

有一点要注意，考虑到实际问题，每个包装只能用一次，所以数组 nums 中的数字也只能使用一次。

暴力穷举法

编写程序解决现实中的问题，一般来说都会有一种简单粗暴的方法，对于本文涉及的“帮助小贩”问题，最容易想到的是暴力穷举法，逐次组合数组中的数字，求和后与目标值 m 对比。这一过程的代码很简单，下面是一段C语言代码示例：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *res = malloc(sizeof(int) * 2);
    if (NULL==res)
        return NULL;
    int i, j;
    for (i=0; i<numsSize-1; i++) {
        for (j=i+1; j<numsSize; j++) {
            if (nums[i]+nums[j] == target) {
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }
    free(res);
    return NULL;
}

注意，twoSum() 函数内部调用了 malloc() 函数分配内存，当然了，这是C语言语法，不是本文讨论的重点。

twoSum() 函数的确能够解决“帮助小贩”问题，但是时间效率却不够好，它的内部有两个 for() 循环，因此我们能够轻易的知道 twoSum() 函数的时间复杂度为 O(n^2)，随着数组长度的增加，函数运行时间会呈 n 的平方式增长。

仔细观察 twoSum() 函数的实现，不难发现时间主要消耗在两个 for() 循环，其中内部的 for() 循环中的

for (j=i+1; j<numsSize; j++) {
    if (nums[i]+num[j] == target)
...

可以改写为：

for (j=i+1; j<numsSize; j++) {
    if (nums[j] == target-nums[i])
...

令 x = target-nums[i]，很明显，twoSum() 函数有相当一部分的时间消耗在从 nums 数组中查找等于 x 的值，而查找一个长度为 n 的数组，最坏的时间复杂度为 O(n)。要优化 twoSum() 函数的时间复杂度，减少这一查找过程消耗的时间是一个可行的办法，为此，我们对 nums 数组做如下修改：

• 初始化时，确定最大元素的值 max_elem
• 定义数组最大长度为 nums[max_elem+1]
• [2, 7, 11, 15] 元素不再依次放入 nums，而是放在和下标相应的位置：nums[2]=2, nums[7]=7, nums[11]=11, nums[15]=15，其他位置元素赋值为 -1

-1 是负数，在“帮助小贩”问题中是一个没有意义的数值，因为没有包装里的商品数目为负数。不过正因如此，-1 可以作为一个标记数值，如果 nums[y]=-1，则说明我们没有商品数量为 y 的包装。这样一来，当需要从 nums 中查询数值 x 时，直接根据下标即可（nums[x]），无需再遍历数组了，此时，twoSum() 函数的代码可以改写为：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *res = malloc(sizeof(int) * 2);
    if (NULL==res)
        return NULL;
    int i, j;
    for (i=0; i<numsSize; i++) {
        int x = target-nums[i];
        if (nums[x]!=-1 && x!=i) {
            res[0] = i;
            res[1] = x;
            *returnSize = 2;
            return res;
        }
    }
    free(res);
    return NULL;
}

修改后的 twoSum() 函数的时间复杂度为 O(n)，因为此时查询 nums 的最坏时间复杂度仅为 O(1)。

不过敏锐的读者应该发现了，为了提升 twoSum() 函数的时间效率，我们牺牲了不少空间——在上例中，仅 4 个元素，程序却需要能够容纳 16 个元素的数组，这造成了空间浪费。如果数组中存在一个更大的数值，例如 1024，那么 nums 数组浪费的空间就更多了（需要 nums[1025]）。

进一步优化算法

前面的优化算法虽然显著的提升了时间效率，但是却造成了大量的空间浪费，这一点在存在较大元素值的情况下尤为明显，而且在实际应用中究竟会出现多大的元素值是不可预期的，所以上面的“优化算法”算不得“优化”，因为我们甚至能不能预测它将会造成多少空间浪费。

不过反过来想，如果“优化算法”的空间浪费能够得以解决，那么它的确是一个不错的算法。假设存在一个函数 f(x)，它能够将任意数值映射到小范围内，例如对于数组元素 [2, 7, 11, 15]，f(x) 能够实现下面这样的映射：

• f(2) = 0
• f(7) = 1
• f(11) = 2
• f(15) = 3

当然，顺序不重要，下面这样的映射也是可以的：

• f(11) = 0
• f(15) = 1
• f(2) = 2
• f(7) = 3

那么，我们就无需再定义很大（取决于元素最大值）的数组了，对于“帮助小贩”问题 [2, 7, 11, 15]，只需要定义能够容纳 4 个元素的 nums[4]，就能实现时间复杂度为 O(n) 的算法：

//int nums[] = {2,7,11,15};

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *res = malloc(sizeof(int) * 2);
    if (NULL==res)
        return NULL;
    int i, j;
    for (i=0; i<numsSize; i++) {
        int x = target-nums[i];
        if (f(x)<numsSize && f(x)!=i) {
            res[0] = i;
            res[1] = f(x);
            *returnSize = 2;
            return res;
        }
    }
    free(res);
    return NULL;
}

事实上，这就是哈希（hash）查找的基本原理，f(x) 函数一般被称作“哈希函数”。很多人也习惯把“哈希”称作“散列”，意义是一致的。理想情况下的 f(x) 不仅要能够将大范围数值映射到小范围，还应保证输出的唯一性，我们来看下面这个例子：

本文通过一个生活中的实例“帮助小贩”问题，逐步探讨了程序开发中必须掌握的“哈希查找”算法。“哈希查找”算法是一个优秀的算法，在理想情况下，时间复杂度为O(1)，当然了，哈希查找非常依赖哈希函数，劣质的哈希函数有可能让哈希查找的时间复杂度退化为O(n)。文章的最后，使用了C++中的STL映射map解决了“帮助小贩”问题。