Волею судьбы сейчас я плотно занимаюсь Java, вместо горячо любимого мною Golang. Ну и попутно сравниваю как решены те ил иные задачи в Golang и Java. Сегодня речь пойдет про хэш таблицы. С точки зрения алгоритмов HashMap и map[] практически идентичны - hash table + разрешение коллизий через цепочки. Но это теоретически, а с практической точки зрения реализация значит ничуть не меньше чем выбранные алгоритмы. Итак начнем: исходники
HashMap я взял отсюда, а
исходники map[] отсюда.
Golang map[]
1. Общее устройство. Данные хранятся в блоках по 8 элементов. Младшие 3 бита хэша используются для идентификации key-value пары внутри блока. Хэш таблица представляет собой массив из таких восьми-элементных блоков. Первый блок из восьми элементов всегда располагается непосредственно в хэш таблице. У этого есть важное следствие - Go map[] чувствует себя очень комфортно при количестве коллизий меньше 8 на элемент хэш таблицы. С учетом того что удлинение цепочки коллизий также происходит блоками по 8 элементов, то go map[] вообще весьма устойчива к росту числа коллизий. Сам блок представляет из себя структуру из 8 однобайтовых значений для хранения младших битов хэшей, затем 8 ключей и 8 значений. В зависимости от типа ключей и значений они могут хранится непосредственно в этой структуре данных либо там могут хранится только указатели на них.
2. Хэш функция - Go использует в качестве хэш функции встроенную в большинство процессоров функцию AES шифрование(инструкция AESENC).
3. Начальный размер хэш таблицы:
3.1 Для пустого map[] хэш таблица вообще не создается,
3.2 Если при инициализации map capacity указана меньше 8 - то хэш таблица также не создается.
3.3 Если capacity указанная при создании map[] больше или равно 8, то размер таблицы рассчитывается как ближайшая степень двойки для которой выполняется условие (1 << B) * loadFactor > count, где B - степень двойки, loadFactor - магическое число равное 6.5, count - map[] capacity указанная при инициализации.
4. Расширение хэш таблицы. При расширении хэш таблицы учитывается два фактора:
a. Количество элементов в map[], при этом логика аналогична описанной выше (как при инициализации map[])
b. Количество цепочек длинной больше 8 элементов. Как я написал выше Golang map[] оптимизирован для работы с цепочками длинной менее 8 элементов, поэтому реализация заточена на то чтобы сохранить длинну цепочки от одного до двух элементов. Так как счетчик "переполнений"(цепочек длинной более одного элемента) это uint16, то сама логика различается для map размером хэш таблицы меньше (1 << 16) и больше этого значения.
если размер таблицы меньше чем (1 << 16) то хэш таблица расширяется в случае если количество цепочек с переполнением становится больше чем (1 << B) (где B - степень двойки, размер хэш таблицы).
если размер таблицы больше чем (1 << 16) то логика остается той же, но расчет количества "переполнений" становится приблизительным.
Если принять во внимание то что в одном звене цепочки может находится до 8 элементов - то расширение хэш таблицы случается всегда по первому условию ( количество значений больше чем 6.5 * (1 << B)).
Java HashMap
1. Общее устройство HashMap предельно простое. Это классический hash map как он описан в учебниках по программированию. Хэш таблица представляет собой массив Entry, в каждом Entry ключ, значение и указатель на следующий Entry. Никаких хитростей и попыток оптимизировать что-то. Прям скуку смертная да и только.
2. Хэш функция - как я понял вызывается встроенный в объект метод hash() к которому сверху применяется простейшая XOR функция:
3. С начальным размером таблицы все тоже очень грустно - оно всегда равно 16 элементам. Либо ближайшей степени двойки большей чем требуемая capacity.
4. Расширение хэш таблицы реализовано также крайне просто - есть loadFactor, равный 0.75. Как только количество элементов в HashMap превышает текущее capacity на 75% ее размер увеличивается в двое. Расширение HashMap также происходит предельно просто - выделяется новая хэш таблица, в цикле проходимся по старой таблице и перекладываем ее элементы в новую таблицу.
Вывод
В общем признаться честно - java меня разочаровала. Единственное достоинство реализации HashMap - это простота реализации. Все просто и понятно. Негде там ошибиться.
По сравнению с этим реализация map[] - это вершина инженерной мысли. Как Porshe 911 по сравнению со старым фордом. В map[] экономится каждый бит. Многих оптимизаций без хорошего понимания ассеблера просто не понять. Количество аллоцируемых объектов, ссылок в Golang map[] на порядок меньше чем в HashMap, а это значит что и гораздо меньше работы для сборщика мусора. Также гораздо выше memory locality. В Golang даже floating point арифметику лишний раз стараются не использовать, заменяя сдвигами и другими целочисленными операциями. В общем мне стало немного понятнее почему софт на Java так тормозит.
