Как устроена хеш-таблица (HashMap)?

Как устроена хеш-таблица (HashMap)?

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

Принцип работы

Хеш-таблица основана на хеш-функции — функции, которая преобразует ключ в индекс массива:

Map<String, int> map = {
  "apple": 5,
  "banana": 3,
  "cherry": 8,
};

print(map["apple"]); // O(1) в среднем случае

Процесс:

1. Вычисляется хеш ключа: hash = hashCode(key)
2. Вычисляется индекс в таблице: index = hash % tableSize
3. По индексу ищется значение

Коллизии (Collisions)

Когда два разных ключа дают одинаковый индекс, возникает коллизия.

Методы разрешения коллизий:

1. Chaining (цепочки)

class HashTable {
  List<List<MapEntry<String, int>>> table = List.generate(16, (_) => []);
  
  void set(String key, int value) {
    int hash = key.hashCode;
    int index = hash % table.length;
    
    for (var entry in table[index]) {
      if (entry.key == key) {
        entry = MapEntry(key, value);
        return;
      }
    }
    
    table[index].add(MapEntry(key, value));
  }
  
  int? get(String key) {
    int hash = key.hashCode;
    int index = hash % table.length;
    
    for (var entry in table[index]) {
      if (entry.key == key) return entry.value;
    }
    return null;
  }
}

2. Open Addressing

class OpenAddressingHashTable {
  List<MapEntry<String, int>?> table = List.filled(16, null);
  
  void set(String key, int value) {
    int hash = key.hashCode;
    int index = hash % table.length;
    
    while (table[index] != null && table[index]!.key != key) {
      index = (index + 1) % table.length;
    }
    
    table[index] = MapEntry(key, value);
  }
}

Хеш-функция

Хорошая хеш-функция:

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

class User {
  final String id;
  final String name;
  
  User(this.id, this.name);
  
  @override
  int get hashCode => id.hashCode ^ name.hashCode;
  
  @override
  bool operator ==(Object other) =>
      identical(this, other) ||
      other is User &&
          runtimeType == other.runtimeType &&
          id == other.id &&
          name == other.name;
}

final map = <User, String>{};
final user = User("1", "John");
map[user] = "admin";
print(map[user]); // O(1) поиск

Resize (Расширение таблицы)

Когда таблица заполняется, происходит расширение в 2 раза:

class DynamicHashTable {
  List<List<MapEntry<String, int>>> table = List.generate(16, (_) => []);
  int _size = 0;
  
  void set(String key, int value) {
    int hash = key.hashCode;
    int index = hash % table.length;
    
    table[index].add(MapEntry(key, value));
    _size++;
    
    if (_size / table.length > 0.75) {
      _resize();
    }
  }
  
  void _resize() {
    List<List<MapEntry<String, int>>> oldTable = table;
    table = List.generate(oldTable.length * 2, (_) => []);
    _size = 0;
    
    for (var bucket in oldTable) {
      for (var entry in bucket) {
        set(entry.key, entry.value);
      }
    }
  }
}

Использование в Dart

Map — стандартная реализация хеш-таблицы:

final map = <String, int>{};
map["count"] = 5; // O(1)
print(map["count"]); // O(1)
map.remove("count"); // O(1)

final linkedMap = <String, int>{};
linkedMap["a"] = 1;
linkedMap["b"] = 2;
for (var key in linkedMap.keys) print(key);

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

• Поиск (get) — O(1) в среднем, O(n) в худшем
• Вставка (set) — O(1) в среднем
• Удаление (remove) — O(1) в среднем
• Итерация — O(n)

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

1. Используйте Map для быстрого поиска
2. Правильно реализуйте hashCode и ==
3. Избегайте частого resize
4. Не меняйте ключи после вставки

Хеш-таблица — фундаментальная структура данных для эффективной разработки.