Внедрение HashMap Java 8

Ответ 1

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 была не очень хорошей.

Ответ 2

Проще говоря (насколько я мог бы проще) + еще несколько деталей.

Эти свойства зависят от множества внутренних вещей, которые было бы очень здорово понять, прежде чем перейти к ним напрямую.

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 - это минимальное количество сегментов до того, как определенный сегмент трансформируется в дерево.

Ответ 3

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.

Ответ 4

Вам нужно будет визуализировать его: скажем, есть ключ класса с переопределенной функцией 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 разница становится более значимой.

Ответ 5

Изменение в реализации HashMap было добавлено с помощью JEP-180. Цель заключалась в следующем:

Повысьте производительность java.util.HashMap в условиях высокого хеш-столкновения, используя сбалансированные деревья, а не связанные списки для хранения записей в карте. Внедрите те же улучшения в классе LinkedHashMap

Однако чистая производительность - не единственный выигрыш. Он также будет предотвращать атаку HashDoS, если хэш-карта используется для хранения пользовательского ввода, потому что красно-черное дерево, используемое для хранения данных в ковше, имеет худшую сложность ввода в O (log n). Дерево используется после выполнения определенных критериев - см. ответ Евгения.

Ответ 6

Чтобы понять внутреннюю реализацию hashmap, вам нужно понять хеширование. Хеширование в простейшем виде - это способ присвоения уникального кода любой переменной/объекту после применения любой формулы/алгоритма к его свойствам.

Истинная хеш-функция должна следовать этому правилу -

"Хэш-функция должна возвращать один и тот же хэш-код каждый раз, когда функция применяется к одинаковым или равным объектам. Другими словами, два равных объекта должны последовательно создавать один и тот же хэш-код".