Как устроена HashMap внутри? Что такое бакет, как происходит вставка, что такое коллизия, рехэширование?

HashMap — это структура данных, которая хранит пары ключ-значение и обеспечивает быстрый доступ по ключу.

• Бакет — это ячейка или слот в массиве, куда помещается элемент. В HashMap ключ сначала проходит через хеш-функцию, которая вычисляет индекс бакета.

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

• Коллизия — ситуация, когда разные ключи имеют одинаковый хеш и попадают в один бакет. Для решения коллизий обычно используется связный список или дерево внутри бакета.

• Рехэширование — процесс увеличения размера массива бакетов и перераспределения элементов, когда количество элементов превышает определённый порог (load factor). Это нужно для поддержания производительности.