Ответ
Хеш-таблица (hash table) — это структура данных, реализующая интерфейс ассоциативного массива (словаря). Она обеспечивает в среднем O(1) время выполнения операций вставки, поиска и удаления пар «ключ-значение».
Принцип работы:
- Хеш-функция преобразует ключ в целочисленный хеш-код.
- Хеш-код отображается в индекс массива (бакета или корзины) с помощью операции (например,
hash_code % array_size). - Если два разных ключа дают один индекс (коллизия), она разрешается одним из методов:
- Метод цепочек: Каждый бакет содержит связный список (или дерево) пар ключ-значение.
- Открытая адресация: Поиск следующего свободного бакета по определенному алгоритму (линейное/квадратичное пробирование).
Пример реализации на Python (упрощенная версия с цепочками):
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # Массив бакетов (списков)
def _hash(self, key):
return hash(key) % self.size # Простая хеш-функция
def put(self, key, value):
bucket_index = self._hash(key)
bucket = self.table[bucket_index]
# Проверка на обновление существующего ключа
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
bucket_index = self._hash(key)
bucket = self.table[bucket_index]
for k, v in bucket:
if k == key:
return v
raise KeyError(f"Key '{key}' not found")
# Использование
ht = HashTable()
ht.put("apple", 50)
ht.put("banana", 30)
print(ht.get("apple")) # 50В Python встроенный тип dict является высокооптимизированной хеш-таблицей.
Ответ 18+ 🔞
Давай разжую тебе про хеш-таблицы, а то смотрю, глаза стеклянные, как у пьяного хомяка. Представь себе, что тебе нужно найти носки в своей комнате, которая похожа на последствия взрыва на помойке. Если ты будешь искать их просто так, перебирая всё подряд — это будет O(n), то есть пиздец как долго. А теперь представь, что у тебя есть волшебный шкафчик с ящиками, и на каждом носке написана формула, которая сразу говорит, в какой именно ящик его кинуть. Вот это и есть хеш-таблица, ёпта.
Как эта магия работает, блядь:
- Берёшь ключ (например, слово
"яблоко"). Ты его пихаешь в хеш-функцию — это такая хитрая жопа, которая из любого ключа делает число (хеш). В идеале, для разных ключей числа должны быть разными, но жизнь, сука, не идеальна. - Это число превращается в индекс массива (просто берешь остаток от деления на размер массива). Это и есть номер того самого ящика в шкафчике.
- А вот тут самое интересное. Два разных носка (ключа) могут получить один и тот же номер ящика. Это называется коллизия, и это пиздец, но решаемый. Есть два главных способа не охуеть от этого:
- Метод цепочек: В каждом ящике висит не один носок, а целая вешалка (список). Нашёл свой ящик — ищешь на вешалке свой конкретный носок. Просто, как три копейки.
- Открытая адресация: Ты пришёл к своему ящику, а он занят чужим потным носком. Ну хуй с ним, идешь к следующему, ищешь свободный. И так, пока не найдёшь.
Вот смотри, как это выглядит в коде, если делать на коленке (через цепочки):
class HashTable:
def __init__(self, size=10):
self.size = size
# Создаём массив, где каждый элемент — это пустой список (наш будущий ящик с вешалкой)
self.table = [[] for _ in range(size)]
def _hash(self, key):
# Берём встроенный хеш Питона и пригоняем его под размер нашей таблицы
return hash(key) % self.size
def put(self, key, value):
bucket_index = self._hash(key) # Узнали номер ящика
bucket = self.table[bucket_index] # Достали сам ящик (список)
# Сначала проверяем, а не положили ли мы уже такой ключ?
for i, (k, v) in enumerate(bucket):
if k == key: # Опа, нашли старую пару!
bucket[i] = (key, value) # Обновляем значение на новое
return
# Если не нашли — просто вешаем новый носок на вешалку
bucket.append((key, value))
def get(self, key):
bucket_index = self._hash(key)
bucket = self.table[bucket_index]
# Роемся в ящике, ищем свой ключ
for k, v in bucket:
if k == key:
return v # Ура, нашли!
# Не нашли? Ну всё, пизда.
raise KeyError(f"Key '{key}' not found")
# Пример использования, чтобы ты не бздел
ht = HashTable()
ht.put("apple", 50)
ht.put("banana", 30)
print(ht.get("apple")) # Выведет: 50А теперь главный секрет, чтобы ты сам от себя охуел: в Питоне обычный словарь (dict) — это и есть овердохуища оптимизированная хеш-таблица. Всё уже сделано, ебать копать. Ты просто им пользуешься, даже не задумываясь, какая там, блядь, магия внутри творится.