Какие примеры использования хеш-таблицы знаешь?

# Примеры использования хеш-таблиц

Хеш-таблица — одна из самых важных структур данных в программировании. Она предоставляет среднюю сложность O(1) для операций поиска, вставки и удаления, что делает её фундаментом для многих алгоритмов и приложений.

Теоретические основы

Как работает хеш-таблица

# В Python dict реализует хеш-таблицу
d = {}

# При добавлении значения:
d['key'] = 'value'

# Python вычисляет хеш ключа
hash_value = hash('key')  # Возвращает целое число

# Использует хеш для определения индекса в массиве
index = hash_value % len(internal_array)

# Хранит значение по этому индексу
internal_array[index] = 'value'

# При поиске повторяет процесс
retrieved = d['key']  # O(1) в среднем случае

Практические примеры

1. Кеширование результатов (Memoization)

Проблема: Повторные вычисления

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# fibonacci(35) требует миллионы вычислений
# fibonacci(34) вычисляется дважды!
# fibonacci(33) вычисляется трижды!
# Экспоненциальная сложность O(2^n)

Решение с хеш-таблицей:

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    result = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    memo[n] = result
    return result

# fibonacci(35) теперь работает мгновенно!
# Сложность: O(n) вместо O(2^n)

print(fibonacci(35))  # 9227465 (за миллисекунды)

Декоратор для кеширования:

from functools import lru_cache

@lru_cache(maxsize=128)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(100))  # Работает мгновенно

2. Подсчёт частоты элементов

Проблема: Найти самый частый элемент

arr = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

# Неправильно: сортировка O(n log n)
sorted_arr = sorted(arr)

# Правильно: хеш-таблица O(n)
freq_map = {}
for num in arr:
    freq_map[num] = freq_map.get(num, 0) + 1

# Найти максимум
most_common = max(freq_map, key=freq_map.get)
print(f"Самый частый: {most_common}, встречается {freq_map[most_common]} раз")

Python встроенные инструменты:

from collections import Counter

arr = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(arr)

# Получить N самых частых элементов
most_common_3 = counter.most_common(3)
print(most_common_3)  # [(4, 4), (3, 3), (2, 2)]

3. Определение уникальных элементов

Проблема: Найти все уникальные элементы

arr = [1, 2, 2, 3, 3, 3, 1, 4]

# Наивный подход: O(n^2)
unique = []
for item in arr:
    if item not in unique:  # O(n) поиск
        unique.append(item)

# Правильно: O(n) с хеш-таблицей
unique = set(arr)  # set использует хеш-таблицу
print(unique)  # {1, 2, 3, 4}

Проверка уникальности в строке:

def has_unique_chars(s: str) -> bool:
    """Проверить, все ли символы уникальны"""
    return len(s) == len(set(s))

print(has_unique_chars("hello"))  # False (l повторяется)
print(has_unique_chars("abc"))    # True

4. Обнаружение дубликатов

Проблема: Найти первый дубликат

arr = [1, 2, 3, 2, 4]

# Используя хеш-таблицу O(n)
seen = set()
for num in arr:
    if num in seen:  # O(1) поиск
        print(f"Первый дубликат: {num}")
        break
    seen.add(num)

Найти все дубликаты:

arr = [1, 2, 3, 2, 4, 3]

freq = {}
duplicated = set()

for num in arr:
    freq[num] = freq.get(num, 0) + 1
    if freq[num] > 1:
        duplicated.add(num)

print(duplicated)  # {2, 3}

5. Анаграммы и группировка слов

Проблема: Найти все анаграммы

def find_anagrams(words):
    """Группировать слова по их анаграммам"""
    anagram_map = {}
    
    for word in words:
        # Сортируем буквы как ключ
        key = ''.join(sorted(word))
        if key not in anagram_map:
            anagram_map[key] = []
        anagram_map[key].append(word)
    
    return list(anagram_map.values())

words = ["listen", "silent", "enlist", "hello", "world"]
print(find_anagrams(words))
# [["listen", "silent", "enlist"], ["hello"], ["world"]]

6. Two Sum (собеседования)

Проблема: Найти два числа, которые в сумме дают target

# Неправильно: O(n^2) с вложенными циклами
def twoSum_bruteforce(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# Правильно: O(n) с хеш-таблицей
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:  # O(1) поиск
            return [seen[complement], i]
        seen[num] = i
    return []

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))  # [0, 1]

7. Валидация скобок (балансировка)

Проблема: Проверить, что скобки балансированы

def is_valid_parentheses(s: str) -> bool:
    # Используем dict для маппинга скобок
    bracket_map = {'(': ')', '[': ']', '{': '}'}
    stack = []
    
    for char in s:
        if char in bracket_map:
            stack.append(char)
        elif char in bracket_map.values():
            if not stack or bracket_map[stack.pop()] != char:
                return False
    
    return len(stack) == 0

print(is_valid_parentheses("([{}])"))  # True
print(is_valid_parentheses("([{])"))   # False

8. LRU Cache (система кеширования)

Проблема: Кеш с ограниченным размером

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        # Переместить в конец (самый свежий)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            # Удалить старое значение
            self.cache.pop(key)
        elif len(self.cache) == self.capacity:
            # Удалить самый старый (первый в очереди)
            self.cache.popitem(last=False)
        
        # Добавить новое
        self.cache[key] = value
        self.cache.move_to_end(key)

# Использование
cache = LRUCache(2)
cache.put(1, 'a')
cache.put(2, 'b')
print(cache.get(1))  # 'a'
cache.put(3, 'c')    # Вытесняет ключ 2
print(cache.get(2))  # -1 (не найден)

9. Поиск в большом наборе данных

Проблема: Проверить, есть ли миллионы IP-адресов в списке запрещённых

# Неправильно: O(n) поиск в списке
blacklist = ["192.168.1.1", "10.0.0.1", ...]  # 1 млн адресов

def is_blacklisted(ip):
    return ip in blacklist  # O(n) поиск!

# Правильно: O(1) поиск в set
blacklist = {"192.168.1.1", "10.0.0.1", ...}  # set

def is_blacklisted(ip):
    return ip in blacklist  # O(1) поиск

Результат:

• Проверка 10 млн IP: ~10 миллионов операций → ~1 миллион операций
• Ускорение в 10 раз!

10. Моделирование графов

Представление графа с помощью хеш-таблицы:

# Неориентированный граф
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# DFS обход
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:  # O(1) доступ к соседям
        if neighbor not in visited:  # O(1) проверка
            dfs(graph, neighbor, visited)

dfs(graph, 'A')  # A -> B -> D -> C

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

Операция       | Средний случай | Худший случай | С хорошим хешем
─────────────────────────────────────────────────────────────
Поиск          | O(1)           | O(n)          | O(1)
Вставка        | O(1)           | O(n)          | O(1)
Удаление       | O(1)           | O(n)          | O(1)
Энумерация     | O(n)           | O(n)          | O(n)

Когда использовать

Используй хеш-таблицу (dict/set в Python):

• Кеширование данных
• Подсчёт частоты элементов
• Поиск дубликатов
• Быстрый поиск (не нужна сортировка)
• Группировка данных
• Анаграммы и анализ текста

Не используй когда:

• Нужен порядок элементов (используй OrderedDict или список)
• Часто нужны диапазонные запросы (используй бинарное дерево)
• Много коллизий (плохой хеш-функции)

Заключение

Хеш-таблица — универсальный инструмент для решения задач с требованиями O(1) доступа. В Python это реализовано как встроенные типы dict и set. Овладение умением использовать хеш-таблицы критично для написания эффективного кода и прохождения собеседований.