UnifiedMap: как это работает?
Eclipse Collections поставляется с собственными реализациями List, Set и Map. Он также имеет дополнительные структуры данных, такие как Multimap, Bag и целую иерархию примитивных коллекций. В этом блоге мы заглянем под капот UnifiedMap.
UnifiedMap
UnifiedMap - это реализация Map для коллекций Eclipse, которая реализована совсем не так, как JDK HashMap.
java.util.HashMap поддерживается таблицей объектов Entry. Реализация Entry в HashMap имеет hashcode, key, value, next в качестве членов, HashMap по существу кэширует хэш-код ключей.
UnifiedMap поддерживается массивом, в котором ключи и значения занимают альтернативные места в массиве: protected transient Object[] table. Структура плоского массива хранит там только ключи и значения, создавая более компактную реализацию Map с уменьшенным объемом памяти. Дополнительным преимуществом наличия ключей и значений в последовательных слотах является улучшенная локальность кеша.
Коллизии в основном массиве обрабатываются путем помещения специального объекта с именем CHAINED_KEY в ключевой слот. Слот значений CHAINED_KEY (слот после CHAINED_KEY слота) содержит другой массив Object[], аналогичный основному массиву с именем CHAINED_OBJECT, с ключами и значениями в альтернативных слотах.
Поиск в UnifiedMap использует стандартный алгоритм индекса хэш-кода, чтобы найти местоположение ключа в массиве. Если ключ не CHAINED_KEY, то следующий слот содержит значение. Если ключ является CHAINED_KEY, тогда CHAINED_OBJECT оценивается линейно, чтобы найти требуемый ключ, и следующий слот в CHAINED_OBJECT содержит значение.
Поскольку UnifiedMap не кэширует хэш-код, для каждого поиска необходимо вычислять хэш-код. Таким образом, производительность UnifiedMap напрямую зависит от реализации хэш-кода ключа.
Ниже приведены несколько сравнений памяти и производительности между JDK 1.8 HashMap и Eclipse Collections 9.0.0 UnifiedMap.
Объем памяти (чем меньше число, тем лучше)
Тесты производительности (чем больше число, тем лучше)
Исходный код для тестов памяти и тестов производительности доступен на GitHub.
Резюме. Коллекции Eclipse UnifiedMap занимает примерно на 50% меньше памяти по сравнению с JDK HashMap, но это оказывает незначительное влияние на производительность.
Коллекции Eclipse открыты для взносов. Если вам нравится, пометьте его.
