Как устроена HashMap?

# HashMap (Hash Table): Устройство и реализация

HashMap (в Python — dict) — одна из самых важных структур данных. Это структура, которая хранит пары ключ-значение и позволяет получить значение по ключу за O(1) в среднем случае.

Основная идея

Вместо того, чтобы хранить данные последовательно и искать (O(n)), HashMap использует хеш-функцию для прямого доступа к данным.

Ключ -> Hash Function -> Index -> Bucket -> Value

Как это работает внутри

1. Хеш-функция

Хеш-функция преобразует ключ в индекс массива:

def simple_hash(key, size):
    """Простая хеш-функция."""
    return hash(key) % size

hash("name")  # Может вернуть большое число: 1234567890
index = hash("name") % 10  # Преобразуем в индекс 0-9: 0

Хорошая хеш-функция должна:

• Быстро вычисляться O(1)
• Равномерно распределять значения по индексам (минимум коллизий)
• Быть детерминированной (одинаковый ключ = одинаковый индекс)

2. Коллизии и разрешение

Проблема: два разных ключа могут дать одинаковый индекс — это коллизия.

hash("name") % 10 = 3
hash("game") % 10 = 3  # Коллизия!

Способ 1: Chaining (цепочки) — Python использует этот способ

Index 0: None
Index 1: None
Index 2: [name -> "John"] -> [game -> "Chess"]  <- Linked List
Index 3: [age -> 25]
...

При коллизии элементы хранятся в списке (цепочке) по одному индексу.

Способ 2: Open Addressing — линейное зондирование

Index 0: None
Index 1: None
Index 2: name -> "John"
Index 3: game -> "Chess"  <- Если Index 2 занят, кладем в следующий

3. Load Factor и Resize

Load factor = количество элементов / размер массива

load_factor = len(items) / len(table)

Когда load factor становится слишком большим (обычно > 0.75), HashMap увеличивает размер и перестраивает индексы (rehashing).

# Когда load_factor > 0.75
old_size = 16
new_size = 32  # Удваиваем размер

# Пересчитываем индексы для всех элементов
for key, value in old_table:
    new_index = hash(key) % new_size
    new_table[new_index] = value

Реализация простой HashMap

class SimpleHashMap:
    """Простая реализация HashMap с chaining."""
    
    def __init__(self, initial_size=16):
        self.size = initial_size
        self.table = [[] for _ in range(initial_size)]  # Списки для chaining
        self.count = 0
    
    def _hash(self, key):
        """Вычисляет индекс по ключу."""
        return hash(key) % self.size
    
    def _rehash(self):
        """Увеличивает размер и перестраивает таблицу."""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        for bucket in old_table:
            for key, value in bucket:
                self.put(key, value)
    
    def put(self, key, value):
        """Добавляет или обновляет значение."""
        # Проверяем load factor
        if self.count / self.size > 0.75:
            self._rehash()
        
        index = self._hash(key)
        bucket = self.table[index]
        
        # Проверяем, есть ли уже такой ключ
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Обновляем
                return
        
        # Добавляем новый элемент
        bucket.append((key, value))
        self.count += 1
    
    def get(self, key, default=None):
        """Получает значение по ключу."""
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return default
    
    def remove(self, key):
        """Удаляет элемент."""
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        
        return False

# Использование
map_obj = SimpleHashMap()
map_obj.put("name", "John")
map_obj.put("age", 25)
map_obj.put("city", "New York")

print(map_obj.get("name"))  # John
print(map_obj.get("age"))   # 25
print(map_obj.get("unknown"))  # None

Как работает Python dict

Python 3.6+ использует более оптимизированную реализацию:

Compact Hash Table

Hash Table (индексы):  [hash | perturb | ...]
Entry Array (данные):  [(hash, key, value), (hash, key, value), ...]

Преимущества:

• Меньше памяти (не нужно хранить цепочки)
• Лучше cache locality
• Сохраняет порядок вставки элементов (Python 3.7+)

Реальная работа dict

# Python dict внутри
d = {}

# d["name"] = "John"
# 1. hash("name") = 1234567890
# 2. index = 1234567890 % table_size
# 3. Проверяем: table[index] == hash("name")?
# 4. Если да: берем значение из entry array
# 5. Если нет (коллизия): пробуем следующий индекс

d = {"name": "John", "age": 25, "city": "NYC"}
print(len(d))  # 3 элемента
print(d["name"])  # O(1) доступ

Сложность операций

# Средний случай (хорошое распределение хешей)
d[key] = value      # O(1)
value = d[key]      # O(1)
del d[key]          # O(1)
key in d            # O(1)

# Худший случай (все коллизии, цепочка из N элементов)
d[key] = value      # O(n)
value = d[key]      # O(n)

Важные свойства для интервью

1. Требования к ключам

# Ключ должен быть hashable
d = {}

# Подходит
d["string"] = 1
d[42] = 2
d[(1, 2, 3)] = 3  # Кортеж hashable

# Не подходит
d[[1, 2, 3]] = 4  # TypeError: unhashable type: 'list'
d[{"a": 1}] = 5   # TypeError: unhashable type: 'dict'

2. Hashable означает immutable

class User:
    def __init__(self, name):
        self.name = name

u = User("John")
d = {u: "data"}  # Работает по умолчанию

# Но если User mutable и меняет содержимое,
# хеш может поменяться, и мы потеряем данные!

3. Пользовательские хеш-функции

class CustomKey:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        """Определяем как вычисляется хеш."""
        return hash(self.value)
    
    def __eq__(self, other):
        """Определяем когда ключи считаются равными."""
        return isinstance(other, CustomKey) and self.value == other.value

key1 = CustomKey("test")
key2 = CustomKey("test")

d = {key1: "value1"}
print(d[key2])  # "value1" — потому что hash и eq совпадают

Производительность в реальной жизни

import time

# dict намного быстрее, чем список для поиска
data_dict = {i: i for i in range(1000000)}
data_list = list(range(1000000))

# Поиск в dict: O(1)
start = time.time()
for _ in range(1000):
    value = data_dict[500000]
print(f"dict: {time.time() - start:.6f}s")  # ~0.0001s

# Поиск в list: O(n)
start = time.time()
for _ in range(1000):
    value = data_list.index(500000)
print(f"list: {time.time() - start:.6f}s")  # ~10s

Ключевые выводы

1. HashMap использует хеш-функцию для преобразования ключа в индекс за O(1)
2. Коллизии решаются chaining (цепочками) или open addressing
3. Load factor контролирует баланс между памятью и скоростью
4. Rehashing происходит при превышении load factor (обычно 0.75)
5. Python dict — оптимизированная compact hash table, сохраняет порядок
6. Ключи должны быть hashable (immutable и с определенными hash и eq)
7. Средняя сложность O(1), худший случай O(n) при множестве коллизий