高效的哈希查找算法

查找是数据处理中为常见的一种操作，通常是指在给定信息集上寻找特定的元素。查找算法有很多种，如顺序查找、折半查找、哈希查找、分块查找等等。查找算法的优劣会影响到程序的效率，尤其是在数据规模很大的时候。

顺序查找简单，但是效率低。折半查找虽然效率不错，但使用的前提是待查找的数据有序。哈希查找是一种高效的查找算法，根据给定的关键字key，无需比较，直接利用哈希表(哈希函数)计算记录的存放地址。不同的记录有可能会得到相同的地址，可以用开放地址、链地址等方法来解决地址冲突的情况。

下面我们通过一个例子来介绍哈希查找的应用。问题描述如下：有两个字符串str和substr，统计在substr中有多少个字符被str包含。

先用顺序查找算法来实现：

int SearchStr(char *str, char *substr)
            {
                int count = 0;
                char *p;
                while (*substr != '\0')
            {
                p = str;
                while (*p != '\0')
            {
                if (*p == *substr) { count++; break; }
                p++;
            }
                substr++;
            }
                return count;
            }

上面算法通过二重循环嵌套来实现，其时间复杂度是O(n2)

再用哈希查找算法来实现：

int SearchStr(char *str, char *substr)
            {
                int count = 0，s[128] = {0}; // 定义数组，和ASCII表中前128个字符一一对应
                while (*str != '\0')
            {
                 s[*str] = 1;
                 str++;
            }
            while (*substr != '\0')
            {
                count += s[*substr];
                substr++;
            }
                return count;
            }