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

过节了,小贩为了能够更好的卖出商品,把商品做了包装,每个包装包含不同数目的商品,这样可以尽量满足顾客购买不同数量的需求。小贩比较聪明,顾客常买的数量商品,都能通过 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) 不仅要能够将大范围数值映射到小范围,还应保证输出的唯一性,我们来看下面这个例子:

价格: 1 元 (已有1人付款)
温馨提示:感谢支持。
输入邮箱或者手机号码,付款后可永久阅读隐藏的内容,请勿未经本站许可,擅自分享付费内容。
如果您已购买本页内容,输入购买时的手机号码或者邮箱,点击支付,即可查看内容。
电子商品,一经购买,不支持退款,特殊原因,请联系客服。
付费可读
时间复杂度为 O(n),明显优于暴力穷举法。关于C++语言的 STL 模板,可以参考我之前的文章:C++中STL标准容器类映射MAP简单入门使用详解

小结

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

阅读更多:   算法
添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif