Чем хеш-таблица (HashMap) лучше массива?

Хеш-таблица (HashMap) vs Массив

Хеш-таблица и массив решают разные задачи. Вопрос не в том, что "лучше", а в том, что использовать для конкретной задачи.

Основные различия

Когда HashMap лучше массива

1. Поиск по ключу вместо индекса:

# ❌ Плохо: массив требует линейного поиска
users = ["alice", "bob", "charlie"]
if "bob" in users:  # O(n) поиск!
    print("Found")

# ✅ Хорошо: HashMap даёт O(1) поиск
users = {"alice": 25, "bob": 30, "charlie": 28}
if "bob" in users:  # O(1) поиск!
    print(users["bob"])  # 30

2. Произвольные ключи:

# ❌ Массив требует числовых индексов
data = [None] * 1000000  # Тратим память впустую
data["user_123"] = "invalid"  # TypeError!

# ✅ HashMap работает с любыми ключами
data = {}
data["user_123"] = {"name": "Alice", "age": 25}
data[(1, 2)] = "tuple key"
data["nested"] = {"level1": {"level2": "value"}}

3. Разреженные данные:

# ❌ Массив неэффективен для разреженных данных
matrix = [None] * 10000000  # Почти все None
for i in range(10000000):
    if matrix[i] is not None:
        print(matrix[i])

# ✅ HashMap хранит только реальные значения
matrix = {}  # Только 100 элементов
matrix[(0, 5)] = 42
matrix[(999, 999)] = 100
for key, value in matrix.items():
    print(f"{key}: {value}")

4. Агрегирование данных:

# ❌ Неудобно с массивом
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = []
for word in words:
    found = False
    for item in freq:
        if item[0] == word:
            item[1] += 1
            found = True
            break
    if not found:
        freq.append([word, 1])

# ✅ Просто с HashMap
freq = {}
for word in words:
    freq[word] = freq.get(word, 0) + 1
# {"apple": 3, "banana": 2, "cherry": 1}

Когда массив лучше HashMap

1. Последовательный доступ:

# ✅ Массив эффективнее
scores = [10, 20, 30, 40, 50]
for score in scores:  # Идеальная локальность в памяти
    print(score)

# ❌ HashMap не гарантирует порядок (в Python < 3.7)
scores_dict = {0: 10, 1: 20, 2: 30, 3: 40, 4: 50}
for key in scores_dict:
    print(scores_dict[key])  # Случайный порядок доступа

2. Память и производительность:

# Массив компактнее в памяти
arr = [1, 2, 3, 4, 5]  # Линейный блок памяти
hmap = {0: 1, 1: 2, 2: 3, 3: 4, 4: 5}  # Больше overhead'а

# Доступ к массиву быстрее из-за кеша процессора
import time
big_array = list(range(1000000))
big_dict = {i: i for i in range(1000000)}

start = time.time()
for i in range(1000000):
    _ = big_array[i]
print(f"Array: {time.time() - start:.4f}s")

start = time.time()
for i in range(1000000):
    _ = big_dict[i]
print(f"Dict: {time.time() - start:.4f}s")
# Array примерно в 2-3 раза быстрее

3. Фиксированный размер и известное количество элементов:

# ✅ Используй массив когда размер известен
def calculate_average(scores):
    total = sum(scores)  # Быстро
    return total / len(scores)

# ❌ HashMap добавляет complexity
def calculate_average_dict(scores_dict):
    total = sum(scores_dict.values())
    return total / len(scores_dict)

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

Пример 1: Кеш (HashMap)

class Cache:
    def __init__(self):
        self.data = {}  # HashMap идеален
    
    def get(self, key):  # O(1)
        return self.data.get(key)
    
    def set(self, key, value):  # O(1)
        self.data[key] = value
    
    def delete(self, key):  # O(1)
        del self.data[key]

Пример 2: Индексирование записей (HashMap)

# Индекс по email
users = []
user_index = {}  # Для быстрого поиска

def add_user(user_data):
    users.append(user_data)
    user_index[user_data["email"]] = len(users) - 1

def find_by_email(email):
    idx = user_index.get(email)  # O(1)
    return users[idx] if idx is not None else None

Пример 3: Обработка последовательности (Array)

# Обработка временного ряда
def moving_average(prices, window=5):
    result = []  # Массив
    for i in range(len(prices) - window + 1):
        avg = sum(prices[i:i+window]) / window
        result.append(avg)
    return result

Когда используется комбинация

# HashMap индексов + Массив данных
class IndexedArray:
    def __init__(self):
        self.data = []  # Быстрый доступ к памяти
        self.indices = {}  # Быстрый поиск
    
    def add(self, key, value):
        self.indices[key] = len(self.data)
        self.data.append(value)
    
    def get(self, key):
        idx = self.indices.get(key)  # O(1)
        return self.data[idx] if idx is not None else None  # O(1)
    
    def get_all(self):
        return self.data  # O(1) возвращение всего

Выводы

HashMap лучше для:

• Поиска по произвольному ключу
• Работы с разреженными данными
• Key-value хранилищ и кешей
• Когда не нужен порядок

Массив лучше для:

• Последовательного доступа
• Максимальной производительности
• Работы с памятью
• Когда порядок важен

Выбор зависит от задачи. Нет "лучше" или "хуже" — есть инструмент для конкретной работы.