all Python 3Algorithms & data structuresfunction

Hash table (dict)

data structures

A Python dict is a hash table. get/set/del take O(1) on average. Uses: counting, caches, indexes.

Syntax

d = {}
d[key] = value
d.get(key, default)

Keys must be hashable — strings, numbers, tuples of immutables; a list or a set gives TypeError: unhashable type. Reading a missing key with d[key] raises KeyError, so when the key may be absent use get() with a default, or a defaultdict. Insertion order has been guaranteed by the language since 3.7, but that is the order you added things in, not sorted order.

Examples

# Подсчёт частоты
from collections import Counter
words = 'the cat sat on the mat the cat sat'.split()
c = Counter(words)
print(c.most_common(3))  # → [('the',3),('cat',2),('sat',2)]

from collections import Counter
# Анаграммы
def are_anagrams(s1, s2):
    return Counter(s1) == Counter(s2)
print(are_anagrams('listen', 'silent'))  # → True
print(are_anagrams('hello', 'world'))   # → False

# Первый неповторяющийся символ
def first_unique(s):
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for ch in s:
        if count[ch] == 1:
            return ch
    return None
print(first_unique('leetcode'))  # → l

# Two Sum с хеш-таблицей O(n)
def two_sum_hash(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target-x in seen:
            return [seen[target-x], i]
        seen[x] = i
    return []
print(two_sum_hash([2,7,11,15], 9))  # → [0,1]

# Кэш с defaultdict
from collections import defaultdict
graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)
graph[2].append(4)
print(dict(graph))  # → {1:[2,3], 2:[4]}

See also

Common errors

Open in the full glossarydocs.python.orgReport an inaccuracy