Что такое хеш-таблица?

Хеш-таблица (Hash Table): Структура данных для быстрого поиска

Хеш-таблица (или hash map) — это структура данных, которая реализует ассоциативный массив — мощный инструмент для хранения пар ключ-значение с быстрым O(1) доступом в среднем случае.

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

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

1. Берется ключ
2. Вычисляется хеш ключа (число)
3. Это число используется как индекс в массиве
4. По этому индексу хранится значение

Ключ: "Alice"
  ↓
[Хеш функция]
  ↓
Индекс: 3
  ↓
Массив: [value0, value1, value2, value3="Alice's data", ...]

Хеш-функция

Свойства хорошей хеш-функции:

• Детерминированная (один ключ → одно значение)
• Быстрая (вычисляется за O(1))
• Равномерное распределение (минимум коллизий)
• Сложная (похожие ключи → разные хеши)

// Простой пример хеш-функции
int simpleHash(String key, int size) {
  int hash = 0;
  for (int i = 0; i < key.length; i++) {
    hash += key.codeUnitAt(i);
  }
  return hash % size; // Приведение к размеру таблицы
}

print(simpleHash('Alice', 10));   // Какой-то индекс 0-9
print(simpleHash('Bob', 10));      // Другой индекс 0-9
print(simpleHash('Alice', 10));    // Же индекс, что первый

Коллизии (Collisions)

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

// Примерно одинаковый хеш
int hash1 = simpleHash('Alice', 10);   // Индекс 5
int hash2 = simpleHash('Bob', 10);     // Тоже индекс 5?

Решение 1: Цепочка (Chaining)

Массив: [null, null, null, null, null, [Alice->data1, Bob->data2], null, ...]
         0    1    2    3    4    5

Если коллизия — храним список элементов на одном индексе.

Решение 2: Открытая адресация (Probing)

Массив: [null, Alice->data1, null, Bob->data2, null, ...]
         0    1              2    3

Если место занято — ищем следующее свободное место.

Хеш-таблица в Dart: Map

Map в Dart — это хеш-таблица:

// Создание Map (хеш-таблица)
Map<String, int> ages = {
  'Alice': 30,
  'Bob': 25,
  'Charlie': 35,
};

// O(1) — быстрый поиск по ключу
print(ages['Alice']);  // 30 (константное время!)
print(ages['Bob']);    // 25

// O(1) — добавление
ages['David'] = 28;

// O(1) — удаление
ages.remove('Bob');

// O(n) — итерация по всем элементам
ages.forEach((key, value) {
  print('$key: $value');
});

Set — специализированная хеш-таблица

Set использует ту же хеш-таблицу, но хранит только ключи:

// Set — уникальные значения
Set<String> colors = {'red', 'green', 'blue'};

// O(1) — быстрая проверка наличия
if (colors.contains('red')) {
  print('Красный есть');
}

// O(1) — добавление
colors.add('yellow');

// O(n) — итерация
for (String color in colors) {
  print(color);
}

// Хеш-таблица не позволяет дубликаты
Set<int> numbers = {1, 2, 3};
numbers.add(1); // Не добавляется (уже есть)
print(numbers.length); // 3, не 4

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

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

class UserCache {
  final Map<int, User> _cache = {};
  
  // O(1) добавление в кэш
  void cache(int id, User user) {
    _cache[id] = user;
  }
  
  // O(1) быстрый поиск
  User? getFromCache(int id) {
    return _cache[id];
  }
  
  // Использование
  User? user = getFromCache(123); // Если есть в кэше — O(1)
  if (user == null) {
    user = await api.fetchUser(123); // Если нет — запрашиваем
    cache(123, user); // Кэшируем для будущего
  }
}

2. Подсчёт частоты (histogram):

// Подсчитать сколько раз каждое число встречается
List<int> numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4];

Map<int, int> frequency = {};
for (int num in numbers) {
  frequency[num] = (frequency[num] ?? 0) + 1;
}

print(frequency); // {1: 1, 2: 2, 3: 3, 4: 4}
// O(n) временная сложность вместо O(n²) с List

3. Быстрая проверка уникальности:

// Есть ли дубликаты в списке?
List<String> emails = ['a@mail.com', 'b@mail.com', 'a@mail.com'];

// Плохо: O(n²)
bool hasDuplicates1(List<String> list) {
  for (int i = 0; i < list.length; i++) {
    for (int j = i + 1; j < list.length; j++) {
      if (list[i] == list[j]) return true;
    }
  }
  return false;
}

// Хорошо: O(n) с Set
bool hasDuplicates2(List<String> list) {
  Set<String> seen = {};
  for (String email in list) {
    if (seen.contains(email)) return true;
    seen.add(email);
  }
  return false;
}

4. Индексирование данных:

class UserRepository {
  final Map<int, User> _usersById = {};     // Индекс по ID
  final Map<String, User> _usersByEmail = {}; // Индекс по Email
  
  void addUser(User user) {
    _usersById[user.id] = user;        // O(1) добавление
    _usersByEmail[user.email] = user;  // O(1) добавление
  }
  
  User? findById(int id) {
    return _usersById[id]; // O(1) поиск
  }
  
  User? findByEmail(String email) {
    return _usersByEmail[email]; // O(1) поиск
  }
}

LinkedHashMap — упорядоченная хеш-таблица

LinkedHashMap сохраняет порядок вставки:

var map = LinkedHashMap<String, int>();
map['first'] = 1;
map['second'] = 2;
map['third'] = 3;

// Итерация в порядке вставки
for (var entry in map.entries) {
  print(entry); // first, second, third
}

// Обычный Map может быть в любом порядке
var unordered = {'c': 3, 'a': 1, 'b': 2};
for (var key in unordered.keys) {
  print(key); // Порядок неопределён
}

Сравнение структур данных

Операция      List    Set/Map
─────────────────────────────
Поиск         O(n)    O(1)
Добавление    O(n)    O(1)
Удаление      O(n)    O(1)
Итерация      O(n)    O(n)
Память        O(n)    O(n+коллизии)

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

Используй Map/Set когда:

• Нужен быстрый поиск по ключу
• Нужна уникальность значений (Set)
• Нужны индексы (несколько ключей для поиска)
• Большой объём данных для поиска

Используй List когда:

• Нужен порядок элементов
• Нужен доступ по индексу (array[0])
• Мало элементов (O(n) не проблема)
• Итерация основная операция

Лучшие практики

1. Выбирайте правильную структуру:

// Плохо: O(n) каждый раз
if (userList.any((u) => u.id == searchId)) { }

// Хорошо: O(1)
if (userIds.contains(searchId)) { }

2. Используйте get с default значением:

int count = frequencies[key] ?? 0;
Set<String> tags = (data[key] as Set?) ?? {};

3. Кэшируйте при необходимости:

Map<String, Result> cache = {};

Result getData(String key) {
  if (cache.containsKey(key)) {
    return cache[key]!; // O(1) из кэша
  }
  Result result = expensiveOperation(key); // O(n) вычисление
  cache[key] = result; // O(1) сохранить
  return result;
}

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