Класс коллекции HashMap, HashTable, разница ConcurrentHashMap?

Node.js задняя часть JVM Безопасность

1.HashMap

1524282042(1)

Проще говоря, HashMap состоит из массива + связанного списка. Массив является основной частью HashMap, а связанный список существует в основном для разрешения конфликтов хэшей. Если в расположенном массиве нет связанного списка (следующая запись текущей записи указывает на ноль), то для таких операций, как поиск и добавление, требуется только одна адресация; если обнаруженный массив содержит связанный список, временная сложность операции добавления по-прежнему составляет O(1), поскольку последняя Запись будет вставлена ​​в заголовок связанного списка, вам нужно только просто изменить цепочку ссылок.Для операции поиска вам нужно пройти по связанному списку, а затем сравнить и выполнить поиск по одному с помощью метода equals ключа объект. Следовательно, с точки зрения производительности, чем меньше связанных списков в HashMap, тем выше производительность.

Хеш-функция (дальнейший расчет хэш-кода ключа и настройка двоичной позиции гарантируют, что окончательное полученное место хранения будет минимально распределено)

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

Найти функции

1524283341(1)

Хэш-карта была преобразована в JDK1.8, как показано ниже.

shixinzhang

До JDK 1.8 реализация HashMap представляла собой массив + связанный список.Даже если хэш-функция хороша, сложно добиться 100% равномерного распределения элементов.

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

В ответ на эту ситуацию JDK 1.8 представил красно-черное дерево (со сложностью времени поиска O (logn)) для оптимизации этой проблемы.

2.HashTable

Hashtable включает в себя несколько важных переменных элементов: таблица, счет, порог, LoadFactor, MODCOUNT.

  • Таблица представляет собой входную [] тип массива, а запись (объяснена в Hashmap) на самом деле является одним из поощно, связанного списком. «Пары клавишных значений» таблицы HASH хранятся в массиве ввода.
  • count — это размер Hashtable, то есть количество пар ключ-значение, которое содержит Hashtable.
  • порог — это порог Hashtable, который используется для определения необходимости корректировки емкости Hashtable. Значение порога = «мощность * коэффициент загрузки».
  • loadFactor — коэффициент нагрузки.
  • modCount используется для реализации отказоустойчивого механизма.

положить метод

Весь процесс метода put:

  1. Определение того, является ли значение пустым, и оно выдаст аномалию для пустого;
  2. Вычислите хеш-значение ключа и получите индекс позиции ключа в массиве таблиц в соответствии с хеш-значением.Если элемент table[index] не пуст, выполните итерацию, и если встретится тот же ключ, он будет заменено напрямую, и будет возвращено старое значение;
  3. В противном случае мы можем вставить его в позицию table[index].
public synchronized V put(K key, V value) {
        // Make sure the value is not null确保value不为null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        //确保key不在hashtable中
        //首先，通过hash方法计算key的哈希值，并计算得出index值，确定其在table[]中的位置
        //其次，迭代index索引位置的链表，如果该位置处的链表存在相同的key，则替换value，返回旧的value
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //如果超过阀值，就进行rehash操作
            rehash();

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        //将值插入，返回的为null
        Entry<K,V> e = tab[index];
        // 创建新的Entry节点，并将新的Entry插入Hashtable的index位置，并设置e为新的Entry的下一个元素
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

получить метод

По сравнению с методом put метод get намного проще. Процесс заключается в том, чтобы сначала получить хеш-значение ключа с помощью метода hash(), а затем получить индекс индекса в соответствии с хеш-значением (алгоритм, используемый в двух предыдущих шагах, такой же, как и метод put). Затем выполните итерацию связанного списка и верните соответствующее значение соответствующего ключа; если не найдено, верните ноль.

public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

3.ConcurrentHashMap

В версии JDK1.7 структура данных ConcurrentHashMap состоит из массива Segment и нескольких HashEntry.

Смысл массива Segment в том, чтобы разделить большую таблицу на несколько маленьких таблиц для блокировки, что является упомянутой выше технологией разделения блокировок, и каждый элемент Segment хранит массив HashEntry + связанный список, что аналогично HashMap. то же самое

поставить операцию

Для вставки данных ConcurrentHashMap здесь выполняются два хэша, чтобы определить место хранения данных.

static class Segment<K,V> extends ReentrantLock implements Serializable {

Как видно из системы наследования сегмента выше, сегмент реализует ReentrantLock, который также имеет функцию блокировки.При выполнении операции put будет выполнен первый ключевой хэш для определения местоположения сегмента.Если сегмент не был инициализирован, то есть присвоить значение через операцию CAS, а затем выполнить вторую хэш-операцию, чтобы найти позицию соответствующего HashEntry. Здесь будут использоваться характеристики унаследованной блокировки. При вставке данных в указанная позиция HashEntry (конец связанного списка), он передаст Наследовать метод tryLock() ReentrantLock и попытается получить блокировку. Если получение прошло успешно, вставьте его непосредственно в соответствующую позицию. Если уже есть поток который получает блокировку сегмента, текущий поток будет продолжать вызывать метод tryLock() циклически, получает блокировку, приостанавливается после указанного количества раз и ожидает пробуждения.

получить операцию

Операция получения ConcurrentHashMap аналогична HashMap, за исключением того, что ConcurrentHashMap необходимо пройти через хэш, чтобы найти позицию сегмента в первый раз, а затем хешировать к указанному HashEntry, пройти по связанному списку под HashEntry для сравнения и вернуться, если успешно или null в случае неудачи.

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

  1. В первом варианте он будет использовать разблокированный режим, чтобы попробовать несколько вычислений ConcurrentHashMap размера, до трех раз, до и после результатов двух вычислений, результаты не считают, что текущее соглашение по элементам добавляется, результат расчет точен;
  2. Вторая схема заключается в том, что если первая схема не соответствует, он добавит блокировку в каждый Segment, а затем вычислит размер ConcurrentHashMap для возврата.

Реализация JDK1.8

Реализация JDK1.8 отказалась от концепции сегмента, но напрямую реализовала структуру данных массива узлов + связанный список + красно-черное дерево.Управление параллелизмом осуществляется с использованием Synchronized и CAS.Все выглядит так, как будто оно оптимизировано и потоко- safe.HashMap, хотя структуру данных Segment все еще можно увидеть в JDK1.8, атрибуты были упрощены только для совместимости со старыми версиями.

поставить операцию

В приведенном выше примере мы будем вызывать метод put при добавлении личной информации, давайте посмотрим.

  1. Если инициализации нет, сначала вызовите метод initTable(), чтобы выполнить процесс инициализации.
  2. Прямая вставка CAS, если нет конфликта хэшей
  3. Если операция расширения все еще выполняется, сначала увеличьте емкость.
  4. В случае конфликта хэшей добавляются блокировки для обеспечения потокобезопасности.Здесь возможны два случая.Во-первых, связанный список просматривается до конца и вставляется напрямую, а во-вторых, красно-черное дерево вставляется в соответствии с красно-черная древовидная структура.
  5. Наконец, если номер связанного списка больше порогового значения 8, он должен быть преобразован в черно-красную древовидную структуру, и break снова входит в цикл.
  6. Если добавление прошло успешно, вызовите метод addCount(), чтобы подсчитать размер и проверить, требуется ли расширение.

получить операцию

Теперь мы возвращаемся к начальному примеру. После того, как мы добавили личную информацию, нам нужно получить вновь добавленную информацию. Используйте String name = map.get("name") для получения вновь добавленной информации об имени. Теперь мы по-прежнему используем метод отладки для анализа метода получения get() ConcurrentHashMap

public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode()); //计算两次hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来
//查找，查找到就返回
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode，那就往下遍历
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
  1. Вычислите значение HASH, найдите позицию индекса таблицы, если это первый узел, верните
  2. Если у вас есть расширение времени, оно будет вызывать узлы признаков ForwardingNode, метод поиска является расширением и ищет узел, совпадение возвращает
  3. Если ничего из вышеперечисленного не соответствует, пройдите по узлу вниз и вернитесь, если он соответствует, в противном случае верните null в конце

На самом деле видно, что структура данных ConcurrentHashMap в JDK1.8 близка к HashMap.Условно говоря, ConcurrentHashMap только добавляет операции синхронизации для управления параллелизмом.От ReentrantLock+Segment+HashEntry в JDK1.7 до JDK1.8 Synchronized+ CAS+HashEntry+красно-черное дерево, условно говоря, итог такой:

  1. Реализация JDK1.8 снижает степень детализации блокировок.Дробность блокировок JDK1.7 основана на сегменте, включая несколько HashEntry, а степень детализации блокировки JDK1.8 — на HashEntry (первый узел).
  2. Структура данных версии JDK1.8 стала проще, что сделало работу более четкой и гладкой.Поскольку для синхронизации используется синхронизация, концепция блокировки сегмента не требуется, и структура данных сегмента не требуется.Снижена сложность реализации также увеличилось
  3. JDK1.8 использует красно-черное дерево для оптимизации связанного списка.Обход длинного связанного списка является очень длительным процессом, а эффективность обхода красно-черного дерева очень высока.Вместо связанного списка с определенный порог, он формирует оптимального партнера.
  4. Почему JDK1.8 использует встроенную синхронизированную блокировку вместо реентерабельной блокировки ReentrantLock, я думаю тут есть следующие моменты:
  • Поскольку степень детализации снижена, в методе блокировки с относительно низкой степенью детализации, synchronized не хуже, чем ReentrantLock.В крупнозернистой блокировке ReentrantLock может контролировать границы каждой низкой детализации через Condition, который является более гибким. , Преимущество Состояние исчезло
  • Команда разработчиков JVM никогда не отказывалась от синхронизации, а пространство оптимизации синхронизации на основе JVM больше, использование встроенных ключевых слов более естественно, чем использование API.
  • При большом количестве операций с данными из-за нехватки памяти JVM ReentrantLock на основе API будет потреблять больше памяти, хотя это не является узким местом, но также является основой для выбора.

4. Резюме

Hashtable и HashMap имеют несколько основных отличий: потокобезопасность и скорость. Используйте Hashtable только в том случае, если вам нужна полная безопасность потоков, а если вы используете Java 5 или выше, вместо этого используйте ConcurrentHashMap.


Категории