如果有一个长度为n的链表（或者数组），我们要确定一个元素X是否存在于这个链表中，我们就按顺序遍历表中的每一个元素，如果有一个元素刚好为X，我们就找到了X，否则当遍历完整个表后，仍没有发现X，则可知表中并不存在一个等于X的元素。这种操作的复杂度为O(n)，因为我们要遍历整个表。另外一个更快的方式是采用二叉搜索，最终复杂度会降到为O(logn)。但是可能我们还不满意，那有没有更快的方式呢？你应该会想到那个常常被提及的结论——哈希可以使查找在常数时间内完成，即复杂度为O(1)。
但是很多人对这个结论并不太理解。不妨来打个比方。假设你要去酒店找一个叫“张三”的人，酒店有n个房间，如果按照顺序表查找的方法，你就不得不去敲所有房间的门，然后看看里面的人是不是张三。我这么说你肯定会觉得这种找法很奇怪，生活中最正常的方式应该是去问前台。前台就相当于一个哈希函数，她会把找人这个问题，映射到以房间号为答案的一个空间里，然后直接告诉某人在哪个房间或者酒店里没这个人。如果你得知张三的房间号，那你自然就不必遍历所有的房间，直接去找他就行了！这也就是哈希查找的基本原理。那哈希有没有什么问题呢，有的，一个比较直接的问题是，我们需要一个花名册来存储客人和他们房间号的对应关系。也就是说，哈希查找其实是一种用空间来换时间的策略！
哈希查找的过程如果用形象的语言来描述就是上面那样的。但是在实际中，我们如果运用这种思想来解决算法问题呢？不用着急，下面我挑选了三道Leetcode题目来具体演示一下哈希查找的具体实现。
首先是一道难度层级为Easy的题目，如下：
是否能设想一个比较快捷的解决方案呢？问题中的提示已经告诉你可以使用Hash Table来处理。所以我们会想到用一个数组来作为哈希表。每个英文字母的ASCII码作为key，而它在字符串中出现的次数将作为这个key对应的value。由于字符串t只比字符串s多一个字符，所以我的做法时先用字符串t来建立哈希表，然后在遍历s的时候，将哈希表中的对应值进行自减。这样处理之后，哈希表中value不等于0的键值对儿中的key就是我们要输出的结果。示例代码如下：
class Solution {public:
char findTheDifference(string s, string t) {
char res;
int hash[256] = {0};
for(int i = 0;i < t.size();i++)
hash[t[i]]++;
for(int i = 0;i < s.size();i++)
hash[s[i]]--;
for(int i = 0;i < 256;i++)
{
if(hash[i] != 0)
{
res = char(i);
break;
}
}
return res;
}
};
分析：这个问题的求解过程给我的启示——如果我们有个字符串，如果要通过遍历它的方法来找到其中某个字符往往时间代价是比较高的。但是如果我们用数组来建立哈希表，那么知道数组的索引，就能够直接定位对应位置的值（就像知道房间号再去酒店找人），那效率就会大幅提升了。
接下来，再来看一道中等（Medium）难度的题目：
题目的Hint已经告诉我们这道题目涉及哈希表和位操作两方面的知识。在位操作上，这个问题的解题关键点在于，A、C、G、T四个字母的ASCII码只有后三位不同，对于一个长度为10的子字符串，我们就（通过位操作）提取每个字符的后三位并把它们连成一个新的二进制串，这样一个长度为10的子字符串，就可以用一个长度为30的二进制串来表示。在我们的哈希表里，key就是这个二进制串编码，而value就是原子字符串出现的次数，只要某个子字符串出现的次数超过1，就把它放到用于存储最终结果的vector中。下面给出示例代码，注释部分已经非常详细的解释了每一步的实现，请注意参考：
class Solution {public: vector<string> findRepeatedDnaSequences(string s) { //如果待查字符串长度小于10，直接返回一个空的vector vector<string> res; if (s.size() <= 10) return res; int mask = 0x7ffffff; // 用于取一个int数的低27位 unordered_map<int, int> m; unsigned int cur = 0, i = 0; /* i从0到8，一共移动9次， 由s[i++]便可取得字符串s中的前9个字符 s[i++] & 7 用于提取每个字符二进制表示的后3位 cur最初等于0，cur << 3 表示每次左移3位， 然后 与 (s[i++] & 7) 做或运算， 如此一来最终cur的初始值就是字符串3中前9个字符的所有后三位 */ while (i < 9) // 取27位 { cur = (cur << 3) | (s[i++] & 7); } // 循环开始前 i=9，也就是从第10为一直逐个移动到字符串结束 while (i < s.size()) { // 取原来字符的27位后再接上新字符的低3位 cur = ((cur & mask) << 3) | (s[i++] & 7); m[cur] ++; if(m[cur] == 2) res.push_back(s.substr(i - 10, 10)); } return res; }};
说明：当然你也可以用00，01，10，11这四种形式来对A、C、G、T进行编码，这样需要的储存空间会更少，但是由于需要增加一个映射（编码）函数，所以会更加耗时。
（本文完）