Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Как хранятся данные в словаре
Словарь (dict) в Python — это одна из самых важных и эффективных структур данных. Понимание его внутреннего устройства критично для написания производительного кода.
1. Hash Table — основа словаря
Словари в Python реализованы с использованием хеш-таблицы:
# Пример работы словаря
my_dict = {'name': 'Alice', 'age': 30, 'city': 'Moscow'}
# Под капотом:
# 1. Ключ 'name' преобразуется в хеш: hash('name') = 8730427504939206848
# 2. Индекс в таблице: hash_value % table_size
# 3. Значение 'Alice' хранится по этому индексу
print(hash('name')) # Выведет хеш-значение
print(hash('age')) # Разные ключи — разные хешы
Хеширование превращает строку (или другой объект) в целое число, которое используется как индекс в массиве.
2. Хеш-функция и коллизии
# Хеширование в Python
key = 'python'
hash_value = hash(key) # Детерминированное число
# ВАЖНО: с Python 3.3 хеши рандомизированы для безопасности
# Между запусками интерпретатора хеши одного значения могут отличаться
# Но в одной сессии — всегда одинаковые
print(hash('test')) # 2314058222371831637
print(hash('test')) # 2314058222371831637 (тот же результат)
# Коллизия — когда разные ключи имеют одинаковый хеш по модулю
dict_size = 8
key1 = 'cat'
key2 = 'dog'
hash1 = hash(key1) % dict_size
hash2 = hash(key2) % dict_size
if hash1 == hash2:
print('Коллизия! Нужно разрешить')
else:
print('Разные индексы')
Коллизии разрешаются открытой адресацией (open addressing): если ячейка занята, ищем следующую свободную.
3. Структура хеш-таблицы в памяти
# Каждая запись в словаре хранит:
# - hash(key) — хеш ключа
# - key — сам ключ
# - value — значение
# В памяти это выглядит примерно так:
"""
┌─────────────────────────────────────┐
│ Хеш-таблица (compact) │
├─────────────────────────────────────┤
│ индекс | hash | key | value │
├─────────────────────────────────────┤
│ 0 | - | UNUSED | UNUSED │
│ 1 | ... | 'name' | 'Alice' │
│ 2 | ... | 'age' | 30 │
│ 3 | ... | 'city' | 'Moscow' │
│ 4 | - | UNUSED | UNUSED │
└─────────────────────────────────────┘
"""
# С Python 3.6 порядок вставки сохраняется
# С Python 3.7+ это гарантированная особенность
my_dict = {}
my_dict['first'] = 1
my_dict['second'] = 2
my_dict['third'] = 3
for key in my_dict:
print(key) # first, second, third (в порядке вставки)
4. Коэффициент Заполнения (Load Factor)
# Словарь растет и перестраивается автоматически
my_dict = {}
print(f'Размер: {len(my_dict)}')
# Добавляем элементы
for i in range(100):
my_dict[i] = i * 2
# Словарь автоматически увеличивает размер
# Это происходит при load_factor > 0.66 (примерно)
print(f'Размер: {len(my_dict)}')
# Получить информацию о размере таблицы
print(my_dict.__sizeof__()) # Размер в байтах
# Коэффициент заполнения
def estimate_load_factor(dictionary):
# Это приблизительная оценка
import sys
items_count = len(dictionary)
# Реальный размер таблицы зависит от реализации
return items_count / max(1, items_count) # Упрощенно
5. Почему ключи должны быть хешируемы
# Хешируемые (hashable) объекты — те, у которых есть hash()
# ✅ Хешируемые
hashable = {
'string': 'OK',
42: 'OK',
(1, 2, 3): 'OK', # Кортежи хешируемы
frozenset([1, 2]): 'OK' # frozenset хешируемы
}
# ❌ Не хешируемые
try:
bad_dict = {
[1, 2, 3]: 'Ошибка', # Списки не хешируемы
}
except TypeError as e:
print(f'Ошибка: {e}')
try:
bad_dict = {
{'a': 1}: 'Ошибка', # Словари не хешируемы
}
except TypeError as e:
print(f'Ошибка: {e}')
# Почему так?
print(hash([1, 2, 3])) # TypeError: unhashable type
print(hash({'a': 1})) # TypeError: unhashable type
# Потому что они изменяемые (mutable)
ls = [1, 2, 3]
ls[0] = 999 # Можем изменить
# Если бы список был ключом, его хеш поменялся бы
# И мы не смогли бы найти значение по старому хешу
6. Кастомные классы как ключи
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def __hash__(self):
# Должны вернуть целое число
return hash((self.name, self.age))
def __eq__(self, other):
# Два объекта с одинаковым hash() должны быть ==
if not isinstance(other, Person):
return False
return self.name == other.name and self.age == other.age
person_dict = {}
alice = Person('Alice', 30)
person_dict[alice] = 'Engineer'
# Работает, потому что определили __hash__ и __eq__
print(person_dict[alice]) # 'Engineer'
# Но это опасно — если объект изменяется, хеш меняется
alice2 = Person('Alice', 30)
print(person_dict[alice2]) # 'Engineer' (работает)
# Лучше использовать immutable объекты как ключи
7. Производительность операций
# Сложность операций в словаре
my_dict = {'a': 1, 'b': 2, 'c': 3}
# O(1) в среднем — прямой доступ по ключу
value = my_dict['a'] # Самый быстрый способ
# O(n) в худшем случае (много коллизий, но редко)
value = my_dict.get('a', None) # Тоже O(1)
# O(n) — перебор всех ключей
for key in my_dict:
print(key)
# O(n) — перебор всех значений
for value in my_dict.values():
print(value)
# Проверка наличия ключа — O(1)
if 'a' in my_dict:
print('Есть')
# Проверка наличия значения — O(n)
if 'value' in my_dict.values():
print('Есть') # Медленнее, нужно проверить все значения
8. Оптимизация памяти
# Python 3.6+ оптимизирован для словарей
# __slots__ сокращает использование памяти
class OptimizedPerson:
__slots__ = ['name', 'age']
def __init__(self, name, age):
self.name = name
self.age = age
# Вместо __dict__ используются slots
# Память экономится, особенно для множества объектов
persons = [OptimizedPerson(f'Person{i}', i) for i in range(1000)]
# Для больших данных можно использовать OrderedDict
from collections import OrderedDict
ordered = OrderedDict()
ordered['z'] = 1
ordered['a'] = 2
print(list(ordered.keys())) # ['z', 'a'] (порядок вставки)
# Или defaultdict для группировки
from collections import defaultdict
groups = defaultdict(list)
groups['key1'].append('value1')
groups['key1'].append('value2')
print(groups['key1']) # ['value1', 'value2']
9. Под капотом: CPython источник
# В CPython словарь реализован в Objects/dictobject.c
# Упрощенная структура (pseudo-code):
"""
struct dictentry {
Py_hash_t hash; // Хеш ключа
PyObject *key; // Указатель на ключ
PyObject *value; // Указатель на значение
};
struct dictobject {
Py_ssize_t fill; // Кол-во заполненных ячеек
Py_ssize_t used; // Кол-во используемых ячеек
dictentry *table; // Массив записей
};
"""
# Ключи и значения хранятся как PyObject* (указатели)
# Это позволяет хранить любые объекты Python
10. Примеры оптимизации
# Плохо: проверяем наличие и потом получаем
if key in my_dict:
value = my_dict[key] # Два поиска!
# Хорошо: используем get
value = my_dict.get(key, default_value) # Один поиск
# Плохо: изменяем словарь во время итерации
for key in my_dict:
if condition(key):
del my_dict[key] # Ошибка или непредсказуемое поведение
# Хорошо: итерируем по копии ключей
for key in list(my_dict.keys()):
if condition(key):
del my_dict[key]
# Хорошо: используем comprehension
my_dict = {k: v for k, v in my_dict.items() if condition(k)}
Заключение
Словари в Python реализованы с помощью хеш-таблиц, что обеспечивает O(1) доступ к элементам в среднем. Понимание этого механизма помогает:
- Писать более эффективный код
- Избегать неожиданного поведения
- Выбирать правильные структуры данных
- Оптимизировать использование памяти