哈希表刷题总结
0 Hash Table basic 哈希表是什么？ hash table通过hash function将key映射到数组下标，实现O(1)的平均查找/插入/删除，python对应dict & set 什么时候用哈希表？ 典型信号词：查找，配对，计数，去重 需要"快速查找判断某个元素是否存在"或"快速找到某个元素对应的值" dict & set 1from collections import defaultdict, Counter 2 3# dict 4ht = {} 5ht = dict() 6ht["key"] = "value" # 插入/更新 O(1) 7ht["name"] = "rhea" 8value = ht.get("name", "default") # 查找，不存在返回default 9print("name" in ht) # 判断key是否存在 O(1) 10del ht["key"] # 删除 O(1) 11 12# defaultdict自动初始化 13ht1 = defaultdict(int) # 默认值为0，d[key]不存在时自动为0 14ht2 = defaultdict(list) # 默认值为[]，d[key]不存在时自动创建空list 15 16ht1["a"] += 1 # ht1: {"a": 1} 17print(ht1["b"]) # 0 18 19ht2["group"].append(1) # defaultdict(list, {'group': [1, 1]}) 20print(ht2["team"]) # [] 21 22# Counter 计数器 23counter = Counter("abracadabra") 24# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}) 25print(counter["a"]) # 5 26print(counter.most_common(2)) # [('a', 5), ('b', 2)] list 27 28# 常见用法：统计频次 29freq = {} 30for ch in s: 31 freq[ch] = freq.get(ch, 0) + 1 32 33# 等价于 34freq = Counter(s) 1# set 2s = set() 3s.add(x) # 添加 O(1) 4print(x in s) # 判断存在 O(1) 5s.discard(x) # 删除（不报错） O(1) 1# defaultdict(int)：词频统计 2freq = defaultdict(int) 3for word in words: 4 freq[word] += 1 # 不用判断key是否存在 5 6# defaultdict(list)：按首字母分组 7groups = defaultdict(list) 8for word in words: 9 groups[word[0]].append(word) 10 11# defaultdict(list)：建图邻接表 12graph = defaultdict(list) 13for u, v in edges: 14 graph[u].append(v) 15 graph[v].append(u) Counter 对象不能作为 dict 的 key，因为它是可变对象，不可哈希 同理,list对象也不能作为dict的key，但是tuple可以 ...