Реализация HashMap Java 8
Согласно следующему ссылочному документу: реализация Java HashMap
Я запутался с реализацией HashMap (или, скорее, улучшение в HashMap). Мои запросы:
во-первых
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
Почему и как используются эти константы? Я хочу несколько четких примеров для этого. Как они достигают прироста производительности с этим?
во-вторых
Если вы видите исходный код HashMap в JDK вы найдете следующий статический внутренний класс:
static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
HashMap.TreeNode<K, V> parent;
HashMap.TreeNode<K, V> left;
HashMap.TreeNode<K, V> right;
HashMap.TreeNode<K, V> prev;
boolean red;
TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
super(arg0, arg1, arg2, arg3);
}
final HashMap.TreeNode<K, V> root() {
HashMap.TreeNode arg0 = this;
while (true) {
HashMap.TreeNode arg1 = arg0.parent;
if (arg0.parent == null) {
return arg0;
}
arg0 = arg1;
}
}
//...
}
Как это используется? Я просто хочу объяснение алгоритма.
5 ответов
HashMap содержит определенное количество ведер Оно использует hashCode чтобы определить, в какое ведро положить их. Для простоты представьте это как модуль.
Если наш хэш-код 123456 и у нас есть 4 сегмента, 123456 % 4 = 0 поэтому товар идет в первое ведро, ведро 1.
Если наша функция хеширования хороша, она обеспечит равномерное распределение, поэтому все сегменты будут использоваться примерно одинаково. В этом случае корзина использует связанный список для хранения значений.
Но вы не можете полагаться на людей для реализации хороших хэш-функций. Люди часто пишут плохие хэш-функции, что приводит к неравномерному распределению.
Чем меньше это распределение, тем дальше мы переходим от операций O(1) и тем ближе мы продвигаемся к операциям O(n).
Реализация Hashmap пытается смягчить это путем организации некоторых блоков в деревья, а не связанных списков, если они становятся слишком большими. Это то, что TREEIFY_THRESHOLD = 8 для. Если в ведре содержится более восьми предметов, оно должно стать деревом.
Это дерево красно-чёрное. Сначала сортируется по хеш-коду. Если хеш-коды совпадают, он использует compareTo метод Comparable если объекты реализуют этот интерфейс, в противном случае идентификационный хеш-код.
Если записи удаляются с карты, количество записей в корзине может уменьшиться, так что эта древовидная структура больше не нужна. Вот что UNTREEIFY_THRESHOLD = 6 для. Если количество элементов в корзине падает ниже шести, мы могли бы также вернуться к использованию связанного списка.
Наконец, есть MIN_TREEIFY_CAPACITY = 64,
Когда хэш-карта увеличивается в размере, она автоматически изменяет свой размер, чтобы иметь больше блоков. Если у нас есть небольшая хэш-карта, вероятность того, что мы получим очень полные сегменты, достаточно высока, потому что у нас нет такого большого количества различных блоков, в которые можно помещать вещи. Гораздо лучше иметь большую хэш-карту с большим количеством менее заполненных сегментов. Эта константа в основном говорит о том, что не следует начинать создавать сегменты в деревьях, если наша хэш-карта очень мала - вместо этого ее размер должен быть больше.
Чтобы ответить на ваш вопрос об увеличении производительности, эти улучшения были добавлены для улучшения наихудшего случая. Я только размышляю, но вы, вероятно, увидите только заметное улучшение производительности из-за этих оптимизаций, если ваш hashCode Функция была не очень хорошей.
Изображения мои (спасибо MSPaint). Используйте их по своему усмотрению.
Проще говоря (насколько я мог бы проще) + еще несколько деталей.
Эти свойства зависят от множества внутренних вещей, которые было бы очень круто понять - прежде чем перейти к ним напрямую.
TREEIFY_THRESHOLD -> когда одна корзина достигает этого (и общее количество превышает MIN_TREEIFY_CAPACITY), он превращается в идеально сбалансированный узел красного / черного дерева. Зачем? Из-за скорости поиска. Подумайте об этом по-другому:
для поиска записи в корзине / корзине с записями Integer.MAX_VALUE потребуется не более 32 шагов.
Немного вступления к следующей теме. Почему количество бункеров / ведер всегда равно двум? По крайней мере, две причины: быстрее, чем операция по модулю и по отрицательным числам по модулю. И вы не можете поместить Entry в "отрицательное" ведро:
int arrayIndex = hashCode % buckets; // will be negative
buckets[arrayIndex] = Entry; // obviously will fail
Вместо этого вместо модуля используется хороший трюк:
(n - 1) & hash // n is the number of bins, hash - is the hash function of the key
Это семантически то же самое, что и операция по модулю. Это сохранит младшие биты. Это имеет интересное следствие, когда вы делаете:
Map<String, String> map = new HashMap<>();
В приведенном выше случае решение о том, куда идет запись, принимается только на основе последних 4 битов вашего хеш-кода.
Это где умножение ведер вступает в игру. При определенных условиях (объяснение в деталях потребует много времени), объемы удваиваются. Зачем? Когда ведра удваиваются в размере, в игру вступает еще один бит.
Итак, у вас есть 16 сегментов - последние 4 бита хеш-кода определяют, куда идет запись. Вы удваиваете сегменты: 32 сегмента - 5 последних битов определяют, куда пойдет запись.
Как таковой этот процесс называется повторным хэшированием. Это может стать медленным. То есть (для людей, которым это небезразлично), так как HashMap "шутит" как: быстро, быстро, быстро, slooow. Есть и другие реализации - поиск без паузы hashmap...
Теперь UNTREEIFY_THRESHOLD вступает в игру после повторного хеширования. В этот момент некоторые записи могут перемещаться из этих корзин в другие (они добавляют еще один бит к (n-1)&hash вычисление - и как таковое может перейти к другим сегментам), и это может достичь UNTREEIFY_THRESHOLD, На этом этапе не стоит держать корзину как red-black tree node, но как LinkedList вместо этого, как
entry.next.next....
MIN_TREEIFY_CAPACITY - это минимальное количество сегментов до того, как определенный сегмент трансформируется в дерево.
TreeNode это альтернативный способ хранения записей, которые принадлежат к одной корзине HashMap, В более старых реализациях записи корзины были сохранены в связанном списке. В Java 8, если количество записей в корзине превысило пороговое значение (TREEIFY_THRESHOLD), они хранятся в древовидной структуре вместо исходного связанного списка. Это оптимизация.
Из реализации:
/*
* Implementation notes.
*
* This map usually acts as a binned (bucketed) hash table, but
* when bins get too large, they are transformed into bins of
* TreeNodes, each structured similarly to those in
* java.util.TreeMap. Most methods try to use normal bins, but
* relay to TreeNode methods when applicable (simply by checking
* instanceof a node). Bins of TreeNodes may be traversed and
* used like any others, but additionally support faster lookup
* when overpopulated. However, since the vast majority of bins in
* normal use are not overpopulated, checking for existence of
* tree bins may be delayed in the course of table methods.
Вам нужно визуализировать это: скажем, есть ключ класса с только переопределенной функцией hashCode(), чтобы всегда возвращать одно и то же значение
public class Key implements Comparable<Key>{
private String name;
public Key (String name){
this.name = name;
}
@Override
public int hashCode(){
return 1;
}
public String keyName(){
return this.name;
}
public int compareTo(Key key){
//returns a +ve or -ve integer
}
}
и затем где-то еще, я вставляю 9 записей в HashMap со всеми ключами, являющимися экземплярами этого класса. например
Map<Key, String> map = new HashMap<>();
Key key1 = new Key("key1");
map.put(key1, "one");
Key key2 = new Key("key2");
map.put(key2, "two");
Key key3 = new Key("key3");
map.put(key3, "three");
Key key4 = new Key("key4");
map.put(key4, "four");
Key key5 = new Key("key5");
map.put(key5, "five");
Key key6 = new Key("key6");
map.put(key6, "six");
Key key7 = new Key("key7");
map.put(key7, "seven");
Key key8 = new Key("key8");
map.put(key8, "eight");
//Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry
Key key9 = new Key("key9");
map.put(key9, "nine");
threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g.
key1
/ \
key2 key3
/ \ / \
Обход дерева происходит быстрее {O(log n)}, чем LinkedList {O(n)}, и с ростом n разница становится более существенной.
Изменение в реализации HashMap было добавлено с JEP-180. Целью было:
Улучшите производительность java.util.HashMap в условиях высокого хеш-коллизии, используя сбалансированные деревья, а не связанные списки для хранения записей карты. Реализуйте то же улучшение в классе LinkedHashMap
Однако чистая производительность - не единственное преимущество. Это также предотвратит атаку HashDoS, если хеш-карта используется для хранения ввода пользователя, поскольку красно-черное дерево, которое используется для хранения данных в корзине, имеет наихудшую сложность вставки в O(log n). Дерево используется после выполнения определенных критериев - см . Ответ Евгения.
Чтобы понять внутреннюю реализацию hashmap, вам нужно понять хеширование. Хеширование в простейшем виде - это способ присвоения уникального кода любой переменной / объекту после применения любой формулы / алгоритма к его свойствам.
Истинная хеш-функция должна следовать этому правилу -
"Хэш-функция должна возвращать один и тот же хэш-код каждый раз, когда функция применяется к одинаковым или равным объектам. Другими словами, два равных объекта должны последовательно создавать один и тот же хеш-код ".