Согласно следующему документу ссылки: Реализация 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;
}
}
//...
}
Как это используется? Мне просто нужно объяснение алгоритма .
java
dictionary
java-8
hashmap
Хаснайн Али Бора
источник
источник
String, имеют гораздо большее пространство значений, чемintхэш-код, поэтому столкновения неизбежны. Теперь это зависит от фактических значений, таких как фактическиеStrings, которые вы вводите в карту, получаете ли вы равномерное распределение или нет. Плохое распределение может быть результатом просто неудачи.java.lang.Stringимеет детерминированный, не криптографическийhashCode, поэтому злоумышленники могут тривиально создавать отдельные строки с конфликтующими хэш-кодами. До этой оптимизации это могло ухудшить операции HashMap до O (n) -время, теперь оно просто снижает их до O (log (n)).if the objects implement that interface, else the identity hash code.я искал эту еще часть.MIN_TREEIFY_CAPACITY. Означает ли это: «Как только мы вставляем ключ, который должен быть хэширован, в корзину, уже содержащую 8 (TREEIFY_THRESHOLD) ключей, и если в ней уже есть 64 (MIN_TREEIFY_CAPACITY) ключаHashMap, связанный список этой корзины преобразуется в сбалансированное дерево».Проще говоря (насколько я мог проще) + еще несколько деталей.
Эти свойства зависят от множества внутренних вещей, которые было бы очень здорово понять, прежде чем переходить к ним напрямую.
TREEIFY_THRESHOLD -> когда отдельная корзина достигает этого значения (а общее число превышает
MIN_TREEIFY_CAPACITY), оно преобразуется в идеально сбалансированный красный / черный узел дерева . Зачем? Из-за скорости поиска. Подумайте об этом по-другому:Некоторое вступление к следующей теме. Почему количество бункеров / ковшей всегда равно двойке ? По крайней мере, две причины: быстрее, чем операция по модулю, и по модулю на отрицательные числа будут отрицательными. И вы не можете поместить запись в "отрицательную" корзину:
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<>();Вот тут-то и играет роль умножение ведер. При определенных условиях (на объяснение точных деталей потребуется много времени ), ведра увеличиваются вдвое. Зачем? Когда ведра увеличиваются вдвое, в игру вступает еще один момент .
По сути, этот процесс называется повторным хешированием. Это может замедлиться. Это (для людей, которым не все равно), поскольку HashMap «шутят» как: быстро, быстро, быстро, медленно . Есть и другие реализации - поиск хеш-карты без пауз ...
Теперь UNTREEIFY_THRESHOLD вступает в игру после повторного хеширования. В этот момент некоторые записи могут перемещаться из этой корзины
(n-1)&hashв другую (они добавляют еще один бит к вычислению - и, таким образом, могут перемещаться в другие корзины), и он может достичь этогоUNTREEIFY_THRESHOLD. На этом этапе неred-black tree nodeстоит хранить корзину как , а какLinkedListвместо этого, например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.источник
TREEIFY_THRESHOLDИ, общее количество ящиков будет не менееMIN_TREEIFY_CAPACITY. Я попытался осветить это в своем ответе ...Вам нужно будет визуализировать это: скажем, есть ключ класса с переопределенной только функцией 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 разница становится более значительной.
источник
compareTofromComparable.identityHashCodeэто еще один механизм, который он использует.Keyне реализуемComparable,identityHashCodeбудем использовать :)Изменение в реализации HashMap было добавлено в JEP-180 . Целью было:
Однако чистая производительность - не единственное преимущество. Это также предотвратит атаку HashDoS , если для хранения пользовательского ввода используется хеш-карта, потому что красно-черное дерево , которое используется для хранения данных в корзине, имеет сложность вставки в худшем случае в O (log n). Дерево используется после выполнения определенных критериев - см . Ответ Евгения .
источник
Чтобы понять внутреннюю реализацию hashmap, вам нужно понять хеширование. Хеширование в простейшей форме - это способ присвоения уникального кода любой переменной / объекту после применения любой формулы / алгоритма к его свойствам.
Настоящая хеш-функция должна следовать этому правилу -
«Хеш-функция должна возвращать один и тот же хэш-код каждый раз, когда функция применяется к одним и тем же или равным объектам. Другими словами, два одинаковых объекта должны последовательно создавать один и тот же хэш-код ».
источник