Где применяется HashMap?

Где применяется HashMap?

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

Основные области применения

1. Кеширование данных

# Простой кеш для функции
from functools import lru_cache

@lru_cache(maxsize=128)
def expensive_function(n):
    # Результаты автоматически кешируются
    return n ** 2

# Или явный кеш
cache = {}

def fibonacci(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = fibonacci(n - 1) + fibonacci(n - 2)
    cache[n] = result
    return result

2. Индексирование и быстрый поиск

# Индекс пользователей по ID
users_by_id = {
    1: {'name': 'Alice', 'email': 'alice@example.com'},
    2: {'name': 'Bob', 'email': 'bob@example.com'},
    3: {'name': 'Charlie', 'email': 'charlie@example.com'}
}

# Быстрый поиск O(1) вместо O(n) в списке
user = users_by_id[1]  # Мгновенно

# Индекс email -> ID
email_to_id = {
    'alice@example.com': 1,
    'bob@example.com': 2
}

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

from collections import Counter

# Подсчёт частоты букв в тексте
text = "hello world"
char_frequency = Counter(text)
print(char_frequency)  # Counter({'l': 3, 'o': 2, ...})

# Или через обычный dict
def count_frequency(items):
    freq = {}
    for item in items:
        freq[item] = freq.get(item, 0) + 1
    return freq

4. Обработка конфигурационных параметров

config = {
    'debug': True,
    'database_url': 'postgresql://localhost/mydb',
    'max_connections': 100,
    'timeout': 30,
    'api_key': 'secret_key_here'
}

# Быстрый доступ к параметрам
debug_mode = config.get('debug', False)
db_url = config['database_url']

5. Групировка данных

# Группировка студентов по факультетам
students_by_faculty = {}

students = [
    {'name': 'Alice', 'faculty': 'CS'},
    {'name': 'Bob', 'faculty': 'Math'},
    {'name': 'Charlie', 'faculty': 'CS'}
]

for student in students:
    faculty = student['faculty']
    if faculty not in students_by_faculty:
        students_by_faculty[faculty] = []
    students_by_faculty[faculty].append(student['name'])

print(students_by_faculty)  # {'CS': ['Alice', 'Charlie'], 'Math': ['Bob']}

# Или более элегантно через defaultdict
from collections import defaultdict

students_by_faculty = defaultdict(list)
for student in students:
    students_by_faculty[student['faculty']].append(student['name'])

6. Проверка принадлежности множеству (O(1) вместо O(n))

# Плохо: O(n)
blacklist = ['user1', 'user2', 'user3', ...]
if username in blacklist:
    raise Exception("User is blacklisted")

# Хорошо: O(1)
blacklist = {'user1': True, 'user2': True, 'user3': True}
if username in blacklist:
    raise Exception("User is blacklisted")

# Или ещё лучше
blacklist = {'user1', 'user2', 'user3'}  # set тоже O(1)

7. Кеширование результатов API

class APICache:
    def __init__(self):
        self.cache = {}
    
    def get(self, endpoint, params):
        key = (endpoint, tuple(sorted(params.items())))
        if key in self.cache:
            return self.cache[key]
        
        # Реальный запрос к API
        response = fetch_from_api(endpoint, params)
        self.cache[key] = response
        return response

8. Таблица трансляции символов

# Маппирование значений
status_map = {
    1: 'pending',
    2: 'approved',
    3: 'rejected',
    4: 'archived'
}

status_code = 2
status_name = status_map[status_code]  # 'approved'

9. Решение задач на собеседованиях

# Проверка, есть ли дублирующиеся элементы
def has_duplicates(arr):
    seen = {}
    for num in arr:
        if num in seen:
            return True
        seen[num] = True
    return False

# Two Sum задача
def two_sum(numbers, target):
    num_map = {}
    for i, num in enumerate(numbers):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

10. Синтаксис и переменные компилятора

# Таблица символов в интерпретаторе
locals()  # Возвращает dict с локальными переменными
globals()  # Возвращает dict с глобальными переменными
vars(obj)  # Возвращает __dict__ объекта

Временная сложность

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

• Когда нужен упорядоченный перебор — используй список или OrderedDict
• Когда нужна неизменяемость ключей — используй frozenset или tuple
• Когда нужна особая структура — граф, дерево, кучу

HashMap — это основная структура данных современного программирования, без которой невозможно представить эффективную разработку. Она используется везде: от кешей и индексов до кодирования алгоритмов и хранения конфигурации.