все Python 3Алгоритмы и структуры данныхфункция

Хеш-таблица (dict)

структуры

Dict в Python — хеш-таблица. O(1) в среднем для get/set/del. Применения: подсчёт, кэш, индексирование.

Синтаксис

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

Ключом может быть только хешируемый объект — строка, число, кортеж из неизменяемого; список или множество дадут TypeError: unhashable type. Обращение d[key] к отсутствующему ключу — это KeyError, поэтому там, где ключа может не быть, берут get() с дефолтом или defaultdict. Порядок вставки гарантирован языком с версии 3.7, но это именно порядок добавления, а не отсортированность ключей.

Примеры

# Подсчёт частоты
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]}

См. также

Частые ошибки

Открыть в полном глоссарииdocs.python.orgСообщить о неточности