Если хэши, бакеты, контракт equals и hashcode для вас давно пройденный этап, то вот вопрос со звездочкой:
🤔 Можно ли сделать что-то быстрее, чем HashMap? Хотя бы для частных случаев? И как это сделать в java?
Об этом и будет сегодняшний пост. Несложный компутер саенс для расширения кругозора.
HashMap - реализация структуры данных хэш-таблица. Принцип прост: вычисляем хэш ключа, находим нужный бакет, кладём пару ключ-значение.
Нюансы начинаются, если в бакете уже что-то есть. Тогда есть два основных пути:
1️⃣ Метод цепочек (separate chaining hash tables)
Его использует HashMap. Допускаем, что в одном бакете могут быть несколько элементов, организуем их в список или дерево.
Альтернативное название - open hashing. “Открытость” означает, что данные лежат не в самом массиве, а где-то в куче.
2️⃣ Метод открытой адресации (open addressing hash tables)
Если бакет занят, вычисляем следующий, пока не найдем свободный. Самое простое - проверить соседний бакет, но есть и другие стратегии.
Как только нашли свободный, кладём туда пару ключ-значение.
Поиск в такой структуре прост:
▫️ Считаем хэш ключа
▫️ Вычисляем бакет
▫️ Смотрим, какой ключ там лежит. Если нужный - возвращаем значение
▫️ Если ключ не совпал, вычисляем новый бакет и проверяем там. Повторяем, пока не дойдем до нужного ключа или пустой ячейки
В каждом бакете максимум одно значение, которое записывается в сам бакет. Все лежит в памяти рядышком, вставка и поиск работают космически быстро🚀
Из-за того, что данные лежат в самом массиве, полученную структуру так же называют close hashing.
🤔 Получается, текущий HashMap - не самый быстрый вариант?
Верно, тк в бакете хранится ссылка на элемент или цепочку элементов, приходится прыгать по ссылкам в куче на несколько гигов.
Но благодаря ссылкам можно работать с объектами произвольных размеров, легко заменять и удалять элементы. Метод цепочек - более простой и универсальный вариант, поэтому именно он используется в готовых хэш-таблицах в java, go и c++.
Метод открытой адресации побеждает лишь в определенных кейсах и сложнее в реализации, поэтому не входит в стандартные библиотеки.
🤔 Можно ли реализовать хэш-таблицу с методом открытой адресации в java?
Можно, но только для примитивов. Ссылочные типы здесь не подойдут. Нужно, чтобы данные лежали в самой структуре.
Но в будущем ситуация изменится! В java вовсю идёт разработка value types — объектов с полями и методами, работа с которыми идёт как с примитивом.
Это позволит хранить данные рядом, пользоваться локальностью, чаще задействовать кэши процессора. Даст зелёный свет многим алгоритмам и структурам данных, в том числе хэш-таблице с открытой адресацией.
Ответ на вопрос перед постом: HashMap использует открытое хэширование. Ставь ❤️, если выбирал ответ сердцем, и 👍 если выбирал умом