После прочтения этой HashMap не проблема поспорить с интервьюером.

Java задняя часть

Обзор хэш-карты

Если у вас нет времени на изучение этой статьи, вы можете непосредственно прочитать обзор HashMap, который даст вам общее представление о HashMap..

HashMap — это реализация интерфейса Map. HashMap допускает использование пустых пар ключ-значение. HashMap считается расширенной версией Hashtable. . HashMap неупорядочен, потому что HashMap не может гарантировать порядок пар ключ-значение, хранящихся внутри.

Базовая структура данных HashMap представляет собой набор массивов + связанные списки, Массивы также вызываются в HashMap.桶(bucket). Время, необходимое для обхода HashMap, равно количеству сегментов экземпляра HashMap + количество (сопоставление ключ-значение). Поэтому не устанавливайте слишком высокую начальную мощность или слишком низкий коэффициент нагрузки, если важно пересечение элементов.

Экземпляр HashMap имеет два очень важных фактора: начальную емкость и коэффициент загрузки. Начальная емкость относится к количеству сегментов хеш-таблицы, а коэффициент загрузки является стандартом для измерения степени заполнения хэш-таблицы. и текущая емкость превышены, хеш-таблица выполнит операцию повторного хеширования, и внутренняя структура данных будет перестроена.

Обратите внимание, что HashMap не является потокобезопасным.Если несколько потоков влияют на HashMap одновременно и хотя бы один поток изменяет структуру HashMap, то HashMap необходимо синхронизировать. можно использоватьCollections.synchronizedMap(new HashMap)для создания потокобезопасной карты.

HashMap приведет к тому, что внешний метод удаления в дополнение к самому итератору вызовет отказоустойчивый механизм, поэтому попробуйте использовать собственный метод удаления итератора. Выдает, если структура карты изменяется во время создания итератораConcurrentModificationExceptionаномальный.

Давайте поговорим о деталях HashMap. Давайте начнем с вопросов интервью для анализа HashMap.

Разница между HashMap и HashTable

Мы представили HashMap выше, теперь давайте представим HashTable

Та же точка

И HashMap, и HashTable реализованы на основе хеш-таблиц, и каждый элемент внутриkey-valueДля пар ключ-значение и HashMap, и HashTable реализуют интерфейсы Map, Cloneable и Serializable.

разница

  • Родитель отличается: Hashmap наследуетAbstractMapкласс, а HashTable наследуетDictionaryсвоего рода

  • Нулевые значения бывают разными: HashMap допускает пустые значения ключа и значения, HashTable не допускает пустых значений ключа и значения. HashMap обрабатывает нулевые ключи как обычные ключи. Повторяющиеся нулевые ключи не допускаются.

  • Потокобезопасность: HashMap не является потокобезопасным. Если несколько внешних операций изменяют структуру данных HashMap одновременно, например, добавляют или удаляют, необходимо выполнять операции синхронизации. Только изменение ключа или значения не является операцией по изменению структура данных. При желании создайте поточно-ориентированную карту, такую ​​какCollections.synchronizedMapилиConcurrentHashMap. А HashTable сама по себе является потокобезопасным контейнером.

  • Производительность: хотя и HashMap, и HashTable основаны на односвязном списке, HashMap может обеспечить производительность с постоянным временем для операций ввода или получения; в то время как операции ввода и получения HashTable добавляются.synchronizedЗаблокировано, поэтому эффективность очень низкая.

  • Начальная емкость другая: начальная длина HashTable равна 11, а затем каждая емкость расширения становится предыдущей 2n+1 (n — предыдущая длина)

    Начальная длина HashMap равна 16, а затем каждое расширение становится вдвое больше исходной длины. При создании, если задано начальное значение емкости, HashTable будет напрямую использовать заданный вами размер, а HashMap расширит его до степени двойки.

Разница между HashMap и HashSet

Часто спрашивают о разнице между HashMap и HashSet.

HashSet наследует интерфейс AbstractSet и реализует интерфейсы Set, Cloneable и java.io.Serializable. HashSet не допускает дублирования значений в коллекции. Нижний уровень HashSet на самом деле является HashMap, и все операции с HashSet на самом деле являются операциями с HashMap. Таким образом, HashSet также не гарантирует порядок коллекции.

Базовая структура HashMap

Чтобы понять класс, мы должны сначала понять структуру класса, сначала посмотреть на структуру HashMap:

Три основных класса (интерфейса):HashMap,AbstractMapиMapТеперь о HashMap. Мы кратко представили его в обзоре выше, давайте представим AbstractMap.

Класс AbstractMap

Этот абстрактный класс является базовой реализацией интерфейса Map, чтобы минимизировать рабочую нагрузку на реализующие классы. Чтобы реализовать немодифицируемую карту, программисту нужно только расширить этот класс и предоставить реализацию метода entrySet. Он вернет сегмент набора карт. Как правило, возвращаемая коллекция будет реализована поверх AbstractSet. Набор не должен поддерживать методы добавления или удаления, а его итератор не должен поддерживать метод удаления.

Чтобы реализовать модифицируемую карту, программист должен дополнительно переопределить метод вставления этого класса (в противном случае будет брошен неподдерживаться, и итератор, возвращенный AndetS.iterator (), должен реализовывать метод удаления ().

Интерфейс карты

Интерфейс карты определяет стандарт для пар ключ-значение. Объект поддерживает хранение ключ-значение. Карта не может содержать повторяющиеся ключи, каждый ключ отображает не более одного значения. Этот интерфейс заменяет класс Dictionary, который является абстрактным классом, а не интерфейсом.

Интерфейс Map предоставляет три конструктора коллекций, которые позволяют обрабатывать содержимое карты как набор ключей, набор значений или набор карт ключ-значение. Порядок карты определяется как порядок, в котором итератор над отображаемой картой коллекцией возвращает свои элементы. Некоторые реализации карт, например класс TreeMap, гарантируют порядок карт, другие, например HashMap, — нет.

Важные внутренние классы и интерфейсы

Интерфейс узла

Узел Node используется для хранения экземпляра HashMap, который реализуетMap.EntryИнтерфейс, давайте сначала посмотрим на определение внутреннего интерфейса Entry interface в Map

Map.Entry

// 一个map 的entry 链，这个Map.entrySet()方法返回一个集合的视图，包含类中的元素，
// 这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在
// 迭代期间有效。
interface Entry<K,V> {
  K getKey();
  V getValue();
  V setValue(V value);
  boolean equals(Object o);
  int hashCode();
}

Узел узла будет хранить четыре атрибута: хеш-значение, ключ, значение и ссылку на следующий узел узла.

 // hash值
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个Node节点的Node类型
Node<K,V> next;

Поскольку Map.Entry связан цепочками входа, узлы Node также являются цепочками входа. При построении нового экземпляра HashMap эти четыре значения атрибута делятся на входящие

Node(int hash, K key, V value, Node<K,V> next) {
  this.hash = hash;
  this.key = key;
  this.value = value;
  this.next = next;
}

Реализует интерфейс Map.Entry, поэтому методы должны быть реализованы, поэтому узел Node также включает пять вышеуказанных методов.

Внутренний класс KeySet

Класс keySet наследуется от абстрактного класса AbstractSet, который определяется HashMap.keyset()метод создания экземпляра KeySet, предназначенный для работы с ключами в HashMap, см. пример кода

на фото1, 2, 3Эти три ключа помещаются в HashMap, а затем лямбда-выражение используется для перебора значений ключей.Вы можете видеть, что map.keySet() фактически возвращает интерфейс Set, а KeySet() определен в интерфейсе Map, но Он реализован HashMap, просто посмотрите исходный код, чтобы понять

// 返回一个set视图，这个视图中包含了map中的key。
public Set<K> keySet() {
  // // keySet 指向的是 AbstractMap 中的 keyset
  Set<K> ks = keySet;
  if (ks == null) {
    // 如果 ks 为空，就创建一个 KeySet 对象
    // 并对 ks 赋值。
    ks = new KeySet();
    keySet = ks;
  }
  return ks;
}

Таким образом, класс KeySet работает с ключом на карте:

Внутренний класс значений

Создание класса Values ​​на самом деле очень похоже на класс KeySet, но KeySet предназначен для работы с ключами в Map, а Values ​​предназначен для работы с ключами в Map.key-valueИспользуйте значение value в паре ключ-значение, взгляните на пример кода:

Прокрутите значения на карте и посмотрите, что в итоге создаст метод values():

public Collection<V> values() {
  // values 其实是 AbstractMap 中的 values
  Collection<V> vs = values;
  if (vs == null) {
    vs = new Values();
    values = vs;
  }
  return vs;
}

Все значения фактически хранятся в AbstractMap, а класс Values ​​фактически реализует интерфейс Values ​​в Map.Посмотрим, какие методы доступны для операций над значениями.

По сути, это похоже на работу ключа

Внутренний класс EntrySet

Как было сказано выше, в HashMap есть операции над ключом и значением, на самом деле есть еще операции над ключом и значением.key-valueВнутренний класс, который работает с парами ключ-значение, называется EntrySet. Давайте посмотрим на процесс создания EntrySet:

Нажмите на entrySet(), и вы обнаружите, что этот метод также определен в интерфейсе Map, который переписан HashMap.

// 返回一个 set 视图，此视图包含了 map 中的key-value 键值对
public Set<Map.Entry<K,V>> entrySet() {
  Set<Map.Entry<K,V>> es;
  return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

Если es пуст, создается новый экземпляр EntrySet. EntrySet в основном включает методы для сопоставления пар ключ-значение, как показано ниже.

Базовая структура HashMap 1.7

В JDK1.7 HashMap принимает реализацию битового ведра + связанный список, то есть связанный список используется для разрешения конфликта, а связанный список с одним и тем же хеш-значением хранится в массиве. Однако, когда в корзине много элементов, то есть когда много элементов с одинаковым значением хеш-функции, эффективность последовательного поиска по значению ключа низка. Его структура данных выглядит следующим образом

Основная структура данных представляет собой массив ввода HASHMAP, запись Hashmap - это базовый блок, каждая запись содержит пары клавишных значений.

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

И каждая запись содержитhash, key ,valueсвойство, которое является внутренним классом HashMap

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;
  
  Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
  }
  ...
}

Итак, общая структура HashMap выглядит следующим образом

Базовая структура HashMap 1.8

По сравнению с JDK 1.7, в версии 1.8 внесены некоторые изменения в базовую структуру. Когда количество элементов в каждой корзине больше 8, она будет преобразована в красно-черное дерево. Цель — оптимизировать эффективность запросов. JDK 1.8 переписываетresize()метод.

Важные свойства HashMap

начальная мощность

Начальная емкость HashMap по умолчанию определяется какDEFAULT_INITIAL_CAPACITYуправление недвижимостью.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

Начальная емкость HashMaap по умолчанию: 1 左移операции, она эквивалентна

Максимальная емкость

Максимальная емкость HashMap составляет

static final int MAXIMUM_CAPACITY = 1 << 30;

Здесь есть вопрос? Int занимает четыре байта.Говорят, что максимальная емкость должна быть смещена влево на 31 бит.Почему максимальная емкость HashMap сдвинута влево на 30 бит? Потому что в численных вычислениях старший бит также является самым левым битом.位Это означает, что знак 0 -> положительное число, 1 -> отрицательное число, емкость не может быть отрицательной, поэтому старший бит HashMap можно сдвинуть только в степени 2 ^ 30.

Коэффициент нагрузки по умолчанию

Коэффициент загрузки по умолчанию для HashMap равен

static final float DEFAULT_LOAD_FACTOR = 0.75f;

тип float, поэтому используйте.fКоэффициент загрузки связан с механизмом расширения мощностей, который кратко упоминается здесь и будет подробно обсуждаться позже. Принцип механизма расширения заключается в том, что когда количество, хранящееся в HashMap > емкость HashMap * коэффициент загрузки, емкость HashMap будет удвоена.

Первое расширение HashMap выполняется, когда DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12.

Порог обработки

Порог дерева для HashMap

static final int TREEIFY_THRESHOLD = 8;

При добавлении элементов, когда количество элементов, хранящихся в ведре, превышает 8, оно будет автоматически преобразовано в красно-черное дерево (функция JDK1.8).

порог связанного списка

Порог связанного списка HashMap равен

static final int UNTREEIFY_THRESHOLD = 6;

При удалении элементов, если количество элементов, хранящихся в корзине, меньше 6, она будет автоматически преобразована в связанный список.

Порог расширения

static final int MIN_TREEIFY_CAPACITY = 64;

Это значение указывает, что когда емкость массива сегментов меньше этого значения, приоритет отдается расширению, а не дереву.

массив узлов

Массив узлов в HashMap — это массив Entry, представляющий HashMap.массив + связанный списокМассивы в структурах данных.

transient Node<K,V>[] table;

Массивы узлов инициализируются при первом использовании и при необходимостиresize, длина массива после изменения размера удваивается.

Количество пар ключ-значение

В HashMap используйтеsizeдля представления количества пар ключ-значение в HashMap.

Правки

В HashMap используйтеmodCountЧтобы представить количество модификаций, он в основном используется для механизма «быстрый сбой-сбой-быстро» при одновременном изменении HashMap.

Порог расширения

В HashMap используйтеthresholdУказывает порог расширения, то есть значение начальной мощности * коэффициент загрузки.

порог включает проблему порога расширения, которая вызванаtableSizeForисходный код решения. Давайте посмотрим на его исходный код, а затем объясним

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

В коде участвует оператор|=, это означает побитовое или, что это значит? ты должен знатьа+=б означает а=а+б, то **аналогично: a |= b равно a = a|b**, то есть обе части преобразуются в двоичные для выполнения операции И. Как показано ниже

Мы использовали относительно большое число для расширения емкости выше.Из приведенного выше рисунка видно, что после серии операций ИЛИ результат массива мощности 2 ^ 29 будет рассчитан как мощность 2 ^ 30.

Следовательно, длина расширенного массива в два раза больше исходного размера.

коэффициент нагрузки

loadFactorПредставляет коэффициент загрузки, который представляет плотность в HashMap.

Конструктор HashMap

В исходном коде HashMap есть четыре типа конструкторов, которые будут представлены отдельно.

  • с участием初始容量 initialCapacityи负载因子 loadFactorконструктор
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  // 扩容的阈值
  this.threshold = tableSizeFor(initialCapacity);
}

Начальная емкость не может быть отрицательной, поэтому при передаче начальной емкости IllegalArgumentExceptionаномальный. Если входящая начальная емкость > максимальной емкости, начальная емкость = максимальная емкость. Коэффициент загрузки также не может быть меньше 0 . Затем расширяйте массив, этот механизм расширения тоже очень важен, мы обсудим его позже.

  • Конструктор только с начальной емкостью
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

Наконец, будет вызван вышеупомянутый конструктор, но этот коэффициент загрузки по умолчанию является коэффициентом загрузки по умолчанию для HashMap, который равен0.75f

  • конструктор без параметров
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
}

Коэффициент нагрузки по умолчанию также равен 0,75f.

  • Конструктор с картой
public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false);
}

Конструктор с Map будет напрямую группировать внешние элементы в HashMap.

Расскажите обо всем процессе установки HashMap.

Я помню, как через год после выпуска я поехал в Пекин на собеседование, и когда меня спросили о процессе размещения HashMap, я заколебался и не смог ответить. Сравнение с JDK 1.8 и более поздними версиями. Сначала опубликуйте весь код, а затем анализируйте его построчно.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 如果table 为null 或者没有为 table 分配内存，就resize一次
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  // 如果不为空
  else {
    Node<K,V> e; K k;
    // 计算表中的这个真正的哈希值与要插入的key.hash相比
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 若不同的话，并且当前节点已经在 TreeNode 上了
    else if (p instanceof TreeNode)
      // 采用红黑树存储方式
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==null
    else {
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          // 在表尾插入
          p.next = newNode(hash, key, value, null);
          // 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 如果找到了同 hash、key 的节点，那么直接退出循环
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 更新 p 指向下一节点
        p = e;
      }
    }
    // map中含有旧值，返回旧值
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  // map调整次数 + 1
  ++modCount;
  // 键值对的数量达到阈值，需要扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

Первый взглядputValметод, этот метод является окончательным, если вы определяете свое собственное наследование HashMap, вам не разрешено самостоятельно переопределять метод put, и тогда этот метод включает пять параметров

  • Hash -> PUT помещается в бочку, перед PUT выполняется расчет функции Hash.
  • key -> ключевое значение параметра
  • значение -> значение параметра
  • onlyIfAbsent -> менять ли существующее значение, то есть заменять ли значение value
  • evict -> является флагом только что созданного HashMap

При вызове метода putVal хеш-функция сначала рассчитает позицию, в которую его следует вставить.

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

Исходный код хэш-функции выглядит следующим образом

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Во-первых, первый понять, как функция правил расчета

Хэш-функция

Хеш-функция будет рассчитываться на основе значения ключа, которое вы передаете, сначала вычислите значение ключа.hashCodeзначение, а затем выполнить операцию сдвига вправо без знака для хэш-кода и, наконец, выполнить операцию сдвига вправо без знака с хэш-кодом异或 ^работать.

>>>: беззнаковая операция сдвига вправо, относится к, то есть, независимо от того, положительное это число или отрицательное, сдвиг вправо добавит 0 к вакантной позиции.

После получения значения хеш-функции будет выполнен процесс размещения.

Во-первых, он определит, является ли массив Node в HashMap нулевым.Если HashMap создается в первый раз и элемент вставляется в первый раз, сначала будет изменен размер массива, то есть重新分配, который также включает в себяresize()Анализ механизма источника расширения, мы будем представлены позже. После завершения расширения он рассчитывает положение хранения Hashmap с помощью( n - 1 ) & hashРассчитайте это.

Затем эта позиция будет использоваться в качестве нижнего индекса массива в качестве позиции для хранения элемента. Если не пусто, то вычислите этот истинный хэш в таблице по сравнению с key.hash для вставки. Если хеш-значение одинаковое, а ключ-значение другое, то оцените, является ли это экземпляром дерева, и если да, то вставьте его в дерево. Если нет, то выполняется метод вставки хвоста для вставки в конце цепочки записей.

Он будет судить, является ли это связанным списком или красно-черным деревом, в зависимости от количества элементов в ведре. Затем оцените, превышает ли количество пар ключ-значение пороговое значение, и если да, увеличьте емкость.

Механизм расширения

В Java массивы имеют фиксированную длину, что означает, что массивы могут хранить только фиксированный объем данных. Но в процессе разработки мы часто не можем знать, насколько большим должен быть массив. К счастью, HashMap является автоматически расширяющейся структурой данных, и в этой структуре данных переменной длины очень важен механизм расширения.

В HashMap пороговый размер является произведением длины массива сегментов и коэффициента загрузки. Когда количество пар ключ-значение в HashMap превышает пороговое значение, увеличьте емкость. Механизм расширения в HashMap сделанresize()Метод реализован, и мы узнаем. (Опубликовать китайскую ноту, легко копировать)

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  // 存储old table 的大小
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  // 存储扩容阈值
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
    // 如果old table数据已达最大，那么threshold也被设置成最大
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // 左移扩大二倍,
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      // 扩容成原来二倍
      newThr = oldThr << 1; // double threshold
  }
  // 如果oldThr                                                                                                                                               !> 0
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  // 如果old table <= 0 并且 存储的阈值 <= 0
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 如果扩充阈值为0
  if (newThr == 0) {
    // 扩容阈值为 初始容量*负载因子
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  // 重新给负载因子赋值
  threshold = newThr;
  // 获取扩容后的数组
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  // 如果第一次进行table 初始化不会走下面的代码
  // 扩容之后需要重新把节点放在新扩容的数组中
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 重新映射时，需要对红黑树进行拆分
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          // 遍历链表，并将链表节点按原顺序进行分组
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          // 将分组后的链表映射到新桶中
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

Исходный код механизма расширения относительно длинный, мы терпеливо его разделим

Мы разделяем его с помощью логики if...else if...else Вышеприведенный код в основном делает эти вещи

  • Определите длину массива в HashMap, то есть(Node<K,V>[])oldTab.length(), а затем оцените, больше ли длина массива, чем наибольшая длина, которая является степенью 2 ^ 30. Если она велика, возьмите максимальную длину напрямую, в противном случае используйте битовую операцию<<Расширен в два раза больше

  • Если длина массива не больше 0, то определить порог расширенияthresholdБудь то больше 0, то есть, есть ли внешне указанный порог расширения, если это так, используйте его. Здесь нам нужно объяснить, когда порогoldThr > 0, так как oldThr = threshold , сравнение здесь на самом деле пороговое, потому что каждый конструктор в HashMap будет вызыватьHashMap(initCapacity,loadFactor)Этот конструктор, поэтому, если InitialCapacity не указан извне, начальная емкость равна 16, а затем в соответствии сthis.threshold = tableSizeFor(initialCapacity);Найдите значение порога.

  • В противном случае напрямую используются начальная емкость и порог расширения по умолчанию, а логика перехода к другому — это когда таблица только что инициализирована.

Затем будет судить, равен ли newThr 0 , как обнаружил автор, когда я впервые начал исследования.newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);Я всегда думал, что это постоянное умножение, как оно может быть 0, на самом деле это не проблема этой части, это операция расширения в приведенном выше логическом суждении, которая может вызвать位溢出.

Пример переполнения: Oldcap = 2^28 power, Threshold > 2 три раза. Входитьfloat ft = (float)newCap * loadFactor;Этот метод заключается в том, что 2 ^ 28 * 2 ^ (3 + n) будет непосредственно > 2 ^ 31 степени, что приведет к получению всех нулей.

После расширения вам нужно поместить узел в новый массив расширения, что также включает три шага.

  • Каждый узел узел Cycle Cycle Country, определяющий узел [I] пустой, пустой возврат непосредственно без пересечения ванна - это пустое массив, а ключ сопоставляется с новым массивом ведра.

  • Если он не пустой, то оцените, является ли это древовидной структурой.Если это древовидная структура, она будет разделена в соответствии с древовидной структурой.Метод разделения находится вsplitметод.

  • Если это не древовидная структура, пройдите по связанному списку и сгруппируйте узлы связанного списка в исходном порядке.

Расскажите обо всем процессе метода get

Мы рассказали обо всем процессе метода PUT в HashMap, давайте посмотрим.getПроцесс метода,

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

  // 找到真实的元素位置
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    // 总是会check 一下第一个元素
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;

    // 如果不是第一个元素，并且下一个元素不是空的
    if ((e = first.next) != null) {

      // 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);

      // 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
}

Кратко представим его: сначала он проверит, пусты ли элементы в таблице, а затем вычислит позицию указанного ключа по хэшу. Затем проверить, пустой ли первый элемент связанного списка, если он не пустой, соответствует ли он, если он соответствует, вернуть запись напрямую; если он соответствует, то судить, является ли значение следующего элемента равным нулю, если он пусто, верните его напрямую, если не пусто, а затем оцените, является ли оноTreeNodeэкземпляр, если это экземпляр TreeNode, используйте его напрямуюTreeNode.getTreeNodeВыньте элемент, иначе цикл будет выполняться до тех пор, пока следующий элемент не окажется в позиции NULL.

getNodeМетод имеет более важный процесс(n - 1) & hash, этот код предназначен для определения местоположения корзины, которую необходимо найти, так почему же (n - 1) & hash ?

n — количество сегментов в HashMap, что означает, что (n — 1) и хэш — это (емкость сегмента — 1) и хеш.

// 为什么 HashMap 的检索位置是 (table.size - 1) & hash
public static void main(String[] args) {

  Map<String,Object> map = new HashMap<>();

  // debug 得知 1 的 hash 值算出来是 49
  map.put("1","cxuan");
  // debug 得知 1 的 hash 值算出来是 50
  map.put("2","cxuan");
  // debug 得知 1 的 hash 值算出来是 51
  map.put("3","cxuan");

}

Затем (n - 1) и хэш после каждого вычисления, чтобы

этоtab[(n - 1) & hash]Рассчитано точное местоположение.

Обход HashMap

Обход HashMap также с особенно высокой рабочей частотой

Базовый класс для обхода HashMap:HashIterator, это хэш-итератор, это абстрактный класс внутри Hashmap, его конструкция относительно проста, есть только три метода,hasNext, удалить и nextNodeметод, где метод nextNode реализуется тремя итераторами

Эти три итератора

  • KeyIterator, пройти ключ
  • ValueIterator, перебрать значение
  • EntryIterator, пройти по цепочке Entry

Хотя итераторов много, на самом деле порядок их обхода одинаков, а структура очень проста.HashIteratorсерединаnextNodeметод прохождения

final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

final class ValueIterator extends HashIterator
  implements Iterator<V> {
  public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
  implements Iterator<Map.Entry<K,V>> {
  public final Map.Entry<K,V> next() { return nextNode(); }
}

HashIterator обхода

abstract class HashIterator {
  Node<K,V> next;        // 下一个 entry 节点
  Node<K,V> current;     // 当前 entry 节点
  int expectedModCount;  // fail-fast 的判断标识
  int index;             // 当前槽

  HashIterator() {
    expectedModCount = modCount;
    Node<K,V>[] t = table;
    current = next = null;
    index = 0;
    if (t != null && size > 0) { // advance to first entry
      do {} while (index < t.length && (next = t[index++]) == null);
    }
  }

  public final boolean hasNext() {
    return next != null;
  }

  final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
      do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
  }

  public final void remove() {...}
}

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

ты найдешьnextNode()Метод обхода метода такой же, как метод обхода HashIterator, но условия оценки отличаются.При построении HashIterator условия оценки заключаются в том, существует ли связанный список и является ли ведро нулевым, а условие оценки для обхода nextNode становится независимо от того, является ли следующий node узел нулевым или нет.И ведро не является нулевым.

Удалить метод в HashMap

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

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (p = tab[index = (n - 1) & hash]) != null) {
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      node = p;
    else if ((e = p.next) != null) {
      if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else {
        do {
          if (e.hash == hash &&
              ((k = e.key) == key ||
               (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
    if (node != null && (!matchValue || (v = node.value) == value ||
                         (value != null && value.equals(v)))) {
      if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      else if (node == p)
        tab[index] = node.next;
      else
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

Существует много методов удаления, которые в конечном итоге вызовут метод removeNode, но передаваемые значения параметров разные, для демонстрации возьмем remove(object).

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

Вопросы собеседования о hashmap

Структура данных HashMap

В JDK1.7 HashMap принимает位桶 + 链表Осознание того, что использование链表Для обработки коллизий связанные списки с одним и тем же значением хеш-функции хранятся в массиве. Однако, когда в корзине много элементов, то есть когда много элементов с одинаковым значением хеш-функции, эффективность последовательного поиска по значению ключа низка.

Поэтому по сравнению с JDK 1.7 в JDK 1.8 внесены некоторые изменения в базовую структуру.Когда количество элементов в каждой корзине превышает 8, она будет преобразована в красно-черное дерево для оптимизации эффективности запросов.

Помещенный процесс HashMap

Общий процесс выглядит следующим образом.Сначала методом хеширования вычисляется хеш-код объекта, и по хеш-коду определяется место хранения в ведре.Если в ведре нет узла Node, ставим его напрямую. Если в соответствующем ведре уже есть узел Node, он поместит объект в ведро. Длина связанного списка анализируется, чтобы определить, превышает ли длина 8. Если длина связанного списка меньше чем 8, метод вставки начала будет использоваться до JDK1.7, и он будет изменен на метод вставки хвоста после JDK1.8. Если длина связанного списка больше 8, будет выполнена операция с деревом, и связанный список будет преобразован в красно-черное дерево и сохранен в красно-черном дереве.

Почему HashMap не является потокобезопасным

HashMap не является потокобезопасным контейнером, и ненадежность отражается в параллельной операции размещения HashMap несколькими потоками. Если есть два потока A и B, сначала A хочет вставить пару ключ-значение в HashMap.Когда положение ведра определено и помещено, квант времени A просто израсходован, наступает очередь запуска B , а B выполняется после выполнения той же операции, что и A, за исключением того, что B успешно вставляет в нее пару ключ-значение. Если A и B вставлены в одно и то же место (сегмент), то поток A перезапишет запись B после продолжения выполнения, что приведет к несогласованности данных.

Еще один момент заключается в том, что когда HashMap расширяется, из-за метода изменения размера будет формироваться цикл, что приводит к бесконечному циклу и заставляет ЦП взлетать.

Как HashMap обрабатывает коллизии хешей

Нижний слой HashMap реализуется с помощью битового ведра + связанный список.Битовое ведро определяет позицию вставки элемента.Битовое ведро определяется методом хеширования.Все они помещаются в соответствующие битовые ведра для формирования связанного списка. Такой способ обработки коллизий хэшей называется методом цепных адресов.

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

Как HashMap получает элементы

Сначала проверяет элементы в пустой таблице, а затем вычисляет позицию на основе указанного хэша ключа. Затем проверить, пустой ли первый элемент связанного списка, если он не пустой, соответствует ли он, если он соответствует, вернуть запись напрямую; если он соответствует, то судить, является ли значение следующего элемента равным нулю, если он пусто, верните его напрямую, если не пусто, а затем оцените, является ли оноTreeNodeэкземпляр, если это экземпляр TreeNode, используйте его напрямуюTreeNode.getTreeNodeПолучает элемент, в противном случае зацикливается до тех пор, пока следующий элемент не окажется в нулевой позиции.

В чем разница между HashMap и HashTable

См. выше

Разница между HashMap и HashSet

см. выше

Как масштабируется HashMap

В HashMap есть две очень важные переменные, одна из нихloadFactor,одинthreshold, loadFactor представляет коэффициент загрузки, а threshold представляет собой порог для следующего расширения.Когда порог = loadFactor * длина массива, длина массива удваивается, чтобы повторно настроить размер карты и поместить исходный объект в новый массив ведра.

Почему длина HashMap равна степени 2?

Этот вопрос я подумал несколько дней, и раньше и групповые друзья обсудили ежедневный вопрос, спросил, почему длина% хэш == (n - 1) и хеш, они сказали, что равное предпосылку длины длины 2 силовая вечеринка, то я вернулся к власти длины? На самом деле я не понял причинные отношения, потому что длина Hashmap была 2 мощности, поэтому остальная часть числа использовалась для определения индекса в ведре. Если длина длины не 2 мощности, маленькие друзья могут привести пример попробовать

Например, когда длина равна 9, 3 и (9-1) = 0, 2 и (9-1) = 0, все на 0, сталкиваются;

Это увеличивает вероятность коллизий HashMap.

Ashmap поток безопасно осознавать, что

Поскольку HashMap не является потокобезопасным контейнером, рекомендуется использовать его в параллельной сцене.ConcurrentHashMap, или с потокобезопасным HashMap используйтеCollectionsПотокобезопасный контейнер в упаковке, например,

Collections.synchronizedMap(new HashMap());

Вы также можете использовать Hashtable, это также безопасный контейнер, на основе магазина клавиш, Hashmap и Hashtable часто сравниваются, потому что Hashtable и HASHMAP одинаковые структуры данных.

Наиболее эффективным выше является ConcurrenthashMap.

постскриптум

В статье не слишком много описывается структура красно-черного дерева, в том числе процесс добавления, удаления и древовидности, это также большая часть контента, поэтому я буду рассматривать красно-черное дерево за ним для объяснение.

Категории