考虑这样一个场景，在某次破案行动中，警方已经获取目标嫌疑人的身份证号，现在有一个身份证信息数据库，存储着身份证号与个人信息的数据。此时警方需要通过身份证号在名单中获取目标嫌疑人的姓名、年龄、地址等信息，考虑这是一个千万级的数据库，如何查询才是有效的呢？
我们考虑该国家的身份证是8位，目标身份证号为50585346，这时候出现了几种不同的查询方法：
A警察采用了顺序遍历的方法，从这个字典中一页一页的往后翻00000000、00000001、…这显然是一种非常麻烦的方法；B警察稍微聪明一点，拿起字典从中间随便翻起一页，看到号码为26000000，目标身份证号比该号码大，于是又在后部分中翻起一页…这种“二分查找”的方法大大提高了查询效率。
稍稍分析就可以看出A警察的查询效率为O(n), B警察的查询效率为O(log n)，有没有一种方法能够实现最理想的查询，达到常数级的查询效率呢？这时哈希表便出现了，哈希表正是这样一种存储结构，能够实现最理想的查询效率，没有一种数据结构能在查询方面比哈希表更优秀。
然而很多人对于哈希表作用的理解，到“快速查询”这一步就停止了，其实哈希表的作用远大于此，本文以LeetCode中几道题目为案例，对哈希表的多种功能进行剖析。
Python中实现哈希表最常用的方法就是字典，下面对Python字典的基本操作进行总结：
方法作用Dict = {}创建字典Dict[“a”] = 1键a的值为1Dict.get(“a”)获取键a的值，没有则返回空Dict.has_key(key)字典是否有键a，没有则返回False，有返回TrueDict.clear()字典清空Dict.keys()以列表返回一个字典所有的键Dict.values()以列表返回一个字典所有的值Dict.items()以列表返回一个字典所有的(键, 值) 元组数组虽然在大多数情况下，通过Python字典实现哈希表已经足够了。然而针对一些特殊情况（比如后面的例题6），哈希表的值为一些特殊的变量（如列表时），我们需要提前对哈希表值的变量类型进行申明，这时候我们可以利用python的Collection库，具体实现方法如下：
from collections import defaultdict dictn = defaultdict(list) #该哈希表的值为列表类型很多人入门LeetCode都是从这道题目入手的，也是通过这道题了解到哈希标的强大。采用普通暴力破解方法解题时，需要对列表中的元素两两组合进行遍历，时间代价为O(n2)，这显然不是最优的解决办法。
于是我们引入哈希表快速查询的机制，对于列表中每一个元素num[i]，都存在一个“配对值”com[i]，使得num[i]+com[i]=target。于是我们可以用一个哈希字典来存储这样的映射关系，以题目示例中的nums数组为例，这样的映射关系为：
nums = [2, 7, 11, 15] #原始序列 hashmap = {2:7,7:2,11:-2,15:-6} #转换的哈希字典这样一来，我们仅仅通过对原始序列进行一次遍历，每访问一个元素检查该元素是否为哈希字典中的key，如果是则返回正确的答案，如果否则将这一组新的映射关系添加到字典中，整个过程的时间代价为O(n)。具体代码实现如下：
class Solution(object): def twoSum(self, nums, target): hashmap={} for i,num in enumerate(nums): if hashmap.get(target-num) is not None: return [hashmap.get(target - num),i] hashmap[num] = i这道题目就是一道典型的通过哈希表实现快速查询的案例，这是LeetCode的第一道题目，难度不高。下面我们通过LeetCode的一道Medium题目对哈希表实现快速查询进行巩固。
这道题目是依图面试的原题，如果采用滑动窗口、动态规划，时间代价都不能满足需求，巧妙用哈希表 Θ(n)时间代价便可解决。本质上该题目是两数之和的变形题，建议读者在学习两数之后，自行继续代码书写进行巩固。
以下为参考的案例代码：
class Solution(object): def subarraySum(self, nums, k): pdict = {} result = 0 pre = [0] pdict[k] = 1 for i in range(len(nums)): # iterate all pre_num in pnums pre.append(pre[-1] + nums[i]) p = pre[-1] if pdict.has_key(p): # if p in dict, add result result = result + pdict[p] target = k + p # tagget number to find if not pdict.has_key(target): # if targer not in pdict pdict[target] = 1 # set value of target to 1 else: pdict[target] = pdict[target] + 1 # add value by one return result哈希表本质上是一种”键与值映射“的数据结构，这种映射关系使得哈希表在查找功能上表现优异。同时，正是存在这种映射关系，我们可以利用哈希表实现计数功能，此时哈希表的键为需要计数的元素，哈希表的值为该元素出现的次数。
这道题目难度不高，只要对”字母异位词“的含义理解了，很快就能解决。对于两个字符串A和B，如果字符串A中不同元素出现的次数和字符串B中不同元素出现的次数一样，那么字符串A和字符串B就是一组字母异位词。针对”统计元素出现的次数“这样的计数问题，哈希表就是一种有效的解决办法。
哈希表可以对字符串中元素出现的次数计数，同样地，也可以对数组中元素出现的次数计数。例4是一道利用数组元素计数解题的例题，建议读者参考例3的思路进行解决。
以下为参考代码：
class Solution(object): def intersect(self, nums1, nums2): dictn = {} resultlist = [] for num in nums1: if not dictn.get(num): dictn[num] = 1 else: dictn[num] = dictn[num] + 1 for num in nums2: if dictn.get(num) and dictn.get(num) != 0 : resultlist.append(num) dictn[num] = dictn[num] - 1 return resultlist做这道题目之前，需要有一个数学定理的支撑：
当余数出现循环时，其对应的商也会出现循环。因此我们需要通过哈希表记录余数和商出现的位置。
那么问题来了，下面那种映射关系才是考虑周全的呢？
A. 余数 --> 位置
B. 余数+商 --> 位置
答案应该是B。读者可通过1/7和1/6两个示例进行对比验证。
哈希表仅仅只是这道题目的解决工具，而这道题目的难点在于分类讨论与边界条件的考虑。该问题可分成整数部分和小数部分两部分进行解决，而每部分的算法设计中又要分不同情况进行考虑，尤其需要对特殊情况进行考虑。
边界条件是LeetCode面试的考察重点，尤其对于测试岗位的面试来说，边界条件是否考虑周全是面试官所重点关注的。下面给出一些可能的边界条件，这些边界条件，你考虑全了吗？
类子类型案例0的影响除数为00/10的影响被除数为01/0结果不完整只有整数部分4/2结果不完整只有小数部分1/3负数的影响分子为负数（-1）/ 3负数的影响分母为负数（2）/（- 3）负数的影响分子分母均为负数（-2）/（- 3）小数点后的不同情况小数点后需要添加01/30小数点后的不同情况小数点后为有限小数1/8小数点后的不同情况小数点后为无限循环小数1/7小数点后的不同情况小数点后为无限循环不小数该情况不可能出现下面给出参考代码：
class Solution(object): def fractionToDecimal(self, numerator, denominator): result = "" dictn = {} # to store the postion of the fractional part position = 0 repeat = True def add(result, position, nstr): return result + nstr, position + len(nstr) #special case if numerator * denominator < 0: result, position = add(result, position, "-") if denominator == 0: return numerator, denominator = abs(numerator), abs(denominator) # calculate the part before "." if numerator >= denominator: result, position = add(result, position, str(numerator / denominator)) numerator = numerator % denominator else: result, position = add(result, position, "0") # calculate the part after "." # numerator % demoninator == 0 if numerator == 0: return result else: result, position = add(result, position, ".") # add zero numerator = numerator * 10 while numerator < denominator : result, position = add(result, position, "0") numerator = numerator * 10 while numerator % denominator != 0 : #print(dictn) reminder = numerator % denominator key = str(reminder) + " " + str(numerator / denominator) # Attention!!! We must treat both reminder and numerator / denominator as key if not dictn.get(key) : dictn[key] = position position = position + 1 else: position = dictn.get(key) repeat = False break result = result + str(numerator / denominator) numerator = reminder * 10 if repeat: result = result + str(numerator / denominator) else: result = result[:position] + "(" + result[position:] + ")" return result方法1：暴力破解法
该题目首先想到的是暴力破解法，按照从上到小、从左到右的顺序进行遍历，具体的遍历方法如下图所示。然而这种方法会出现超时的现象。
class Solution(object): def findDiagonalOrder(self, nums): def findmaxclength(nums): maxl = 0 for i in nums: maxl = max(len(i), maxl) return maxl maxc = findmaxclength(nums) maxr = len(nums) print(maxc, maxr) resultlist = [] # first column: from top to end for i in range(maxr): r_id = i while r_id >= 0: # i - c_id : row id c_id : column_id if i - r_id <= len(nums[r_id]) - 1: # to prevent index out of range resultlist.append(nums[r_id][i - r_id]) r_id = r_id - 1 # last row: from left to right for i in range(maxr, maxr + maxc): r_id = maxr - 1 while r_id >= 0: if i - r_id <= len(nums[r_id]) - 1: # to prevent index out of range resultlist.append(nums[r_id][i - r_id]) r_id = r_id - 1 return resultlist方法2：哈希表法
如何对暴力破解中的超时问题进行优化呢？我们可以利用哈希表，将row+col相等的数存在列表中放入哈希表。哈希表的键为row+col，哈希表中的值为row+col相等的数所存放的列表，这样可以大大减少访问次数。
from collections import defaultdict class Solution(object): def findDiagonalOrder(self, nums): dictn = defaultdict(list) resultlist = [] for row in range(len(nums)): for col in range(len(nums[row])): dictn[row + col].append(nums[row][col]) for key in sorted(dictn.keys()): resultlist.extend(dictn[key][::-1]) return resultlist