这一篇的前三节都是基础的介绍，没有具体的算法题，如果对这部分知识已经一定了解，可以直接跳到第四部分。
前面我们介绍过，用顺序查找的方法来确认一个没有排序好的数组中某个元素是否存在，其时间复杂度为O(n)。基本上近似于暴力查找了，没有特别的技巧可言，具体的时间视乎运气，但平均而言，和数组的大小是呈线性关系。而如果数组已排序好，我们可以用二分查找，其时间复杂度为O(log(n))。但排序本身也是需要成本的。后面几节我们会了解到，排序是一个相当昂贵的过程。因此假如仅仅是出于方便查找的目的而将数组排序一遍，是非常不划算的。
那么有没有一种查找方法，既不要求数组排序好，又能达到很高的查找效率呢？
如题目所示，这种方法是存在的。
前面我们讲的两种查找，假如给定一个任意值，比如说整数4，那么它是可能存在于数组的任意一个位置的。比如对于一个长度为8的数组a[8]，4这个值可能不存在，也可能存储在a[0]~a[7]之间的任意一个位置。这就给我们的查找带来了难度：我们事先不知道它可能在哪，因此才需要采用各种笨方法去枚举、试探、缩小范围。
而这就给我们提供了一个新的思路：如果我们能在一个数值和它的可能存储的位置之间建立关系，那么当我们要找某个数值的时候，只需要扫一眼那些可能的位置有没有就可以了。如果没有，那就说明那个元素不在数组中。通过这种方法，我们就可以完成查找，而不必去遍历整个数组。
举一个最简单的例子：假设我们有一个大小为5的数组a[5]用来存储整数，一开始数组是空的。
这时候进来一个新的数值，38，需要储存。这一次我们并不按照先来后到的规则将其放在a[0]，而是我们事先约定一个规则：进来的数值存储的位置等于这个数除以5的余数。38%5=3。因此我们把38放在a[3]。
稍后又来了几个数，分别是21 15 4 22，我们按照对5取余这个规则，分别将它们放在a[1] a[0] a[4] a[2]。
存储任务完成。
要查找怎么办呢？假如说我们要看4是否在数组里，这回我们不必遍历整个数组了。我们知道每个数存储的位置等于其除以5的余数，因此，我们只需要按照这个规则去a[4]那里看一下就可以了。有就是有，没有就是没有。时间复杂度，请注意，是O(1)！这是说，在理想情况下，无论数组多大，由于我们知道了存储的规则，我们可以轻车熟路直接去敲某一个对应的门，只打开这个门我们就可以判断出结果。这个过程的时间损耗是恒定的，与数组大小无关。
以上便是一个最简单的哈希表(hash table)。其中x%5就是它的哈希函数，通过哈希函数，我们将每一个进来的数值映射到它该去的位置。这就给我们的查找带来极大的方便：既然我们知道了它该去的位置，那么只要去这个位置看一下就可以了。
以上是一个理想的简陋的哈希表。你可能已经发现很多问题了：
如果进来两个数，除以5的余数是相等的，比如4和9，这个时候如何分配房间？
除以5是否是心血来潮，为何不除以6？
......
嗯，便捷不是没有代价的。选择了一种O(1)的方式，也就要打包承担它带来的种种问题。
上述的哈希函数的最大的问题，是会引起冲突(collision)。当两个数对5的余数相等时，它们就要争同一个位置了。因此，如何使得每一个进来的数都能映射到一个独一无二的位置，是设计哈希函数的一个大问题。
一个可能的解决方案，是我们把取余的除数设成很大，这样就一定程度避免冲突了。设想如果把除数设为10000000，那么10000000以内的整数对其取余，都可以获得一个unique的值，都会分配到不同的房间，就不会起冲突了。
但是代价是，你要相应地准备10000000个房间。这对内存的挑战是非常大的。除非我们的元素很多，否则你可想而知这个内存的利用率是极低的。
另一种方法是一个大数进行拆解，比如我们要存储一个电话号码135-234-232-10。我们可以把它按照三位一组的方式拆开，然后求和：135+234+232+10=611。这时假如数组大小是12，那么余数就是11了。
另外的一个常用的方法，是所谓中位平方法(mid-square)。假定我们要存储的数是35，则先求它的平方35^2=1225，取中间两位，就得到22，然后再根据数组的大小取余数。
如果我们存储的不是整数，而是，比如字符，那么也可以先通过获取ASCII码的方法获取其数值，然后再设计哈希函数。
总之，设计哈希函数有非常多的常用方法，但没有系统性的一劳永逸的方法。这里面的要点是：
- 尽量避免冲突
- 尽量提高空间的利用率
- 要根据存储对象的性质来设计不同的哈希函数；比如，如果我们存储的数都是5的倍数（比如网球小局的比分，那么用取余的方法就不恰当）
一些哈希函数的设计可以参考一下这里。
基本上无论哈希函数设计得多么巧妙，冲突某种程度上总是不能避免的。那么，真的出现了冲突了怎么办？如果数组已满，每个位置上都有人了，那么当然别无他法。这个即使是一个一般数组也是这样，这里不作讨论。
要考虑的情况是，如果数组还有空位，那么很自然的选择是给新元素找一个次优的位置。
问题是如何找？
我们用empty来表示数组某个空位还没人。假设对7取余，某个数组目前是这样的：
a[7] = [35, empty, empty, 3, 11, 19, 34];
如果我们要插入一个新元素14，这时候由于余数是0，按理是要放在第一位，但由于35已经在那里。我们要另找一个位置。
一个方法是就近存储，如果余数为0的位置已经有人，则优先存到余数为1的地方，如果还是不行，就存到下一个位置，以此类推。这个方法叫Linear probing。
这个方法的优点是简单，但潜在的问题是，假如某一个位置的冲突的值非常多，除了最先占的那一个，其它元素都要顺延。注意，这个linear probing是有副作用的。像上面的例子，7存到a[1]，也使得那些取余为1的数要另找位置，这就可能带来一个连锁反应：在a[0]的这个区块附近，所有的数字都不在他们该在的位置。
一个化解方法是，找空位的时候，与其每次移动一个位置，不如移动多一点，确保整个数组都能平衡分布。这样就不会纠集在某个角落（学名叫clustering）。所以，与其加一，我们也可以加三，加五。这个过程表达起来就是：
new_position = (original_positon + offset) % array_size
offset就是我们每次加的值，如果一次不行就接着加，直到找到空位。这里要注意，我们要保证数组的每一个位置都有被访问的机会，不然有些空位永远都不会被用到，其实就使得空间的利用率降低。一个简单的办法，是保证数组的大小是一个素数(质数)。
另一个方法是与其设定一个固定的offset，我们可以改变这个数值，比如，一开始按加一的方法来找空位，如果不行，就加4，再不行就加9，16，25...
另一类处理冲突的方法，是链式定址。这种方法是说，原先的数组并不存储某具体值，而是每个房间放一个地图（指针），这张地图指向取余后结果相同的那一组元素。这样听起来比较复杂，我们用下面的示意图来说明（除以5取余）：
| 地图0 | empty | empty | 地图3 | 地图4 |
|---|---|---|---|---|
| 10 | 23 | 54 | ||
| 20 | 43 | |||
| 50 | ||||
| 70 |
第一行就用来存储指针，如果来了一个相应的元素，就把它放进相应的链条里。这种方法的好处是，我们可以确知某个元素在哪个链条里，比如与试探定址不同，我们不必担心余数为2的数跑到3那里。但不足之处也是可想而知的，随着链长度的增大，查找的难度也随之变大，而且地图本身的存储也占用了一定的内存。
那么这两种方法哪个好？这个问题这里就不讨论了，有兴趣的可以参考这里。
例1 某创业公司一直坚持小而美的理念，员工人数一直保持在11人以下。设计一个数据类型来存储每个员工的工号和工资，要求当给定某个工号时，能在O(1)的时间内返回对应的工资（或者返回：工号不存在）。工号的格式是：yyyymmdd，入职的年月日，比如20140215，工资以元为单位，比如125600。具体要求实现的类如下面所示：
class employee_info:
def __init__(self,size):
# 定义表格的大小，以及两个项目：工号和工资
self.size = size
self.id = [None]*self.size
self.salary = [None]*self.size
def set(self,id,salary):
# 该函数用来进行数据录入，输入工号和工资，将其保存在数据表里
def get(self,id):
# 该函数返回工号为id的员工的工资
def hash_function(self,id):
# 定义哈希函数
def collision_resolve(self, origin, offset):
# 定义冲突的解决方法，此处可以采用随便哪种方法(前方高能预警：下面就是参考答案。建议你自己先写一个)
class employee_info:
def __init__(self,size):
self.size = size
self.id = [None]*self.size
self.salary = [None]*self.size
def set(self,id,salary):
# 找到工号对应的哈希值，这里用的取余法：工号%self.size
hash_value = self.hash_function(id)
# 如果对应的房间还没有人，就很简单了，给对应的位置赋值就可以了
if self.id[hash_value] == None:
self.id[hash_value] = id
self.salary[hash_value] = salary
# 如果房间以及有人，就要进行冲突化解
else:
time = 1
# 这里用的是试探定址，一直找到有空位为止
while self.id[hash_value] != None:
# 用的是quadratic probing
offset = time**2
# 通过冲突解决函数确定下一个试探的房间
hash_value = self.collision_resolve(hash_value,offset)
time += 1
# 赋值
self.id[hash_value] = id
self.salary[hash_value] = salary
def get(self,id):
# 还是先找到对应的哈希值
hash_value = self.hash_function(id)
if self.id[hash_value] == None:
return '工号不存在！'
# 不然就开始找，顺利的话找一次，不然就要顺着quadratic probing的可能位置找下去，直到工号值吻合
time = 1
while self.id[hash_value] != id:
offset = time*2
hash_value = self.collision_resolve(hash_value,offset)
time += 1
# 找到了，返回相应的工资
return self.salary[hash_value]
def hash_function(self, key):
# 取余法
return key%self.size
def collision_resolve(self, origin, offset):
# 冲突化解
return (origin+offset)%self.size根据上面的注释，应该不难看懂各个函数，基本上，难点在输入数据这一块，如果哈希值对应的那个id[hash_value]里面还是None的话，就比较简单，直接赋值，不然就要根据定址方法，找到一个None为止。
我们输入一组数据来进行一个测试：
T = employee_info(11)
T.set(20131225,180000)
T.set(20140825,90000)
T.set(20141110,112300)
T.set(20141121,112300)
print T.id
print T.salary
print T.get(20131225)
print T.get(20111220)输出分别是：
[20141110, 20140825, None, None, 20131225, 20141121, None, None, None, None, None]
[112300, 90000, None, None, 180000, 112300, None, None, None, None, None]
180000
工号不存在这里值得注意的是我们输入的第四组数据(20141121, 112300)，工号对11取余等于0，按理应该放在最前面，但前面已经被(20141110,112300)占了，于是根据quadratic probing，它只能找下一个，但下一个也被(20140825, 90000)占了，于是只能设定offset=2*2=4，直接跑到id[5]，这回没人了，于是数据存放在那里。
上面的实现是一个最小化的只为说明问题的类。即使仅仅是做练习用，仍然有一些最基本的东西需要考虑进去。
练习 上面的代码中，假设有人涨工资了，工号20140824的员工工资由96000涨到112200，这时候我们要如何进行更新？用现有的set函数可以解决问题吗？如果不能，修改set函数使得满足这个需求。或者多加一个update函数。
再比如，如果有人离职了，数据自然要删除，那么是不是应该定义一个del之类的函数？这个要如何实现？
还有，假如我们定义一个11的表，而这时却输入了12个数据，这时候会出现什么样的结果？如何修改上面的代码，保证录入的数据不多于数据表的大小？
这些问题就留给大家了，如果你写出了相应的代码（不管是什么语言的），请记得和我分享！
Python本身自带了dict这种数据类型，它可以很方便地用来存储key-value这样的数据。在下面的例子里，我们会用到它。当然，你也可以不用它，而是稍微改动你上一节写的哈希表，也可以用来解下面的题目。dict的用法很简单，具体可以看这里。
例2 给定一个数组和一个目标值，从数组中找出两个数，使得它们的和等于目标值，返回这两个数在数组中的下标（从一开始）。
比如，给定[4,12,3,8]和20，则返回1和3两个下标，注意这里下标从1开始计。
这是LeetCode的第1题，难度中等。这里假定答案一定存在，且唯一。
一个很自然的笨方法是每轮询到一个数，我们就遍历一遍数组的其它元素，看有没有元素可以匹配到。但这样的话，最坏情况下时间复杂度可能达到O(n^2)。一个更好的方法，是我们可以发挥哈希表的威力，利用它能迅速查找某元素是否存在的特点，将复杂度降下来。所以一个可能的流程是这样的：1. 用一个哈希表将数组的元素和下标存起来； 2. 遍历新建的哈希表，从第一个元素开始查找是否有可以匹配的另一个元素，直到找到为止。由于我们有哈希表，因此流程的第二步最坏情况下，时间复杂度也只有O(n)。
更进一步想，第一步和第二步其实可以合并起来：每进来一个元素，我们先看哈希表是否已有匹配元素，如果有的话，就可以直接返回结果了。如果没有，则把这个新元素存进哈希表里。这样想的话，代码可以是这样的：
# num 是数组，target是目标值
def two_sum(num, target):
# 新建一个Python dict数据类型
d = {}
for i in range(len(num)):
if target-num[i] in d:
# 假如匹配值已经在哈希表里，那么直接返回两个下标就可以了
return i+1, d[target-num[i]]
else:
# 以数值为key,以下标为value，方便我们迅速通过数值来查找
d[num[i]] = i + 1例3 给定一串字符串，找出其中最长的不含任何重复字符的子字符串长度。比如，abcabcbb，则返回3。
这是LeetCode的第3题，难度中等。
不难看出，这又是一个我们需要频繁判断if a is in b的题目。通常来说这种情况下哈希表很可能派上用场。我们的基本思路是：既然是子字符串，有始有终，我们需要有两个指针（或者说标记的变量）来标识子字符串的开始和结束。基本的过程是，我们遍历整个字符串，如果遇到有新的字符和当前的子字符串里面的其它重复，就停下来，看看当前的字符串长度，与当前最长的长度比较，如果比最长的还长，我们就更新它，不然就继续往下走。
def lengthOfLongestSubstring(self, s):
if s == '':
# 如果是空字符串，就不必麻烦了
return 0
sList = list(s)
# 定义一个哈希表来记录某个字符出现的最近位置
dict = {}
# 记录最长的长度
max_len = 0
# 记录每个子字符串的开始下标
start = 0
for i in range(len(sList)):
# 遍历所有字符串
if sList[i] in dict:
# 当前字符已出现过至少一次。但如果不是在当前的字符串，就不必管，如果是在当前字符串
# 则要比较当前子字符串的长度和max_len哪个长
if(dict[sList[i]] >= start):
max_len = max(max_len, i-start)
# 重设新子字符串的开始位置
# 注意这里不能设成i+1，而应该是dict[sList[i]]+1，为什么？
start = dict[sList[i]]+1
# 如果不存在，就记录下来
dict[sList[i]] = i
max_len = max(max_len,len(sList)-start)
return max_len
这里的难点之一是当发现重复字符时，如何重设start的位置。考虑这个例子：abcdefgfhijkrtewop，不难看出最长子字符串是gfhijkrtewop，但要注意，我们第一次发现重复元素是在第二个f，这时候发现了重复的f，我们应该做的是将start设到上一个f的后面，而不是当前的f的后面。这一点要注意。
- 排序一锅端
- 标明原作者StevenSLXie;
- 标明原链接(https://github.com/StevenSLXie/Tutorials-for-Web-Developers/blob/master/%E7%AE%80%E6%98%8E%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97%EF%BC%9A%E5%93%88%E5%B8%8C%E6%9F%A5%E6%89%BE.md);
- 在可能的情况下请保持文本显示的美观。比如，请不要直接一键复制到博客之类，因为代码的显示效果可能非常糟糕;
- 请将这个转载声明包含进来；
- 在GitHub上的这个repo打星，因为我之后还会陆续更新。这样可能方便一点，对我更是一种鼓励；
- 如果你是V2EX过来的，可以在那里表示感谢；
Happy Coding!