Что такое коллизия в HashMap

1️⃣ Как кратко ответить

Коллизия в HashMap происходит, когда два разных ключа имеют одинаковое хэш-значение, что приводит к их размещению в одной и той же "корзине" (bucket). Это может замедлить операции поиска, вставки и удаления, так как требуется дополнительная обработка для разрешения коллизий, например, с помощью цепочек (linked lists) или открытой адресации.

2️⃣ Подробное объяснение темы

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

Как работает HashMap

1. Хэш-функция: При добавлении элемента в HashMap, ключ пропускается через хэш-функцию, которая возвращает индекс массива, где будет храниться значение. Например, если у нас есть ключ "apple", хэш-функция может преобразовать его в индекс 5.

2. Корзины (buckets): HashMap состоит из массива корзин. Каждая корзина может содержать несколько элементов, если произошла коллизия.

3. Коллизия: Если два ключа, например "apple" и "banana", имеют одинаковый индекс после применения хэш-функции, они попадают в одну и ту же корзину. Это и есть коллизия.

Разрешение коллизий

Существует несколько методов для разрешения коллизий:

• Цепочки (Chaining): В этом методе каждая корзина содержит связанный список всех элементов, которые имеют одинаковый хэш-индекс. Если происходит коллизия, новый элемент добавляется в связанный список соответствующей корзины.

  #include <iostream>
  #include <list>
  #include <vector>
  #include <string>
  ​
  class HashMap {
  private:
      // Вектор списков для хранения элементов
      std::vector<std::list<std::pair<std::string, int>>> table;
      int size;
  ​
      // Простая хэш-функция
      int hashFunction(const std::string& key) {
          return key.length() % size;
      }
  ​
  public:
      HashMap(int s) : size(s) {
          table.resize(size);
      }
  ​
      // Метод для вставки элемента
      void insert(const std::string& key, int value) {
          int index = hashFunction(key);
          table[index].emplace_back(key, value);
      }
  ​
      // Метод для поиска элемента
      int get(const std::string& key) {
          int index = hashFunction(key);
          for (const auto& pair : table[index]) {
              if (pair.first == key) {
                  return pair.second;
              }
          }
          throw std::runtime_error("Key not found");
      }
  };
  ​
  int main() {
      HashMap map(10);
      map.insert("apple", 1);
      map.insert("banana", 2);
      std::cout << "Value for 'apple': " << map.get("apple") << std::endl;
      std::cout << "Value for 'banana': " << map.get("banana") << std::endl;
      return 0;
  }
  

  В этом примере HashMap использует вектор списков для хранения элементов. Хэш-функция вычисляет индекс на основе длины ключа. Если два ключа имеют одинаковую длину, они попадают в одну и ту же корзину, и их значения хранятся в связанном списке.

• Открытая адресация (Open Addressing): В этом методе, если корзина занята, ищется следующая свободная корзина по определенному алгоритму (например, линейное или квадратичное пробирование).

Зачем это нужно

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