Что такое коллизии?

Что такое коллизии?

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

Как возникают коллизии?

Каждый объект в Java имеет метод hashCode(), который возвращает целое число. Это число используется как индекс в массиве HashMap для определения места хранения объекта:

int index = hashCode() % arrayLength;

Проблема возникает, когда разные ключи возвращают одинаковые или близкие хеш-коды. Например, строки "AB" и "BA" могут генерировать одинаковые хеш-коды, и оба ключа будут претендовать на одно место в массиве.

Способы разрешения коллизий

Chaining (Цепочки) Это основной метод, используемый в Java HashMap. Вместо простого массива каждая ячейка содержит связный список (или в Java 8+ — красно-чёрное дерево при более чем 8 элементах). Если два ключа имеют один индекс, они сохраняются в одну цепочку:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
// Если оба ключа хешируются в индекс 5,
// они образуют цепочку в этой ячейке

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

Практическое значение

Понимание коллизий критично при:

• Реализации кастомных equals() и hashCode(): неправильная реализация приводит к неэффективности HashMap
• Оптимизации производительности: частые коллизии замораживают работу приложения
• Работе с большими объёмами данных: нужно понимать, как HashMap расширяется и перехешируется

В Android особенно важно избегать коллизий при работе с кешами и хранилищами данных, так как это может привести к утечкам памяти и ухудшению производительности приложения на устройстве с ограниченными ресурсами.