HashMap: альтернативная реализация

Если хэши, бакеты, контракт 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 использует открытое хэширование. Ставь ❤️, если выбирал ответ сердцем, и 👍 если выбирал умом