在很多算法问题中我们需要知道某个元素是否出现过、出现了几次第一次出现的位置在哪里。如果用数组或列表查找通常需要线性扫描时间复杂度是O(n)。即使通过排序配合二分查找将查找复杂度降为O(log n)也引入了额外的排序成本。哈希表把这种从头找一遍的问题变得一下子就找到。它的基本思路是用空间换时间通过一种映射机制将查找这一操作的平均时间复杂度压缩到接近O(1)。一、哈希表哈希表先给每一个元素算一个编号再用这个编号直接去存和取数据。这个过程由哈希函数完成。它会把一个元素转换成一个整数下标。index hash(key)只要元素相同算出来的下标就一定相同。当我们再次遇到这个元素时可以直接去对应的位置查看而不需要再遍历整个数组。一个简单的哈希函数为m 8 table [None] * m def h(k): return k % m def put(k, v): table[h(k)] (k, v) def get(k): pair table[h(k)] return None if pair is None else pair[1] put(4, A) print(get(4)) # A一旦完成从 key 到 index 的映射后续操作便转化为对数组下标的访问。插入时直接写入对应位置查找时直接读取该位置更新时直接覆盖。这种访问方式避免了线性扫描正是因为省掉了从头到尾找的过程哈希表的查找效率通常可以做到接近O(1)。二、哈希冲突哈希表把 key 映射到数组下标实际情况下key 的可能性通常远大于index所以必然存在不同的 key 算出同一个 index这就是哈希冲突。如h(x) x mod m。m5时h(1)1, h(6)1, h(11)1 … 它们会撞在一起。解决冲突主要有两种经典方法1. 拉链法数组的每个位置不是存一个元素而是一个链表的头指针。冲突了就往链表后面挂。当向哈希表中插入一个键值对(k,v) 时首先使用哈希函数对key进行计算得到它对应的下标。接下来在第i 个桶中查找是否已经存在 key 等于k 的元素。如果找到了相同的 key说明这是一次更新操作此时直接将对应的 value 替换为新的v。没有找到说明这是一个新的键值对将 (k,v) 追加到该桶中用于后续查找。class HashMapChaining: def __init__(self, m8): self.m m self.buckets [[] for _ in range(m)] # 存 (k,v) def _idx(self, key): return hash(key) % self.m def put(self, key, val): i self._idx(key) bucket self.buckets[i] for j, (k, _) in enumerate(bucket): if k key: bucket[j] (key, val) # 更新 return bucket.append((key, val)) def get(self, key, defaultNone): i self._idx(key) for k, v in self.buckets[i]: if k key: return v return default2. 开放地址法所有元素都直接放在同一个大数组里。冲突时按照某种探测规则往后找空位。最常见的探测是线性探测i0 h(k) i1 (i0 1) mod m i2 (i0 2) mod m ...代码示例class HashMapLinearProbing: _EMPTY object() _DELETED object() def __init__(self, m8): self.m m self.table [self._EMPTY] * m self.size 0 def _idx(self, key): return hash(key) % self.m def put(self, key, val): i self._idx(key) first_deleted None for step in range(self.m): j (i step) % self.m slot self.table[j] if slot is self._EMPTY: target first_deleted if first_deleted is not None else j self.table[target] (key, val) self.size 1 return if slot is self._DELETED: if first_deleted is None: first_deleted j continue k, _ slot if k key: self.table[j] (key, val) # 更新 return raise RuntimeError(Hash table full) def get(self, key, defaultNone): i self._idx(key) for step in range(self.m): j (i step) % self.m slot self.table[j] if slot is self._EMPTY: return default # 遇到 EMPTY 判定不存在 if slot is self._DELETED: continue k, v slot if k key: return v return default def delete(self, key): i self._idx(key) for step in range(self.m): j (i step) % self.m slot self.table[j] if slot is self._EMPTY: return False if slot is self._DELETED: continue k, _ slot if k key: self.table[j] self._DELETED self.size - 1 return True return False三、LeetCode 练习3.1 LeetCode 1. 两数之和在遍历数组时对元素x需要判断之前是否出现过ytarget−x使用哈希表可以将这一步查找降低到接近 O(1)为此需要设计一个从元素值到下标的映射。回答某个数 y是否出现过、出现过的位置是哪令key为数组元素的值value则是这个值出现的下标接下来明确遍历过程中的状态更新规则与答案更新时机在遍历到下标 i 时首先计算needtarget−nums[i]如果 need 已存在于哈希表中说明已经找到一对满足条件的元素返回对应的下标作为答案。如果 need 不存在则将当前元素及其下标记录进哈希表 seen[nums[i]] i继续向后遍历。class Solution(object): def twoSum(self, nums, target): seen {} # value - index for i, x in enumerate(nums): need target - x if need in seen: return [seen[need], i] seen[x] i3.2 LeetCode 242. 有效的字母异位词需要判断的是两个字符串中 每个字符出现的次数完全相同出现次数统计可以尝试哈希表令key代表字符value是该字符出现的次数状态更新规则如下遍历字符串 s遇到一个字符 c执行count[c] 1再遍历字符串 t遇到一个字符 c执行count[c] - 1如果两个字符串完全由相同字符组成最终每个字符的计数都应该回到 0答案更新时机遍历结束后只要哈希表中所有字符的计数都为 0则返回 True此外还存在提前失败条件如果在遍历 t 的过程中某个字符 c 根本不在哈希表中或者减完之后出现负数说明 t 中出现了 s 没有或数量更多的字符可以直接返回 Falseclass Solution(object): def isAnagram(self, s, t): if len(s) ! len(t): return False count {} # 统计 s 中字符出现次数 for c in s: count[c] count.get(c, 0) 1 # t for c in t: if c not in count: return False count[c] - 1 if count[c] 0: return False return True3.3 LeetCode 128. 最长连续序列如果先排序再找连续段复杂度至少是O(nlogn)那么在不排序的情况下判断一个数 x 后面有没有 x1、前面有没有 x-1这正是哈希表做的事本题只关心某个数在不在数组中所以设计key为数组中的整数值即可构成一个哈希集合set状态更新规则为遍历集合中的每个数 x判断是否为起点如果 x - 1 在集合中则跳过从 cur x 开始当 cur 1 在集合中时cur 1class Solution(object): def longestConsecutive(self, nums): num_set set(nums) ans 0 for x in num_set: if x - 1 not in num_set: cur x length 1 while cur 1 in num_set: cur 1 length 1 ans max(ans, length) return ans3.4 LeetCode 146. LRU 缓存题目要求 get/put 平均 O(1)get 要 O(1) 找到 key需要哈希表put 超容量淘汰最久未使用必须能 O(1) 找到最旧的并删除/移动 可以用双向链表维护顺序哈希表中设计key为缓存的 keyvalue指向双向链表中对应节点的node定义链表头部head.next是最近使用尾部tail.prev是最久未使用。需要定义一下三个 O(1) 操作remove(node)把节点从链表摘掉、add_to_front(node)把节点插到头部表示刚被使用、move_to_front(node)先 remove 再 add_to_front在get(key)函数中若 key 不在 map返回 -1否则拿到 nodemove_to_front(node)返回 node.valueput(key,value)中若 key 已存在更新 node.valuemove_to_front(node)若 key 不存在新建 node加入 map并 add_to_front(node)若 size capacity淘汰 tail.prev从链表 remove(old)从 map 删除 old.key完整代码class Node(object): __slots__ (key, val, prev, next) def __init__(self, key0, val0): self.key key self.val val self.prev None self.next None class LRUCache(object): def __init__(self, capacity): self.cap capacity self.map {} # key - Node self.size 0 self.head Node() self.tail Node() self.head.next self.tail self.tail.prev self.head # 链表基础操作 def _remove(self, node): p, n node.prev, node.next p.next n n.prev p def _add_to_front(self, node): # 插入到 head 之后 node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _move_to_front(self, node): self._remove(node) self._add_to_front(node) def _pop_lru(self): # 弹出tail.prev lru self.tail.prev self._remove(lru) return lru # 题目接口 def get(self, key): if key not in self.map: return -1 node self.map[key] self._move_to_front(node) return node.val def put(self, key, value): if key in self.map: node self.map[key] node.val value self._move_to_front(node) return node Node(key, value) self.map[key] node self._add_to_front(node) self.size 1 if self.size self.cap: lru self._pop_lru() del self.map[lru.key] self.size - 13.5 LeetCode 1044. 最长重复子串题目要的是最长的且出现至少两次的连续子串直接枚举所有子串复杂度无疑会爆炸。因此不妨假定一个长度为 L 的重复子串判定它是否存在即可如果存在长度为 L 的重复子串那么所有 ≤ L 的长度一定也存在这是一个单调性可以使用二分的思路在区间 [1,n−1] 二分一个长度 L判断是否存在长度为 L 的重复子串使用二分的方法内部则针对给定的 L判断是否有重复子串用哈希表的方法将长度为L的子串变成一个数将字符串看成一个 base 进制的数代码中不直接算指数而是滑窗滚动去掉左端字符加上右端字符这样每次更新是O(1)。这个长度为 L 的子串的哈希值存在哈希表的key里状态更新规则为对长度 L先算第一个子串的 hash放入 seen窗口向右滑如果 hash 已在 seen 中说明找到重复返回该子串起点未找到则加入 seen。全部扫完仍无重复说明不存在长度 L 的重复子串对于外层的二分初始化left 1, right n – 1mid (left right) // 2如果存在长度mid的重复子串记录答案并令left mid 1尝试更长字串否则right mid - 1完整代码class Solution(object): def longestDupSubstring(self, s): n len(s) nums [ord(c) - ord(a) for c in s] base 26 mod (1 61) - 1 def check(L): 是否存在长度为 L 的重复子串存在则返回起点否则返回 -1 h 0 for i in range(L): h (h * base nums[i]) % mod seen {h} power pow(base, L, mod) for i in range(L, n): # 去左加右 h (h * base - nums[i - L] * power nums[i]) % mod if h in seen: return i - L 1 seen.add(h) return -1 left, right 1, n - 1 start -1 max_len 0 while left right: mid (left right) // 2 idx check(mid) if idx ! -1: start idx max_len mid left mid 1 else: right mid - 1 return if start -1 else s[start:start max_len]