Map
Карта — это структура данных для быстрого поиска. Она хранит данные в виде пар ключ-значение. Каждый ключ уникален и соответствует значению. Если вы хотите найти данные в карте, вам нужно только передать ключ, карту будет соответствовать ключу и вернет значение, соответствующее ключу.Можно сказать, что Map на самом деле представляет собой набор пар ключ-значение. Карта широко используется в различных языках программирования, но название может немного сбивать с толку, например в Python это называется словарь (Dictionary), а некоторые языки называют его ассоциативным массивом (Associative Array), но на самом деле все они то же самое, оба являются набором пар ключ-значение. Что касается HashMap, который часто используется в Java, это также тип карты, который называется хэш-таблицей.Я буду упоминать подробности хэш-таблицы при объяснении исходного кода HashMap в этой статье.
Java также предоставляет структуру данных, тесно связанную с Map:Set, которая является коллекцией в математическом смысле со следующими характеристиками:
-
Беспорядок: в наборе статус каждого элемента одинаков, и элементы также неупорядочены. Однако Java также предоставляет упорядоченный набор, который не полностью соблюдается.
-
Взаимность: любые два элемента в наборе не совпадают.
-
Детерминированный: при заданном наборе и любом из его элементов должно быть определено, принадлежит ли элемент набору или нет.
Очевидно, что ключ в Map очень подходит для этих характеристик, и реализация Set фактически использует Map внутри. Например, HashSet определяет переменную-член типа HashMap. Добавление элемента a в HashSet эквивалентно добавлению пары ключ-значение с ключом a и значением объекта Object во внутреннюю HashMap. Этот объект Object является константой A HashSet, это фиктивное значение и не имеет фактического значения.Исходный код выглядит следующим образом:
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
После этого эпизода давайте перейдем к Map, который является интерфейсом JDK верхнего уровня и предоставляет три вида коллекций (Collection Views): коллекцию, содержащую все ключи, коллекцию, содержащую все значения, и коллекцию, содержащую все ключи-значения. пары, Карта Порядок элементов в связан с порядком итерации элементов в представлении коллекции, которое он возвращает. То есть сама карта не гарантирует упорядочение, конечно, есть исключения. Например, TreeMap гарантирует упорядочение, который Главным образом потому, что он реализован на основе красно-черного дерева.
Так называемое представление коллекции — это способ доступа к данным, предоставляемым самой коллекцией, и любое изменение представления также повлияет на коллекцию. какMap.keySet()возвращает набор содержащихся в нем ключей, если вы вызываетеMap.remove(key)ТакkeySet.contains(key)также вернетсяfalse, скажемArrays.asList(T)Вы можете инкапсулировать массив в список, чтобы иметь доступ к данным и управлять ими через API списка, например следующий пример кода:
String[] strings = {"a", "b", "c"};
List<String> list = Arrays.asList(strings);
System.out.println(list.get(0)); // "a"
strings[0] = "d";
System.out.println(list.get(0)); // "d"
list.set(0, "e");
System.out.println(strings[0]); // "e"
Разве это не удивительно, на самом делеArrays.asList()просто объедините входящий массив сArraysвнутренний класс вArrayList(обратите внимание, что это то же самое, что иjava.utilв упаковкеArrayListне тот) сделал "привязку", после звонкаget()Когда элемент в массиве возвращается непосредственно по индексу, а вызовset()Он также напрямую изменит элемент, соответствующий индексу в массиве. По сравнению с прямым копированием преимущество представления коллекции заключается в том, что использование памяти выше.Предположим, у вас есть массив и вы хотите использовать API списка для работы с ним, тогда вам не нужно создавать новый.ArrayListдля копирования элементов массива, требуя лишь немного дополнительной памяти (черезArrays.ArrayListИнкапсулировать массив), исходные данные все еще находятся в массиве и не будут копироваться в несколько копий.
Интерфейс Map стандартизирует общий API структуры данных Map (также содержит несколько методов по умолчанию для упрощения операций, default — это новая функция JDK8, это реализация по умолчанию методов, объявленных в интерфейсе, то есть неабстрактных методов ) и по-прежнему внутренне Определен интерфейс Entry (сущностный класс пар ключ-значение). Все структуры данных Map, представленные в JDK, реализуют интерфейс Map. Ниже приведен исходный код интерфейса Map (комментарии в коде слишком длинные, и они в основном являются спецификациями реализации. Я постараюсь опустить их для экономии места).
package java.util;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;
public interface Map<K,V> {
// 查询操作
/**
* 返回这个Map中所包含的键值对的数量，如果大于Integer.MAX_VALUE，
* 则应该返回Integer.MAX_VALUE。
*/
int size();
/**
* Map是否为空。
*/
boolean isEmpty();
/**
* Map中是否包含key，如果是返回true，否则false。
*/
boolean containsKey(Object key);
/**
* Map中是否包含value，如果是返回true，否则false。
*/
boolean containsValue(Object value);
/**
* 根据key查找value，如果Map不包含该key，则返回null。
*/
V get(Object key);
// 修改操作
/**
* 添加一对键值对，如果Map中已含有这个key，那么新value将覆盖掉旧value，
* 并返回旧value，如果Map中之前没有这个key，那么返回null。
*/
V put(K key, V value);
/**
* 删除指定key并返回之前的value，如果Map中没有该key，则返回null。
*/
V remove(Object key);
// 批量操作
/**
* 将指定Map中的所有键值对批量添加到当前Map。
*/
void putAll(Map<? extends K, ? extends V> m);
/**
* 删除Map中所有的键值对。
*/
void clear();
// 集合视图
/**
* 返回包含Map中所有key的Set，对该视图的所有修改操作会对Map产生同样的影响，反之亦然。
*/
Set<K> keySet();
/**
* 返回包含Map中所有value的集合，对该视图的所有修改操作会对Map产生同样的影响，反之亦然。
*/
Collection<V> values();
/**
* 返回包含Map中所有键值对的Set，对该视图的所有修改操作会对Map产生同样的影响，反之亦然。
*/
Set<Map.Entry<K, V>> entrySet();
/**
* Entry代表一对键值对，规范了一些基本函数以及几个已实现的类函数（各种比较器）。
*/
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// 比较和hashing
/**
* 将指定的对象与此Map进行比较是否相等。
*/
boolean equals(Object o);
/**
* 返回此Map的hash code。
*/
int hashCode();
// 默认方法（非抽象方法）
/**
* 根据key查找value，如果该key不存在或等于null则返回defaultValue。
*/
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
}
/**
* 遍历Map并对每个键值对执行指定的操作（action）。
* BiConsumer是一个函数接口（具有一个抽象方法的接口，用于支持Lambda），
* 它代表了一个接受两个输入参数的操作，且不返回任何结果。
* 至于它奇怪的名字，根据Java中的其他函数接口的命名规范，Bi应该是Binary的缩写，意思是二元的。
*/
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
/**
* 遍历Map，然后调用传入的函数function生成新value对旧value进行替换。
* BiFunction同样是一个函数接口，它接受两个输入参数并且返回一个结果。
*/
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
/**
* 如果指定的key不存在或者关联的value为null，则添加键值对。
*/
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
/**
* 当指定key关联的value与传入的参数value相等时删除该key。
*/
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
/**
* 当指定key关联的value与oldValue相等时，使用newValue进行替换。
*/
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
/**
* 当指定key关联到某个value时进行替换。
*/
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
/**
* 当指定key没有关联到一个value或者value为null时，调用mappingFunction生成值并添加键值对到Map。
* Function是一个函数接口，它接受一个输入参数并返回一个结果，如果mappingFunction返回的结果
* 也为null，那么将不会调用put。
*/
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
/**
* 当指定key关联到一个value并且不为null时，调用remappingFunction生成newValue，
* 如果newValue不为null，那么进行替换，否则删除该key。
*/
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
/**
* remappingFunction根据key与其相关联的value生成newValue，
* 当newValue等于null时删除该key，否则添加或者替换旧的映射。
*/
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
/**
* 当指定key没有关联到一个value或者value为null，将它与传入的参数value
* 进行关联。否则，调用remappingFunction生成newValue并进行替换。
* 如果，newValue等于null，那么删除该key。
*/
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
Следует отметить, что эти методы по умолчанию не являются потокобезопасными, и любой класс расширения, гарантирующий потокобезопасность, должен переопределять эти методы, например ConcurrentHashMap.
На следующем рисунке показана схема структуры отношения наследования Map, которая также является схемой классов реализации Map, которые будут проанализированы в этой статье.Эти классы реализации используются относительно часто.В JDK есть десятки классов реализации Map, большинство из которых которые являются нашими.Те, которые не используются, не будут объяснены по одному из-за нехватки места (эта статья содержит много исходного кода и анализ деталей реализации, читателям рекомендуется занять непрерывное свободное время, чтобы успокоиться и читать медленно).
Автор этой статьиSylvanasSun(sylvanas.sun@gmail.com), впервые опубликовано вБлог SylvanasSun. Исходная ссылка: https://sylvanassun.github.io/2018/03/16/2018-03-16-map_family/ (Для перепечатки просьба сохранить заявление в этом абзаце и сохранить гиперссылку.)
AbstractMap
AbstractMap — это абстрактный класс, представляющий собой скелет реализации интерфейса Map, который минимизирует абстрактные функции, предоставляемые этим интерфейсом. Это правило в основном соблюдается в структуре Java Collection.Скелетная реализация создает уровень абстракции между интерфейсом и классом реализации.Цель состоит в том, чтобы повторно использовать некоторые более общие функции и облегчить расширение.Например, интерфейс List имеет скелетную реализацию. Интерфейс AbstractList, Set имеет каркасную реализацию AbstractSet и так далее.
Давайте посмотрим, что реализует AbstractMap в соответствии с различными типами операций.Первым является операция запроса:
package java.util;
import java.util.Map.Entry;
public abstract class AbstractMap<K,V> implements Map<K,V> {
protected AbstractMap() {
}
// Query Operations
public int size() {
return entrySet().size();
}
// 键值对的集合视图留给具体的实现类实现
public abstract Set<Entry<K,V>> entrySet();
public boolean isEmpty() {
return size() == 0;
}
/**
* 遍历entrySet，然后逐个进行比较。
*/
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
/**
* 跟containsValue()同理，只不过比较的是key。
*/
public boolean containsKey(Object key) {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}
/**
* 遍历entrySet，然后根据key取出关联的value。
*/
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
}
Можно обнаружить, что эти операции зависят от функцииentrySet()Да, он возвращает представление коллекции пар ключ-значение.Поскольку реализация Entry разных подклассов реализации также может отличаться, она обычно реализуется внутренне для наследования от AbstractSet, а универсальный типMap.EntryВнутренний класс используется как EntrySet, за которым следуют операции модификации и пакетные операции:
// Modification Operations
/**
* 没有提供实现，子类必须重写该方法，否则调用put()会抛出异常。
*/
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
/**
* 遍历entrySet，先找到目标的entry，然后删除。
*（还记得之前说过的吗，集合视图中的操作也会影响到实际数据）
*/
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
// Bulk Operations
/**
* 遍历参数m，然后将每一个键值对put到该Map中。
*/
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
/**
* 清空entrySet等价于清空该Map。
*/
public void clear() {
entrySet().clear();
}
Абстрактная карта не реализованаput()функция, это делается для того, чтобы учесть, что могут быть неизменяемые подклассы реализации Карты, наследующие ее, в то время как для модифицируемой реализации подкласс реализации Карты должен переопределятьput()функция.
AbstractMap не предоставляетentrySet()реализации, но обеспечиваетkeySet()иvalues()Реализация коллекций по умолчанию, все они зависят отentrySet()Реализовано возвращаемое представление коллекции, исходный код выглядит следующим образом:
/**
* keySet和values是lazy的，它们只会在第一次请求视图时进行初始化，
* 而且它们是无状态的，所以只需要一个实例（初始化一次）。
*/
transient Set<K> keySet;
transient Collection<V> values;
/**
* 返回一个AbstractSet的子类，可以发现它的行为都委托给了entrySet返回的集合视图
* 与当前的AbstractMap实例，所以说它自身是无状态的。
*/
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}
/**
* 与keySet()基本一致，唯一的区别就是返回的是AbstractCollection的子类，
* 主要是因为value不需要保持互异性。
*/
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}
Он также предоставляет два класса реализации Entry: SimpleEntry и SimpleImmutableEntry, Реализация этих двух классов очень проста, разница в том, что первый изменяем, а второй неизменяем.
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = -8499721149061103585L;
private final K key;
private V value;
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public String toString() {
return key + "=" + value;
}
}
/**
* 它与SimpleEntry的区别在于它是不可变的，value被final修饰，并且不支持setValue()。
*/
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = 7138329143949025153L;
private final K key;
private final V value;
public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
throw new UnsupportedOperationException();
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public String toString() {
return key + "=" + value;
}
}
Читая приведенный выше исходный код, нетрудно обнаружить, что все операции, реализованные в AbstractMap, зависят отentrySet()Представление возвращаемой коллекции. Об остальных функциях и говорить нечего, если интересно, можете съездить и посмотреть сами.
TreeMap
TreeMap — это Карта, основанная на красно-черном дереве (самобалансирующемся бинарном дереве поиска), гарантирующем упорядочение. На диаграмме структуры отношений наследования мы видим, что TreeMap реализует интерфейс NavigableMap, который, в свою очередь, наследует интерфейс SortedMap. давайте посмотрим, какие функции определяют эти два интерфейса.
SortedMap
Первый — это интерфейс SortedMap. Класс реализации, реализующий этот интерфейс, должен обеспечивать упорядочение ключей в соответствии с естественным порядком, так называемый естественный порядок, основанный на порядке ключей.compareTo()функция (которая должна реализовать интерфейс Comparable) или класс реализации Comparator, переданный в конструктор для сортировки, и порядок обхода элементов в представлении коллекции также должен соответствовать порядку ключей. Интерфейс SortedMap также определяет следующие функции, позволяющие эффективно использовать упорядочение:
package java.util;
public interface SortedMap<K,V> extends Map<K,V> {
/**
* 用于在此Map中对key进行排序的比较器，如果为null，则使用key的compareTo()函数进行比较。
*/
Comparator<? super K> comparator();
/**
* 返回一个key的范围为从fromKey到toKey的局部视图（包括fromKey，不包括toKey，包左不包右），
* 如果fromKey和toKey是相等的，则返回一个空视图。
* 返回的局部视图同样是此Map的集合视图，所以对它的操作是会与Map互相影响的。
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 返回一个严格地小于toKey的局部视图。
*/
SortedMap<K,V> headMap(K toKey);
/**
* 返回一个大于或等于fromKey的局部视图。
*/
SortedMap<K,V> tailMap(K fromKey);
/**
* 返回当前Map中的第一个key（最小）。
*/
K firstKey();
/**
* 返回当前Map中的最后一个key（最大）。
*/
K lastKey();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}
NavigableMap
Затем есть подинтерфейс NavigableMap для SortedMap, который расширяет некоторые методы навигации, такие как функцииlowerEntry(key)Он вернет самую большую пару пар ключ-значение, меньшую, чем ключ в соответствии с ключом входящего параметра.Например, мы вызываем следующим образомlowerEntry(6), то будет возвращена пара ключ-значение с ключом 5, если нет ключа с ключом 5, будет возвращена пара ключ-значение с ключом 4 и так далее, пока не будет возвращено значение null (если его не удастся найти) .
public static void main(String[] args) {
NavigableMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < 10; i++)
map.put(i, i);
assert map.lowerEntry(6).getKey() == 5;
assert map.lowerEntry(5).getKey() == 4;
assert map.lowerEntry(0).getKey() == null;
}
NavigableMap определяет что-то похожее наlowerEntry(key)методы и представления коллекций, отсортированные в обратном и возрастающем порядке, эти методы используют упорядочение для достижения более гибких операций, чем интерфейс SortedMap.
package java.util;
public interface NavigableMap<K,V> extends SortedMap<K,V> {
/**
* 返回一个小于指定key的最大的一对键值对，如果找不到则返回null。
*/
Map.Entry<K,V> lowerEntry(K key);
/**
* 返回一个小于指定key的最大的一个key，如果找不到则返回null。
*/
K lowerKey(K key);
/**
* 返回一个小于或等于指定key的最大的一对键值对，如果找不到则返回null。
*/
Map.Entry<K,V> floorEntry(K key);
/**
* 返回一个小于或等于指定key的最大的一个key，如果找不到则返回null。
*/
K floorKey(K key);
/**
* 返回一个大于或等于指定key的最小的一对键值对，如果找不到则返回null。
*/
Map.Entry<K,V> ceilingEntry(K key);
/**
* 返回一个大于或等于指定key的最小的一个key，如果找不到则返回null。
*/
K ceilingKey(K key);
/**
* 返回一个大于指定key的最小的一对键值对，如果找不到则返回null。
*/
Map.Entry<K,V> higherEntry(K key);
/**
* 返回一个大于指定key的最小的一个key，如果找不到则返回null。
*/
K higherKey(K key);
/**
* 返回该Map中最小的键值对，如果Map为空则返回null。
*/
Map.Entry<K,V> firstEntry();
/**
* 返回该Map中最大的键值对，如果Map为空则返回null。
*/
Map.Entry<K,V> lastEntry();
/**
* 返回并删除该Map中最小的键值对，如果Map为空则返回null。
*/
Map.Entry<K,V> pollFirstEntry();
/**
* 返回并删除该Map中最大的键值对，如果Map为空则返回null。
*/
Map.Entry<K,V> pollLastEntry();
/**
* 返回一个以当前Map降序（逆序）排序的集合视图
*/
NavigableMap<K,V> descendingMap();
/**
* 返回一个包含当前Map中所有key的集合视图，该视图中的key以升序（正序）排序。
*/
NavigableSet<K> navigableKeySet();
/**
* 返回一个包含当前Map中所有key的集合视图，该视图中的key以降序（逆序）排序。
*/
NavigableSet<K> descendingKeySet();
/**
* 与SortedMap.subMap基本一致，区别在于多的两个参数fromInclusive和toInclusive，
* 它们代表是否包含from和to，如果fromKey与toKey相等，并且fromInclusive与toInclusive
* 都为true，那么不会返回空集合。
*/
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
/**
* 返回一个小于或等于（inclusive为true的情况下）toKey的局部视图。
*/
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
/**
* 返回一个大于或等于（inclusive为true的情况下）fromKey的局部视图。
*/
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
/**
* 等价于subMap(fromKey, true, toKey, false)。
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 等价于headMap(toKey, false)。
*/
SortedMap<K,V> headMap(K toKey);
/**
* 等价于tailMap(fromKey, true)。
*/
SortedMap<K,V> tailMap(K fromKey);
}
Интерфейс NavigableMap гораздо более гибкий, чем интерфейс SortedMap.Поскольку TreeMap также реализует этот интерфейс, очень удобно использовать TreeMap, когда вам нужны данные в порядке и вы хотите иметь гибкий доступ к ним.
красно-черное дерево
Выше мы упоминали, что внутренняя реализация TreeMap основана на красно-черном дереве, которое является разновидностью бинарного дерева поиска. Двоичное дерево поиска представляет собой упорядоченную древовидную структуру, преимущество в том, что временная сложность поиска и вставки составляет всегоO(log n), со следующими характеристиками:
-
Любой узел может иметь не более двух дочерних узлов.
-
Левый и правый узлы любого узла можно рассматривать как бинарное дерево поиска.
-
Если левое поддерево любого узла не пусто, то все узлы левого поддерева имеют значение меньше, чем значение его корневого узла.
-
Если правое поддерево любого узла не пусто, то значение всех узлов в правом поддереве больше, чем значение его корневого узла.
-
Ключи любого узла разные.
Хотя бинарное дерево поиска выглядит красиво, оно может быть контрпродуктивным, и бинарное дерево поиска может стать не таким эффективным в крайних случаях Предположим, у нас есть упорядоченная последовательность целых чисел:1,2,3,4,5,6,7,8,9,10,..., что произойдет, если вы вставите всю эту последовательность в двоичное дерево поиска по порядку? Двоичное дерево поиска будет перекошено, каждый элемент в последовательности больше своего корневого узла (предыдущего элемента), а левое поддерево всегда пусто, то это бинарное дерево поиска ничем не отличается от обычного связанного списка. сложность операции поиска толькоO(n).
Чтобы решить эту проблему, необходимо ввести самобалансирующееся бинарное дерево поиска. Так называемая самобалансировка заключается в исправлении, когда древовидная структура вот-вот наклонится. Эта операция исправления называется вращением, а дерево может быть уравновешен операцией вращения.
Красно-черное дерево является реализацией сбалансированного бинарного дерева поиска. Его название происходит от того факта, что его дочерние узлы окрашены, и каждый дочерний узел либо черный, либо красный. Поскольку существует только два цвета (два состояния), логическое значение обычно используется для Указывает, что следующая запись реализована в TreeMap, которая представляет собой узел в красно-черном дереве:
// Red-black mechanics
private static final boolean RED = false;
private static final boolean BLACK = true;
/**
* Node in the Tree. Doubles as a means to pass key-value pairs back to
* user (see Map.Entry).
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
Операция поиска любого сбалансированного бинарного дерева поиска такая же, как и у бинарного дерева поиска, потому что операция поиска не влияет на структуру дерева и, следовательно, не нуждается в модификации.Код выглядит следующим образом:
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 使用Comparator进行比较
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 从根节点开始，不断比较key的大小进行查找
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) // 小于，转向左子树
p = p.left;
else if (cmp > 0) // 大于，转向右子树
p = p.right;
else
return p;
}
return null; // 没有相等的key，返回null
}
Операции вставки и удаления тесно связаны с деталями сбалансированного бинарного дерева поиска.Что касается деталей реализации красно-черного дерева, я уже писал в блоге ранее.Дело о красно-черном деревеОбъяснено очень понятно, читателям, не знакомым с этим аспектом, рекомендуется ознакомиться, поэтому я не буду повторяться здесь.
просмотр коллекции
Наконец, давайте взглянем на реализацию представления коллекции TreeMap, Представление коллекции обычно реализует класс, который инкапсулирует текущий экземпляр, поэтому модификация представления коллекции по сути является модификацией текущего экземпляра, и TreeMap не является исключением. .
древовидная картаheadMap(),tailMap()а такжеsubMap()Все функции возвращают статический внутренний класс AscendingSubMap
abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
private static final long serialVersionUID = -2102997345730753016L;
final TreeMap<K,V> m;
/**
* (fromStart, lo, loInclusive) 与 (toEnd, hi, hiInclusive)代表了两个三元组，
* 如果fromStart为true，那么范围的下限（绝对）为map（被封装的TreeMap）的起始key，
* 其他值将被忽略。
* 如果loInclusive为true，lo将会被包含在范围内，否则lo是在范围外的。
* toEnd与hiInclusive与上述逻辑相似，只不过考虑的是上限。
*/
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
NavigableSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException("fromKey > toKey");
} else {
if (!fromStart) // type check
m.compare(lo, lo);
if (!toEnd)
m.compare(hi, hi);
}
this.m = m;
this.fromStart = fromStart;
this.lo = lo;
this.loInclusive = loInclusive;
this.toEnd = toEnd;
this.hi = hi;
this.hiInclusive = hiInclusive;
}
// internal utilities
final boolean tooLow(Object key) {
if (!fromStart) {
int c = m.compare(key, lo);
// 如果key小于lo，或等于lo（需要lo不包含在范围内）
if (c < 0 || (c == 0 && !loInclusive))
return true;
}
return false;
}
final boolean tooHigh(Object key) {
if (!toEnd) {
int c = m.compare(key, hi);
// 如果key大于hi，或等于hi（需要hi不包含在范围内）
if (c > 0 || (c == 0 && !hiInclusive))
return true;
}
return false;
}
final boolean inRange(Object key) {
return !tooLow(key) && !tooHigh(key);
}
final boolean inClosedRange(Object key) {
return (fromStart || m.compare(key, lo) >= 0)
&& (toEnd || m.compare(hi, key) >= 0);
}
// 判断key是否在该视图的范围之内
final boolean inRange(Object key, boolean inclusive) {
return inclusive ? inRange(key) : inClosedRange(key);
}
/*
* 以abs开头的函数为关系操作的绝对版本。
*/
/*
* 获得最小的键值对：
* 如果fromStart为true，那么直接返回当前map实例的第一个键值对即可，
* 否则，先判断lo是否包含在范围内，
* 如果是，则获得当前map实例中大于或等于lo的最小的键值对，
* 如果不是，则获得当前map实例中大于lo的最小的键值对。
* 如果得到的结果e超过了范围的上限，那么返回null。
*/
final TreeMap.Entry<K,V> absLowest() {
TreeMap.Entry<K,V> e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
}
// 与absLowest()相反
final TreeMap.Entry<K,V> absHighest() {
TreeMap.Entry<K,V> e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
// 下面的逻辑就都很简单了，注意会先判断key是否越界，
// 如果越界就返回绝对值。
final TreeMap.Entry<K,V> absCeiling(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absHigher(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absFloor(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absLower(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
/** 返回升序遍历的绝对上限 */
final TreeMap.Entry<K,V> absHighFence() {
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
/** 返回降序遍历的绝对下限 */
final TreeMap.Entry<K,V> absLowFence() {
return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
}
// 剩下的就是实现NavigableMap的方法以及一些抽象方法
// 和NavigableSubMap中的集合视图函数。
// 大部分操作都是靠当前实例map的方法和上述用于判断边界的方法提供支持
.....
}
Наиболее важным для частичного представления является возможность определить, принадлежит ли входящий ключ области действия представления.В приведенном выше коде можно обнаружить, что NavigableSubMap предоставляет множество вспомогательных функций для оценки области действия.Далее, давайте посмотрим на NavigableSubMap Как реализованы итераторы:
/**
* Iterators for SubMaps
*/
abstract class SubMapIterator<T> implements Iterator<T> {
TreeMap.Entry<K,V> lastReturned;
TreeMap.Entry<K,V> next;
final Object fenceKey;
int expectedModCount;
SubMapIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
expectedModCount = m.modCount;
lastReturned = null;
next = first;
// UNBOUNDED是一个虚拟值（一个Object对象），表示无边界。
fenceKey = fence == null ? UNBOUNDED : fence.key;
}
// 只要next不为null并且没有超过边界
public final boolean hasNext() {
return next != null && next.key != fenceKey;
}
final TreeMap.Entry<K,V> nextEntry() {
TreeMap.Entry<K,V> e = next;
// 已经遍历到头或者越界了
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
// modCount是一个记录操作数的计数器
// 如果与expectedModCount不一致
// 则代表当前map实例在遍历过程中已被修改过了（从其他线程）
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向后移动next指针
// successor()返回指定节点的继任者
// 它是节点e的右子树的最左节点
// 也就是比e大的最小的节点
// 如果e没有右子树，则会试图向上寻找
next = successor(e);
lastReturned = e; // 记录最后返回的节点
return e;
}
final TreeMap.Entry<K,V> prevEntry() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向前移动next指针
// predecessor()返回指定节点的前任
// 它与successor()逻辑相反。
next = predecessor(e);
lastReturned = e;
return e;
}
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 被删除的节点被它的继任者取代
// 执行完删除后，lastReturned实际指向了它的继任者
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
final void removeDescending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
}
final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
SubMapEntryIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
super(first, fence);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
public void remove() {
removeAscending();
}
}
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
}
public Map.Entry<K,V> next() {
return prevEntry();
}
public void remove() {
removeDescending();
}
}
До сих пор мы много обсуждали представления коллекций, и я думаю, что каждый может понять концепцию представлений коллекций.Благодаря SortedMap и NavigableMap в TreeMap существует множество представлений коллекций, включая различные частичные представления и различную сортировку.Посмотрите, заинтересованные читатели могут просматривать исходный код самостоятельно, и следующее содержимое не будет слишком много объяснять представление коллекции.
HashMap
Как вы можете догадаться из названия, HashMap должен быть реализован на основе алгоритма хеширования, эта карта на основе хеширования называется хеш-таблицей.
Массив хранится в хеш-таблице, и каждый элемент массива называется сегментом.key = "a"При запросе хэш-таблица сначала передаст ключ в хеш-функцию для адресации, а полученный результат будет индексом массива, а затем ассоциированное значение можно будет получить, обратившись к массиву через этот индекс.
Все мы знаем, что организация данных в массиве линейна, это позволит непосредственно выделить ряд последовательных последовательностей адресов памяти, для нахождения элемента нужно только вычислить смещение адреса по индексу (найти начало элемента Адрес: начальный адрес массива плюс нижний индекс, умноженный на размер адреса, занимаемого типом элемента). Следовательно, в идеальном случае хеш-таблицы временная сложность различных операций составляет всего лишьO(1), который даже превосходит бинарные деревья поиска, хотя идеал не всегда выполняется, о чем мы поговорим позже.
Почему хэш?
Алгоритм хеширования — это алгоритм дайджеста данных, который может извлекать свой «отпечаток пальца» из любых данных.Он сопоставляет данные (входные данные) любого размера с последовательностью фиксированного размера (выходными данными), которая называется хеш-кодом, дайджестом данных или отпечатком пальца. Наиболее известными алгоритмами хеширования являются MD5 и SHA.
Хэш уникален и необратим. Уникальность означает, что хэш-код, сгенерированный одним и тем же входом, всегда один и тот же, и легко понять, что он необратим. Алгоритм дайджеста данных не является алгоритмом сжатия, он просто генерирует дайджест data. , данные не сжаты. Алгоритм сжатия обычно использует более компактное правило кодирования для повторного кодирования данных.Для декомпрессии требуется только декодирование в соответствии с правилом кодирования.Представьте, что хэш-код, сгенерированный несколькими сотнями МБ или даже несколькими ГБ данных, является всего лишь одним Если последовательность фиксированной длины может быть распакована в обратном направлении, как насчет других алгоритмов сжатия?
То, что мы обсуждали выше, — это только хэш-алгоритм в криптографии, а хеш-функция, необходимая в хеш-таблице, — это возможность адресации ключа к позиции в сегментах, а реализация хэш-функции влияет на производительность всей хеш-таблицы. .
Идеальная хеш-функция должна иметь возможность равномерно распределять ключи по корзинам, при этом каждый ключ должен быть назначен корзине, но это невозможно. Хотя хеш-алгоритм уникален, он также повторяем. Уникальность гарантирует, что вывод одного и того же ввода непротиворечив, но не гарантирует, что вывод разных входов несовместим. То есть это вполне возможно для двух разных ключей. назначаются одному и тому же сегменту (поскольку их хэш-коды могут совпадать), это называется коллизией. Короче говоря, идеал очень богат, а реальность очень худа.Хэш-функция может только максимально уменьшить конфликт, а полностью устранить конфликт невозможно.
Есть много способов реализовать хэш-функции, и хорошая хеш-функция зависит от того, сможет ли она равномерно распределять ключи. Прежде всего, вводится самый простой метод: метод остатка, сначала хешировать ключ, чтобы получить его хэш-код, а затем использовать хэш-код, чтобы взять остаток от количества элементов в массиве Buckets, и результатом является индекс ведра, то есть Этот метод прост и эффективен, а также может использоваться в качестве алгоритма маршрутизации для балансировки нагрузки кластера.
private int hash(Key key) {
// & 0x7fffffff 是为了屏蔽符号位，M为bucket数组的长度
return (key.hashCode() & 0x7fffffff) % M;
}
Следует отметить, что только целые числа могут выполнять операцию остатка.Если хэш-код представляет собой строку или другой тип, вам необходимо преобразовать его в целое число, чтобы использовать метод остатка, но Java предоставляет объект Object.hashCode()функция, эта функция возвращает значение int, поэтому любой пользовательский абстрактный тип данных, который вы хотите поместить в HashMap, должен реализовать эту функцию иequals()функция, и между этими двумя функциями также соблюдается соглашение: еслиa.equals(b) == true, то a и b равныhashCode()также должно быть одинаковым.
Ниже приведен класс StringhashCode()функция, которая сначала проходит по внутреннему массиву символов, а затем вычисляет хеш-код в каждом цикле (умножает хэш-код на простое число и добавляет символ текущего элемента цикла):
/** The value is used for character storage. */
private final char value[];
/** Cache the hash code for the string */
private int hash; // Default to 0
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
HashMap не использует такой простой метод. Одна из причин заключается в том, что длина массива Bucket в HashMap всегда является степенью 2, а не простым числом. Если длина является простым числом, она может больше подходить для простого и насильственный метод деления и остатка (конечно, метод деления и остатка прост, но не так эффективен), кстати, хеш-таблица Tears of the Times использует метод деления и остатка, который не навязывает длину массива ведер.
HashMap внутренне реализуетhash()функция, перваяhashCode()Возвращаемое значение обрабатывается:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Эта функция будетkey.hashCode()Младшие 16 бит и старшие 16 бит выполняют операцию XOR, цель которой состоит в том, чтобы исказить младшую информацию для уменьшения коллизий. Затем необходимоhash()Возвращаемое значение такое же, какtable.length - 1выполнить операцию И (tableпредставляет собой массив сегментов), а результатом является нижний индекс массива.
table.length - 1Подобно низкоразрядной маске (эта конструкция также оптимизирует производительность операции раскрытия), она иhash()При выполнении операций AND старшие биты должны быть экранированы (поскольку HashMap не может иметь особенно большой массив сегментов, по крайней мере, это невозможно до непрерывного автоматического расширения, поэтомуtable.length - 1Большинство старших битов равны 0), а зарезервированы только младшие. Кажется, что в этом нет ничего плохого, но на самом деле это загадка. Это всегда приведет к тому, что действительными будут только самые младшие биты, поэтому даже если вашhashCode()Как бы хорошо это ни было реализовано, коллизий избежать сложно. В настоящее время,hash()Отражено значение функции, которая добавляет случайности младшим битам хеш-кода и смешивает некоторые черты старших битов, что значительно снижает возникновение конфликтов коллизий (околоhash()Как работает функция, вы можете обратиться к этой статьеAn introduction to optimising a hashing strategy).
Конкретный поток хеш-функции HashMap выглядит следующим образом:
Решение конфликта
Выше мы много раз упоминали конфликты коллизий, но хэш-функция не может быть идеальной, и не бывает ситуаций, когда распределение ключей является полностью однородным, поэтому конфликты коллизий всегда неизбежны.
Так что же происходит, когда происходит столкновение? Вы не можете всегда выбрасывать данные, верно? Должен быть разумный способ решить эту проблему.HashMap использует стратегию под названием «раздельная цепочка» (также переводится как «метод застежки-молнии») для разрешения конфликтов. Его основная идея заключается в том, что каждое ведро должно быть независимой структурой данных.В случае конфликта вам нужно только поместить данные в ведро (поскольку само ведро также является структурой данных, которая может хранить данные), чтобы запрос key Затраченное время — это время, затраченное на доступ к корзине, плюс время, затраченное на поиск в корзине.
Массив Buckets в HashMap на самом деле представляет собой массив связанных списков. Когда возникает конфликт, вам нужно только поместить Entry (помните Entry? Entry реализация HashMap — это простой узел связанного списка, который включает в себя ключ, значение и хэш-код) в конец связанного списка. , если нет конфликта (сегмент в нижнем индексе равен нулю), то используйте Entry в качестве заголовка связанного списка. И HashMap также использует ленивую стратегию, массив ведер будет вызываться только в первый раз.put()Инициализируйте функцию, это способ предотвратить трату памяти, так как ArrayList тоже ленивый, он вызывается в первый разadd()Внутренний массив инициализируется только тогда, когда
Однако, хотя связанный список прост в реализации, эффективность его поиска невелика.O(n), и большинство наших операций направлено вверх, вhashCode()Если дизайн не очень хорош, могут часто возникать конфликты коллизий, и связанный список будет становиться все длиннее и длиннее, что очень неэффективно. Его оптимизировала Java 8. Когда количество узлов в связанном списке достигает порога, он будет преобразован в красно-черное дерево, так что время, необходимое для поиска, составляет всегоO(log n)Порог определяется следующим образом:
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
Если обнаруживается, что связанный список превышает пороговое значение при вставке записи, будут выполнены следующие операции для дерева связанного списка; наоборот, если обнаружено, что красно-черное дерево имеет слишком мало узлов при удалении записи. (или расширенный) (в соответствии с порогом UNTREEIFY_THRESHOLD ), также вырождает красно-черное дерево в связанный список.
/**
* 替换指定hash所处位置的链表中的所有节点为TreeNode，
* 如果buckets数组太小，就进行扩容。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY = 64，小于该值代表数组中的节点并不是很多
// 所以选择进行扩容，只有数组长度大于该值时才会进行树化。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 转换链表节点为树节点，注意要处理好连接关系
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 从头部开始构造树
}
}
// 该函数定义在TreeNode中
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 初始化root节点
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 确定节点的方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 如果kc == null
// 并且k没有实现Comparable接口
// 或者k与pk是没有可比较性的（类型不同）
// 或者k与pk是相等的（返回0也有可能是相等）
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 确定方向后插入节点，修正红黑树的平衡
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
// 确保给定的root是该bucket中的第一个节点
moveRootToFront(tab, root);
}
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
// System.identityHashCode()将调用并返回传入对象的默认hashCode()
// 也就是说，无论是否重写了hashCode()，都将调用Object.hashCode()。
// 如果传入的对象是null，那么就返回0
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
Еще одна стратегия разрешения конфликтов коллизий называется открытой адресацией, которая сильно отличается от идеи раздельного связывания. В методе открытой адресации все записи будут храниться в массиве Bucket. Одно очевидное отличие состоит в том, что каждая корзина в методе раздельного связывания представляет собой связанный список или другую структуру данных, в то время как каждая корзина в методе открытой адресации представляет собой просто запись. сам.
Метод открытой адресации разрешает конфликты на основе вакансий в массиве.Идея его очень проста.Вместо использования таких структур данных, как связанные списки, лучше сразу оставлять вакансии в массиве как метку, которая все равно будет занимать лишнюю память .
Когда вы ищете ключ, он сначала начинается с начальной позиции (индекс массива, вычисленный хэш-функцией), и постоянно проверяет, является ли текущий сегмент целевой записью (судя по сравнению ключа), если текущий сегмент не целевой Entry, Затем ищите в обратном направлении (интервал поиска зависит от реализации), пока не встретите вакансию (null), а это значит, что искомый ключ не существует.
Если вы хотите поставить новую Запись (такого ключа в Карте нет), то поиск все равно начнется с начальной позиции, если начальная позиция не пуста, значит, произошел конфликт коллизий, и вы должны продолжайте поиск назад, пока не найдете вакансию.
От этого же происходит и название метода открытой адресации.Положение Записи не полностью определяется значением хеша, поэтому его также называют закрытым хешированием.Относительно метод разделительной ссылки также называется открытым хешированием или закрытой адресацией.
Существует множество различных реализаций метода открытой адресации в зависимости от алгоритма обратного зондирования (поиска).Мы вводим один из самых простых алгоритмов: Линейное зондирование, которое просто увеличивает индекс на единицу при возникновении коллизии. массива, если достигнут конец массива, пока не будет найдена цель или вакансия.
Поисковая операция, основанная на линейном методе обнаружения, выглядит следующим образом:
private K[] keys; // 存储key的数组
private V[] vals; // 存储值的数组
public V get(K key) {
// m是buckets数组的长度，即keys和vals的长度。
// 当i等于m时，取模运算会得0（折回数组头部）
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key))
return vals[i];
}
return null;
}
Операция вставки немного сложнее, и перед вставкой необходимо оценить оставшуюся емкость текущего массива, а затем решить, расширять ли емкость. Чем больше остаточная емкость массива, чем больше интервал между входами и чем раньше будет обнаружена вакансия (чем меньше количество обратных детектирований), тем, естественно, будет выше эффективность. Цена в том, что он потребляет больше памяти, которая также обменивает пространство на время.
public void put(K key, V value) {
// n是Entry的数量，如果n超过了数组长度的一半，就扩容一倍
if (n >= m / 2) resize(2 * m);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key)) {
vals[i] = value;
return;
}
}
// 没有找到目标，那么就插入一对新的Entry
keys[i] = key;
vals[i] = value;
n++;
}
Далее следует операция удаления.Следует отметить, что мы не можем просто установить положение целевого ключа (массив ключей и vals) равным нулю, что приведет к тому, что запись после этой позиции будет необнаруживаемой, поэтому нам нужно установить правую сторону Вся запись повторно вставляется в хеш-таблицу:
public V delete(K key) {
int i = hash(key);
// 先找到目标的索引
while (!key.equals(keys[i])) {
i = (i + 1) % m;
}
V oldValue = vals[i];
// 删除目标key和value
keys[i] = null;
vals[i] = null;
// 指针移动到下一个索引
i = (i + 1) % m;
while (keys[i] != null) {
// 先删除然后重新插入
K keyToRehash = keys[i];
V valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
n--;
// 当前Entry小于等于数组长度的八分之一时，进行缩容
if (n > 0 && n <= m / 8) resize(m / 2);
return oldValue;
}
Динамическое расширение
Хеш-таблица организует бакеты в виде массива.Проблема в том,что массив размещается статически.Чтобы обеспечить производительность поиска,нужно расширять емкость,когда количество записей больше критического значения В противном случае, даже если эффект от хеш-функции будет хорошим, неизбежно возникнут коллизии.
Так называемое расширение фактически заменяет текущий массив массивом большей емкости (умножая исходную емкость на два).Этот процесс требует повторного хеширования данных в старом массиве в новый массив, поэтому расширение может также быть замедленным до определенной степени столкновения.
HashMap вычисляет критическое значение путем умножения коэффициента загрузки (Load Factor) на длину массива ковшей.Алгоритм:threshold = load_factor * capacity. Например, начальная емкость HashMap по умолчанию равна 16 (capacity = 16), коэффициент загрузки по умолчанию равен 0,75 (load_factor = 0.75), то критическое значение равноthreshold = 0.75 * 16 = 12, если количество записей превышает 12, будет запущена операция расширения.
Вы также можете настроить коэффициент загрузки через следующие конструкторы.Чем меньше коэффициент загрузки, тем выше будет производительность поиска, но тем больше памяти будет занято при этом.Если нет особой необходимости, не рекомендуется изменить значение по умолчанию.
/**
* 可以发现构造函数中根本就没初始化buckets数组。
* （之前说过buckets数组会推迟到第一次调用put()时进行初始化）
*/
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;
// tableSizeFor()确保initialCapacity必须为一个2的N次方
this.threshold = tableSizeFor(initialCapacity);
}
Ограничение размера массива Bucket критически важно для всего HashMap.Чтобы предотвратить передачу целого числа, которое не является степенью 2, необходимо принять меры предосторожности.tableSizeFor()Функция попытается исправить целое число и преобразовать его в ближайшую степень числа 2 к этому целому числу.
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
Помните, как вычислялся индекс массива?index = (table.length - 1) & hash, на самом деле это метод оптимизации.Поскольку размер массива всегда равен степени 2, после расширения новый индекс элемента находится либо в исходной позиции, либо в исходной позиции плюс емкость до расширения. Гениальность этого метода заключается в операции &. Как упоминалось ранее, операция & будет фокусироваться только на значащих битах n - 1 (n = длина массива). Оно станет вдвое больше предыдущего значения, поэтому это очень важно чтобы длина массива всегда была степенью 2), и тогда вам нужно только определить, равен ли хэш 0 или 1 в позиции вновь добавленного значимого бита, чтобы вычислить новую позицию индекса. Если это 0 , то индекс не изменился.Если он равен 1, индекс равен исходному индексу плюс емкость до расширения.
Таким образом, нет необходимости пересчитывать хэш каждый раз, когда емкость расширяется, что экономит много времени, и независимо от того, является ли новый эффективный бит 0 или 1 случайным, и две ранее столкнувшиеся записи могут быть снова равномерно распределены. во время расширения емкости. Нижеresize()Исходный код:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table就是buckets数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap大于0，进行扩容，设置阈值与新的容量
if (oldCap > 0) {
// 超过最大值不会进行扩容，并且把阈值设置成Interger.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，扩容为原来的2倍
// 向左移1位等价于乘2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// oldCap = 0，oldThr大于0，那么就把阈值做为新容量以进行初始化
// 这种情况发生在用户调用了带有参数的构造函数（会对threshold进行初始化）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap与oldThr都为0，这种情况发生在用户调用了无参构造函数
// 采用默认值进行初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr还没有被赋值，那么就根据newCap计算出阈值
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;
// 如果oldTab != null，代表这是扩容操作
// 需要将扩容前的数组数据迁移到新数组
if (oldTab != null) {
// 遍历oldTab的每一个bucket，然后移动到newTab
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 索引j的bucket只有一个Entry（未发生过碰撞）
// 直接移动到newTab
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是一个树节点（代表已经转换成红黑树了）
// 那么就将这个节点拆分为lower和upper两棵树
// 首先会对这个节点进行遍历
// 只要当前节点的hash & oldCap == 0就链接到lower树
// 注意这里是与oldCap进行与运算，而不是oldCap - 1(n - 1)
// oldCap就是扩容后新增有效位的掩码
// 比如oldCap=16，二进制10000，n-1 = 1111，扩容后的n-1 = 11111
// 只要hash & oldCap == 0，就代表hash的新增有效位为0
// 否则就链接到upper树（新增有效位为1）
// lower会被放入newTab[原索引j]，upper树会被放到newTab[原索引j + oldCap]
// 如果lower或者upper树的节点少于阈值，会被退化成链表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 下面操作的逻辑与分裂树节点基本一致
// 只不过split()操作的是TreeNode
// 而且会将两条TreeNode链表组织成红黑树
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;
}
Еще одна вещь, которую следует отметить при использовании HashMap, заключается в том, что он не будет динамически сжиматься, то есть вы не должны хранить HashMap, который удалил много записей (если вы не планируете продолжать добавлять элементы), в это время его массив ведер проходы через Множественные расширения стали очень большими, что займет много бесполезной памяти.Преимущество этого в том, что массив не нужно расширять или уменьшать несколько раз. Однако, как правило, этого не происходит, если вы столкнулись с этим, пожалуйста, не раздумывая, выбросьте его или перенесите данные на новый HashMap.
добавить элемент
Мы уже поняли внутреннюю реализацию и принцип работы HashMap.Он поддерживает массив внутри, и каждый ключ будет передавать хэш-функцию, чтобы получить индекс в массиве.Если индексы двух ключей одинаковы, то разделительная ссылка Для решения проблемы используется метод Конфликт столкновений, когда количество Вхождений больше критического значения, массив расширяется.
Затем добавьте элемент сput()) процесс в качестве примера для сортировки знаний, следующий рисунокput()Блок-схема функции:
Затем исходный код:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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 or table.length == 0
// 第一次调用put()，初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 没有发生碰撞，直接放入到数组
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 发生碰撞（头节点就是目标节点）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 节点为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 节点为链表
else {
for (int binCount = 0; ; ++binCount) {
// 未找到目标节点，在链表尾部链接新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表过长，转换为红黑树
treeifyBin(tab, hash);
break;
}
// 找到目标节点，退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 节点已存在，替换value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeXXXXX是提供给LinkedHashMap重写的函数
// 在HashMap中没有意义
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过临界值，进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
WeakHashMap
WeakHashMap — это хеш-таблица на основе интерфейса Map, детали реализации аналогичны HashMap (есть коэффициенты загрузки, хеш-функции и т. д., но методов оптимизации не так много, как у HashMap). ключ является слабой цитатой.
Прежде всего, нам нужно понять, что такое слабая ссылка, Java делит ссылку на четыре категории (начиная с JDK1.2), и сила постепенно ослабевает:
-
Сильная ссылка: это обычный объект ссылки, который обычно используется, например
Object obj = new Object(), что является сильной ссылкой. Пока сильная ссылка все еще существует, она не будет собрана сборщиком мусора. -
Мягкая ссылка: Мягкая ссылка представляет объект, который все еще полезен, но не является обязательным.В отличие от сильной ссылки, он также должен косвенно ссылаться на целевой объект через класс SoftReference (за исключением сильных ссылок). Объект, связанный с мягкой ссылкой, будет помещен в диапазон повторного использования для второго повторного использования, прежде чем возникнет исключение переполнения памяти (если после второго повторного использования памяти все еще недостаточно, будет сгенерировано исключение OOM).
-
Слабая ссылка: она также представляет несущественный объект, но она слабее, чем мягкая ссылка, и на целевой объект необходимо косвенно ссылаться через класс WeakReference. Объекты, связанные со слабыми ссылками, могут существовать только до тех пор, пока не произойдет следующая сборка мусора.При запуске сборки мусора, независимо от того, достаточно ли текущей памяти, объекты, связанные только со слабыми ссылками, будут переработаны (если на объект все еще ссылаются сильные ссылки, тогда он не будет переработан).
-
Фантомная ссылка: это самая слабая ссылочная связь, и на целевой объект необходимо косвенно ссылаться через класс PhantomReference. Независимо от того, имеет ли объект виртуальную ссылку, это никак не повлияет на его время жизни, и экземпляр объекта не может быть получен через виртуальную ссылку. Единственной целью виртуальной ссылки является получение системного уведомления (используемого вместе с ReferenceQueue) при повторном использовании объекта. Исходя из этого, деструктор объекта можно реализовать через виртуальные ссылки, что лучше, чем использование
finalize()Функция намного надежнее.
WeakHashMap подходит для использования в качестве кэша. Предполагая, что ваша система кэширования реализована на основе сильных ссылок, вы должны вручную (или использовать поток для непрерывного опроса), чтобы удалить недопустимую запись кэша, в то время как записи кэша, реализованные на основе слабых ссылок, не используются другими ассоциациями объектов со строгой ссылкой, будут поставить прямо в очередь на переработку.
Следует отметить, что только ключ связан со слабой ссылкой, а значение обычно является объектом сильной ссылки. Поэтому необходимо следить, чтобы значение не было связано с его ключом, иначе это будет мешать восстановлению ключа. В крайних случаях объект-значение A ссылается на другой ключевой объект D, а объект-значение C, соответствующий D, в свою очередь, ссылается на ключевой объект B, соответствующий A, что создаст цикл ссылок, в результате чего ни D, ни B не могут быть перерабатывается нормально. Чтобы решить эту проблему, вы можете только превратить значение в слабую ссылку, напримерm.put(key, new WeakReference(value)), взаимные ссылки между слабыми ссылками не будут влиять друг на друга.
Реализация операции поиска намного проще, чем у HashMap. Пока вы понимаете HashMap, вы можете в основном понять его. Исходный код выглядит следующим образом:
/**
* Value representing null keys inside tables.
*/
private static final Object NULL_KEY = new Object();
/**
* Use NULL_KEY for key if it is null.
*/
private static Object maskNull(Object key) {
return (key == null) ? NULL_KEY : key;
}
/**
* Returns index for hash code h.
*/
private static int indexFor(int h, int length) {
return h & (length-1);
}
public V get(Object key) {
// WeakHashMap允许null key与null value
// null key会被替换为一个虚拟值
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
// 遍历链表
while (e != null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return null;
}
Несмотря на то, что ключ является слабой ссылкой, по-прежнему необходимо вручную повторно использовать запись, которая была признана недействительной. Эта операция будетgetTable()Выполняется в функции, будь то поиск, добавление или удаление, вам нужно вызватьgetTable()получить массив бакетов, так что это пассивная защита от утечек памяти.
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
Entry<K,V>[] table;
/**
* Reference queue for cleared WeakEntries
*/
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
/**
* Expunges stale entries from the table.
*/
private void expungeStaleEntries() {
// 遍历ReferenceQueue，然后清理table中无效的Entry
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;
int i = indexFor(e.hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = null; // Help GC
size--;
break;
}
prev = p;
p = next;
}
}
}
}
/**
* Returns the table after first expunging stale entries.
*/
private Entry<K,V>[] getTable() {
expungeStaleEntries();
return table;
}
Затем есть операции вставки и операции удаления, которые относительно просто реализовать:
public V put(K key, V value) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
if (h == e.hash && eq(k, e.get())) {
V oldValue = e.value;
if (value != oldValue)
e.value = value;
return oldValue;
}
}
modCount++;
Entry<K,V> e = tab[i];
// e被连接在new Entry的后面
tab[i] = new Entry<>(k, value, queue, h, e);
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
public V remove(Object key) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
if (h == e.hash && eq(k, e.get())) {
modCount++;
size--;
if (prev == e)
tab[i] = next;
else
prev.next = next;
return e.value;
}
prev = e;
e = next;
}
return null;
}
мы неput()В функции обнаружено, что ключ конвертируется в слабую ссылку, что происходит? Ключ нужно преобразовать в слабую ссылку только тогда, когда он помещается в массив ведер в первый раз, то естьnew Entry<>(k, value, queue, h, e), реализация WeakHashMap Entry на самом деле является подклассом WeakReference.
/**
* The entries in this hash table extend WeakReference, using its main ref
* field as the key.
*/
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next;
/**
* Creates new entry.
*/
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
@SuppressWarnings("unchecked")
public K getKey() {
return (K) WeakHashMap.unmaskNull(get());
}
public V getValue() {
return value;
}
public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
K k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
V v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public int hashCode() {
K k = getKey();
V v = getValue();
return Objects.hashCode(k) ^ Objects.hashCode(v);
}
public String toString() {
return getKey() + "=" + getValue();
}
}
Типичным случаем использования WeakReference является ThreadLocal, заинтересованные читатели могут обратиться к моему предыдущему блогу.Давайте поговорим о безопасности потоков в Spring.
LinkedHashMap
LinkedHashMap наследует HashMap и реализует интерфейс Map, а также имеет предсказуемый порядок итерации (отсортированный по порядку вставки). Отличие его от HashMap в том, что он поддерживает двусвязный список, который проходит через все его Entry (потому что дополнительно поддерживается связь связанного списка, производительность немного хуже, чем у HashMap, но время обхода представления коллекции пропорционально к количеству элементов, а HashMap пропорционален длине массива Buckets), его можно рассматривать как комбинацию хеш-таблицы и связанного списка.
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 迭代顺序模式的标记位，如果为true，采用访问排序，否则，采用插入顺序
* 默认插入顺序（构造函数中默认设置为false）
*/
final boolean accessOrder;
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
Реализация Entry LinkedHashMap также наследуется от HashMap, но есть еще два указателя спереди и сзади.
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
Вы также можете использовать конструктор для создания LinkedHashMap, порядок итерации которого является порядком доступа (accessOrder имеет значение true), который относится к порядку последней доступной записи (от наименее недавно доступной к самой последней доступной). Исходя из этого, кэш с использованием стратегии LRU (наименее недавно использованный) можно просто реализовать.
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap повторно использует большую часть кода HashMap, поэтому его реализация поиска очень проста, и лишь немногим более сложной операцией является обеспечение порядка доступа.
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
Помните эти функции в формате именования afterNodeXXXX? Мы видели это в HashMap раньше, эти функции являются просто пустой реализацией в HashMap, которая представляет собой функцию-ловушку, специально используемую для того, чтобы заставить LinkedHashMap переписать реализацию.
// 在HashMap.removeNode()的末尾处调用
// 将e从LinkedHashMap的双向链表中删除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
// 在HashMap.putVal()的末尾处调用
// evict是一个模式标记，如果为false代表buckets数组处于创建模式
// HashMap.put()函数对此标记设置为true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// LinkedHashMap.removeEldestEntry()永远返回false
// 避免了最年长元素被删除的可能（就像一个普通的Map一样）
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// HashMap.get()没有调用此函数，所以LinkedHashMap重写了get()
// get()与put()都会调用afterNodeAccess()来保证访问顺序
// 将e移动到tail，代表最近访问到的节点
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
УведомлениеremoveEldestEntry()По умолчанию всегда возвращается false, и его поведение такое же, как и у обычной карты. если вы положитеremoveEldestEntry()Переписано, чтобы всегда возвращать true, тогда можно оставить LinkedHashMap в состоянии, которое всегда пусто (каждый разput()илиputAll()удалит головной узел).
Более разумный пример реализации:
protected boolean removeEldestEntry(Map.Entry eldest){
return size() > MAX_SIZE;
}
LinkedHashMap переписанnewNode()и другие функции для инициализации или подключения узла к его внутреннему двусвязному списку:
// 链接节点p到链表尾部（或初始化链表）
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
// 用dst替换掉src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
// src是头节点
if (b == null)
head = dst;
else
b.after = dst;
// src是尾节点
if (a == null)
tail = dst;
else
a.before = dst;
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
Время, необходимое для обхода LinkedHashMap, пропорционально количеству Entry, поскольку итератор напрямую выполняет итерацию по двусвязному списку, а связанный список содержит только узлы Entry. Порядок итерации - от головного узла к хвостовому узлу.Операция вставки свяжет новый узел с хвостом, поэтому порядок вставки гарантируется, а порядок доступа будет проходить черезafterNodeAccess()Чтобы узлы с большим количеством посещений были ближе к хвосту.
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
ConcurrentHashMap
Упомянутые выше Карты не являются потокобезопасными, а это означает, что эти Карты не должны изменяться в нескольких потоках, что может привести к несогласованности данных и даже к зацикливанию связанного списка из-за одновременной вставки элементов. вызовет расширение, и операция расширения должна перефразировать элементы исходного массива в новый массив. В это время параллельная операция может создать циклическую ссылку на связанный список и сформировать цикл), поэтому произойдет бесконечный цикл во время поиска, влияя на все приложение.
Collections.synchronizedMap(Map<K,V> m)Map можно преобразовать в потокобезопасную реализацию, по сути, через класс-оболочку, и тогда все функции делегируются входящей реализации Map, а класс-оболочка основан наsynchronizedключевое слово для обеспечения безопасности потоков (эра слез Hashtable также основана наsynchronizedключевое слово), нижний слой использует блокировку мьютекса (доступ к нему возможен только у потока, одновременно удерживающего блокировку, другие конкурирующие потоки переходят в спящий режим), а производительность и пропускная способность неудовлетворительны.
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
............
}
Однако детали реализации ConcurrentHashMap далеко не простые, поэтому производительность намного выше. Он не использует глобальную блокировку, чтобы заблокировать себя, но использует метод уменьшения детализации блокировки, чтобы свести к минимуму блокировки и конфликты, вызванные конкурирующими блокировками, а операция извлечения ConcurrentHashMap не требует блокировок.
В Java 7 ConcurrentHashMap разделяет внутреннюю часть на несколько небольших HashMap, называемых Segments, которые по умолчанию разделены на 16 сегментов. Для операции записи к ней сначала будет обращаться по хеш-коду, чтобы узнать, в каком сегменте должна храниться Entry, а затем просто блокировать сегмент.
В идеале ConcurrentHashMap по умолчанию может одновременно принимать 16 потоков для операций записи (если все они работают в разных сегментах).
блокировка сегмента дляsize()Такая глобальная операция не имеет никакого эффекта.Чтобы получить количество Entry, вам нужно пройти все сегменты, получить все блокировки, а затем подсчитать общее количество. На самом деле, ConcurrentHashMap сначала попытается посчитать общее количество безблокировочным способом, и эта попытка будет предпринята 3 раза, если времена modCount сегментов, полученные в двух соседних вычислениях, совпадают, это означает, что ни один из этих произошло два вычисления. Если вы измените операцию, вы можете вернуть ее как окончательный результат. В противном случае вы должны получить блокировки всех сегментов и пересчитать размер.
В этой статье в основном обсуждается ConcurrentHashMap в Java 8, который сильно отличается от реализации в Java 7. Полностью отказался от дизайна сегментов, но вернулся к дизайну, аналогичному HashMap, с использованием массива бакетов и метода разделения ссылок (также древовидность при превышении порога, логика построения красно-черных деревьев не сильно отличается от HashMap, но требует дополнительных использование CAS для обеспечения безопасности потоков), степень детализации блокировки также подразделяется на каждый элемент массива (я лично думаю, что причина этого в том, что HashMap также реализовал множество оптимизаций в Java 8, даже если коллизия серьезная, он также может гарантировать определенную производительность, а Segment не только раздут, но и имеет слабые проблемы с согласованностью), поэтому его уровень параллелизма связан с длиной массива (Java 7 связан с количеством сегментов).
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
*/
transient volatile Node<K,V>[] table;
обращение
Хеш-функция ConcurrentHashMap ничем не отличается от HashMap, она также выполняет операцию XOR над старшими 16 битами и младшими 16 битами хеш-кода ключа (поскольку длина массива сегментов ConcurrentHashMap всегда является степенью двойки). , а затем выполните операцию И над зашифрованным хэш-кодом и длиной массива минус один (фактический максимальный индекс, к которому можно получить доступ), и результатом будет расположение цели.
// 2^31 - 1，int类型的最大值
// 该掩码表示节点hash的可用位，用来保证hash永远为一个正整数
static final int HASH_BITS = 0x7fffffff;
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
Ниже приведен исходный код операции поиска, реализация относительно проста.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
// 先尝试判断链表头是否为目标，如果是就直接返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
// eh < 0代表这是一个特殊节点（TreeBin或ForwardingNode）
// 所以直接调用find()进行遍历查找
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历链表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Хэш обычного узла (узла связанного списка) не может быть меньше 0 (уже вspread()Функция была исправлена), поэтому значение меньше 0 может быть только специальным узлом, который нельзя обойти путем обхода связанного списка в цикле while.
TreeBin — головной узел красно-черного дерева (узел красно-черного дерева — TreeNode), который сам по себе не содержит ключа и значения, а указывает на связанный список узлов TreeNode и их корневых узлов, при использовании CAS (ConcurrentHashMap не полностью основан на реализации мьютекса, но используется в сочетании с оптимистичной стратегией CAS для повышения производительности) реализует блокировку чтения-записи, вынуждая модуль записи (удерживающий эту блокировку) ждать завершения чтения перед тем, как операция по восстановлению дерева.
ForwardingNode — это временный узел, используемый в процессе передачи данных (вызванный расширением), он будет вставлен в заголовок. Это подкласс класса Node вместе с TreeBin (и TreeNode).
Чтобы определить, какие узлы являются особыми, хеш-поля TreeBin и ForwardingNode являются просто фиктивными значениями:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
......
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
/*
* Encodings for Node hash fields. See above for explanation.
*/
static final int MOVED = -1; // hash for forwarding nodes
static final int TREEBIN = -2; // hash for roots of trees
static final int RESERVED = -3; // hash for transient reservations
static final class TreeBin<K,V> extends Node<K,V> {
....
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
....
}
....
}
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
.....
}
видимость
мы вget()В функции не найден код, связанный с блокировкой, так как же она обеспечивает потокобезопасность? ОперацияConcurrentHashMap.get("a"), его шаги в основном делятся на следующие шаги:
-
Доступ к таблице осуществляется по индексу, вычисляемому хэш-функцией.
-
Удалить головной узел из таблицы.
-
Перемещайтесь по головному узлу, пока не будет найден целевой узел.
-
Возьмите значение из целевого узла и верните его.
Поэтому до тех пор, пока вы гарантируете, что операции доступа к таблицам и узлам всегда могут возвращать самые последние данные. ConcurrentHashMap не использует блокировки, а черезvolatileключевые слова, чтобы обеспечить их видимость. Как вы можете видеть в приведенном выше коде, table, Node.val и Node.next всеvolatileИзменено по ключевому слову.
volatileКлючевые слова обеспечивают видимость и порядок переменных в многопоточной среде, а базовая реализация основана на барьере памяти.
В целях оптимизации производительности порядок выполнения инструкций современных ЦП фактически несовместим с порядком кода приложения (некоторые компиляторы также выполняют эту оптимизацию), что представляет собой так называемую технологию выполнения вне порядка. Выполнение вне очереди может повысить эффективность работы конвейера ЦП, если данные соответствуют правильности логики программы (следуяhappens-beforeв общем). Но в сегодняшнюю многоядерную эпоху будет проблемой случайный беспорядок без обеспечения мер защиты. Оптимизация не по порядку будет выполняться на каждом ЦП, и логический порядок, гарантированный одним ЦП, может быть нарушен другими ЦП.
Барьер памяти является защитой от этой ситуации. Думайте об этом как о точке синхронизации (но это также и сама инструкция процессора). Например, вIA32Введен в архитектуру набора инструкцийSFENCEинструкции, все операции записи перед этой инструкцией должны быть завершены, а операции чтения все еще могут выполняться не по порядку.LFENCEИнструкция гарантирует, что все предыдущие операции чтения должны быть завершены, и есть более грубыеMFENCEИнструкция гарантирует, что все предыдущие операции чтения и записи должны быть завершены.
Барьер памяти подобен забору, который защищает порядок инструкций, защищая последующие инструкции от пересечения предыдущими инструкциями. Вставка барьера памяти между операциями записи и операциями чтения гарантирует, что последующие операции чтения могут получить доступ к самым последним данным, потому что операция записи перед барьером уже записала данные обратно в память (согласно протоколу когерентности кэша, это не прямая обратная запись). в память, но измените состояние в личном кеше процессора, а затем уведомите другой процессор о том, что строка кеша была изменена, а затем другой процессор может обнаружить, что строка кеша недействительна во время операции чтения, когда он читает последнюю строку кеша. от другого ЦП до того, как предыдущий ЦП изменит состояние и запишет обратно в память).
Например, чтениеvolatileДекорированная переменная V всегда может получить последние данные из основной памяти JMM (модель памяти Java). Из-за барьера памяти каждый раз, когда используется переменная V (через инструкцию JVMuse, все инструкции в JVM, а не в процессоре), должны быть выполнены доloadИнструкция (поместить данные, полученные из основной памяти, в рабочую память), согласно регламенту JVM,loadИнструктаж должен проходить вreadПосле инструкции (чтение данных из основной памяти), поэтому каждый доступ к переменной V будет сначала читаться из основной памяти. Напротив, операция записи также каждый раз записывается непосредственно обратно в основную память из-за порядка инструкций, гарантированного барьером памяти.
ноvolatileКлючевое слово не гарантирует атомарность операции. Параллельные непрерывные операции над переменной не потокобезопасны. К счастью, ConcurrentHashMap используется только для обеспечения актуальности используемых переменных, поэтому проблем не возникнет.
Из соображений производительности Дуг Ли (java.util.concurrentАвтор пакета) работает с таблицей напрямую через класс Unsafe.
Java претендует на звание безопасного языка программирования, и ценой обеспечения безопасности является отказ программиста от возможности свободно манипулировать памятью. Например, в C/C++ вы можете манипулировать памятью, манипулируя переменными-указателями (фактически манипулируют виртуальными адресами), но такая гибкость часто приводит к некоторым глупым ошибкам в руках новичков, таких как неограниченный доступ к памяти.
Unsafe буквально небезопасен, он содержит много нативных методов (программы, написанные на других языках, работающие на платформе JVM, в основном C/C++,JNIреализация), эти методы поддерживают операции над указателями, поэтому он называется небезопасным. Хоть это и небезопасно, но все же реализовано на C/C++, и некоторые операции, которые взаимодействуют с операционной системой, определенно быстрее, чем Java.В конце концов, между Java и операционной системой существует слой абстракции (JVM), но цена теряется.Многоплатформенная переносимость, принесенная JVM (по сути, просто файл c/cpp, если платформа изменена, его необходимо перекомпилировать).
Следующие три функции работают с таблицами, и все они используют Unsafe (вjava.util.concurrentпакеты везде):
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// 从tab数组中获取一个引用，遵循Volatile语义
// 参数2是一个在tab中的偏移量，用来寻找目标对象
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
// 通过CAS操作将tab数组中位于参数2偏移量位置的值替换为v
// c是期望值，如果期望值与实际值不符，返回false
// 否则，v会成功地被设置到目标位置，返回true
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
// 设置tab数组中位于参数2偏移量位置的值，遵循Volatile语义
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
Если вас интересует Unsafe, вы можете обратиться к этой статье:Java Magic. Part 4: sun.misc.Unsafe
инициализация
ConcurrentHashMap ленив, как и HashMap, доступ к массиву ведер будет осуществляться в первый раз.put()функция, ее конструктор по умолчанию даже является пустой функцией.
/**
* Creates a new, empty map with the default initial table size (16).
*/
public ConcurrentHashMap() {
}
Но следует отметить, что ConcurrentHashMap работает в многопоточной параллельной среде, если несколько потоков вызываются одновременно.put()Что должна делать функция? Это приведет к повторной инициализации, поэтому должны быть соответствующие меры защиты.
ConcurrentHashMap объявляет переменную экземпляра sizeCtl, используемую для управления инициализацией и расширением таблицы, и значением по умолчанию является 0. Когда это отрицательное число, это означает, что таблица находится в состоянии инициализации или расширения.-1Указывает, что таблица инициализируется,-NЭто означает, что в настоящее время имеется N-1 поток, в котором происходит увеличение емкости.
В других случаях, если таблица не была инициализирована (table == null), sizeCtl указывает размер массива для инициализации таблицы (таким образом, InitialCapacity, переданный из конструктора, будет присвоен ему после вычисления). Если таблица была инициализирована, это указывает на порог запуска следующей операции раскрытия.АлгоритмstzeCtl = n - (n >>> 2), что составляет 75% от n, что соответствует HashMap с коэффициентом загрузки по умолчанию (0,75).
private transient volatile int sizeCtl;
Операция инициализации таблицы находится в функцииinitTable(), исходный код выглядит следующим образом:
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// sizeCtl小于0，这意味着已经有其他线程进行初始化了
// 所以当前线程让出CPU时间片
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// 否则，通过CAS操作尝试修改sizeCtl
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// 默认构造函数，sizeCtl = 0，使用默认容量（16）进行初始化
// 否则，会根据sizeCtl进行初始化
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 计算阈值，n的75%
sc = n - (n >>> 2);
}
} finally {
// 阈值赋给sizeCtl
sizeCtl = sc;
}
break;
}
}
return tab;
}
sizeCtl — этоvolatileПеременная, пока операция потока CAS выполняется успешно, sizeCtl будет временно изменен на -1, чтобы другие потоки могли знать, была ли таблица инициализирована в соответствии с sizeCtl, и, наконец, sizeCtl будет установлен в качестве порога для запуска операции расширения. .
Расширение
Время срабатывания расширения ConcurrentHashMap аналогично таковому для HashMap, либо при преобразовании связанного списка в красно-черное дерево, чтобы определить, меньше ли длина массива таблиц порогового значения (64). Вход превышает порог, и если это так, расширяйте возможности.
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// 小于MIN_TREEIFY_CAPACITY，进行扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
// 将链表转换成红黑树...
}
}
}
}
...
final V putVal(K key, V value, boolean onlyIfAbsent) {
...
addCount(1L, binCount); // 计数
return null;
}
private final void addCount(long x, int check) {
// 计数...
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// s(元素个数)大于等于sizeCtl，触发扩容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 扩容标志位
int rs = resizeStamp(n);
// sizeCtl为负数，代表正有其他线程进行扩容
if (sc < 0) {
// 扩容已经结束，中断循环
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 进行扩容，并设置sizeCtl，表示扩容线程 + 1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 触发扩容（第一个进行扩容的线程）
// 并设置sizeCtl告知其他线程
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
// 统计个数，用于循环检测是否还需要扩容
s = sumCount();
}
}
}
Видно, что операция sizeCtl включает в себя большое количество битовых операций, давайте сначала разберемся в значении этих битовых операций. прежде всегоresizeStamp(), эта функция возвращает бит флага для проверки данных, что означает расширение таблицы длины n. Он принимает начальные нули n (количество нулей перед старшим битом) и1 << 15Выполните операцию ИЛИ, в это время старший бит из младших 16 бит равен 1, а остальные являются ведущими нулями n.
static final int resizeStamp(int n) {
// RESIZE_STAMP_BITS = 16
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
Алгоритм инициализации sizeCtl (операция расширения выполняется в первый раз первым потоком) таков:(rs << RESIZE_STAMP_SHIFT) + 2,Во-первыхRESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS = 16,Такrs << 16Это эквивалентно перемещению бита флага в старшие 16 бит.В это время старший бит равен 1, поэтому sizeCtl в это время является отрицательным числом, а затем добавить два (что касается того, почему это 2, помните описание о sizeCtl?1 представляет собой состояние инициализации, поэтому фактическое количество потоков, которое нужно вычесть из 1), означает, что в настоящее время существует поток, который расширяется,
Таким образом, sizeCtl делится на две части: старшие 16 бит — это бит флага для проверки данных n, а младшие 16 бит указывают количество потоков, участвующих в операции расширения + 1.
Некоторых читателей может смутить, зачем операция обновления количества потоков для расширения?sc + 1вместоsc - 1, это связано с тем, что все операции над sizeCtl основаны на битовых операциях, поэтому их не волнует собственное значение, а только его значение в двоичном формате, иsc + 1добавит 1 к младшим 16 битам.
tryPresize()функция сaddCount()Вторая половина логики аналогична, постоянно судить о текущем состоянии по sizeCtl, а затем выбирать соответствующую стратегию.
private final void tryPresize(int size) {
// 对size进行修正
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
// sizeCtl是默认值或正整数
// 代表table还未初始化
// 或还没有其他线程正在进行扩容
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
// 设置sizeCtl，告诉其他线程，table现在正处于初始化状态
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
// 计算下次触发扩容的阈值
sc = n - (n >>> 2);
}
} finally {
// 将阈值赋给sizeCtl
sizeCtl = sc;
}
}
}
// 没有超过阈值或者大于容量的上限，中断循环
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
// 进行扩容，与addCount()后半段的逻辑一致
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
Суть операции расширения заключается в передаче данных.В однопоточной среде передача данных очень проста.Это не что иное, как перенос данных из старого массива в новый массив. Однако это не работает в многопоточной среде. Это необходимо для обеспечения безопасности потоков. Во время расширения другие потоки также могут добавлять элементы. Что делать, если расширение сработало? Кто-то может сказать, что это несложно, почему бы не заблокировать процесс операции передачи данных мьютексом? Это действительно жизнеспособный обходной путь, но также приводит к чрезвычайно низкой пропускной способности.
Блокировки мьютексов приведут к блокировке всех потоков, обращающихся к критическому разделу, что потребует дополнительных системных ресурсов. Ядру необходимо сохранить контекст этих потоков и поместить их в очередь блокировки. Чем дольше длится поток, удерживающий блокировку, тем больше конкурирующие потоки будут постоянно блокироваться, поэтому пропускная способность будет низкой, что приведет к увеличению времени отклика. И блокировки всегда сопровождаются проблемами взаимоблокировки.После возникновения взаимоблокировки это повлияет на все приложение, поэтому блокировка всегда является последним вариантом.
Дуг Леа не выбрал блокировку напрямую, а реализовал стратегию параллельной синхронизации без блокировки на основе CAS.Примечательно, что он не только не отключил другие потоки, но даже пригласил их для помощи в работе.
Так как же заставить несколько потоков работать вместе? Дуг Ли рассматривает весь массив таблиц как очередь задач, совместно используемую несколькими потоками, и затем ему нужно только поддерживать указатель.Когда поток начинает передавать данные, он сначала перемещает указатель, указывая, что область корзины, которую пересекает указатель, контролируется потоком.
Этот указатель объявляется какvolatileЦелочисленная переменная, начальная позиция которой находится в конце таблицы, т.е. она равнаtable.length, очевидно, что эта очередь задач проходится в обратном порядке.
/**
* The next table index (plus one) to split while resizing.
*/
private transient volatile int transferIndex;
/**
* 一个线程需要负责的最小bucket数
*/
private static final int MIN_TRANSFER_STRIDE = 16;
/**
* The next table to use; non-null only while resizing.
*/
private transient volatile Node<K,V>[] nextTable;
Бакет, который был перенесен, будет заменен узлом ForwardingNode, чтобы отметить, что бакет был перенесен другими потоками. Ранее мы упоминали ForwardingNode, это специальный узел, который можно идентифицировать по фиктивному значению хеш-поля, он также перезаписываетfind()Функция для поиска цели в новом массиве.
Операция переноса данных находится вtransfer()Функция, несколько потоков полагаются на указатели sizeCtl и transferIndex для совместной работы, каждый поток имеет свою собственную область, ведро, которое завершило миграцию, будет установлено как ForwardingNode, другие потоки пропустят ведро, когда они столкнутся с этим специальным узлом, и обработают следующий ведро.
transfer()Функцию можно условно разделить на три части.Первая часть инициализирует переменные, которые необходимо использовать позже:
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 根据当前机器的CPU数量来决定每个线程负责的bucket数
// 避免因为扩容线程过多，反而影响到性能
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 初始化nextTab，容量为旧数组的一倍
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; // 初始化指针
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
Вторая часть назначает задачи текущему потоку и контролирует ход выполнения задачи текущего потока.transfer()Основная логика описывает, как работать с другими потоками:
// i指向当前bucket，bound表示当前线程所负责的bucket区域的边界
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 这个循环使用CAS不断尝试为当前线程分配任务
// 直到分配成功或任务队列已经被全部分配完毕
// 如果当前线程已经被分配过bucket区域
// 那么会通过--i指向下一个待处理bucket然后退出该循环
while (advance) {
int nextIndex, nextBound;
// --i表示将i指向下一个待处理的bucket
// 如果--i >= bound，代表当前线程已经分配过bucket区域
// 并且还留有未处理的bucket
if (--i >= bound || finishing)
advance = false;
// transferIndex指针 <= 0 表示所有bucket已经被分配完毕
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// 移动transferIndex指针
// 为当前线程设置所负责的bucket区域的范围
// i指向该范围的第一个bucket，注意i是逆向遍历的
// 这个范围为(bound, i)，i是该区域最后一个bucket，遍历顺序是逆向的
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 当前线程已经处理完了所负责的所有bucket
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 如果任务队列已经全部完成
if (finishing) {
nextTable = null;
table = nextTab;
// 设置新的阈值
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 工作中的扩容线程数量减1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// (resizeStamp << RESIZE_STAMP_SHIFT) + 2代表当前有一个扩容线程
// 相对的，(sc - 2) != resizeStamp << RESIZE_STAMP_SHIFT
// 表示当前还有其他线程正在进行扩容，所以直接返回
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 否则，当前线程就是最后一个进行扩容的线程
// 设置finishing标识
finishing = advance = true;
i = n; // recheck before commit
}
}
// 如果待处理bucket是空的
// 那么插入ForwardingNode，以通知其他线程
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 如果待处理bucket的头节点是ForwardingNode
// 说明此bucket已经被处理过了，跳过该bucket
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
Последняя часть — конкретный процесс миграции (для текущей корзины), логика этой части аналогична логике HashMap, в качестве маски используется емкость старого массива, а затем выполняется операция И с хэшем узла, чтобы получить новый узел.Действительный бит, если вновь добавленный действительный бит равен 0, поместите его в связанный список A, если он равен 1, поместите его в другой связанный список B, позиция связанного списка A в новом массиве остается неизменным (тот же, что и индекс в старом массиве), связанный список B Позиция в новом массиве равна исходному индексу плюс емкость старого массива.
Этот метод уменьшает количество вычислений повторного хеширования и может достичь цели равномерного распределения.Если вы не можете понять, см. объяснение операции расширения HashMap в этой статье.
else {
// 对于节点的操作还是要加上锁的
// 不过这个锁的粒度很小，只锁住了bucket的头节点
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// hash code不为负，代表这是条链表
if (fh >= 0) {
// fh & n 获得hash code的新增有效位，用于将链表分离成两类
// 要么是0要么是1，关于这个位运算的更多细节
// 请看本文中有关HashMap扩容操作的解释
int runBit = fh & n;
Node<K,V> lastRun = f;
// 这个循环用于记录最后一段连续的同一类节点
// 这个类别是通过fh & n来区分的
// 这段连续的同类节点直接被复用，不会产生额外的复制
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// 0被放入ln链表，1被放入hn链表
// lastRun是连续同类节点的起始节点
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
// 将最后一段的连续同类节点之前的节点按类别复制到ln或hn
// 链表的插入方向是往头部插入的，Node构造函数的第四个参数是next
// 所以就算遇到类别与lastRun一致的节点也只会被插入到头部
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// ln链表被放入到原索引位置，hn放入到原索引 + 旧数组容量
// 这一点与HashMap一致，如果看不懂请去参考本文对HashMap扩容的讲解
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd); // 标记该bucket已被处理
advance = true;
}
// 对红黑树的操作，逻辑与链表一样，按新增有效位进行分类
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 元素数量没有超过UNTREEIFY_THRESHOLD，退化成链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
считать
В Java 7 ConcurrentHashMap считает каждый сегмент отдельно, если вы хотите получить общее количество, вам нужно получить блокировки всех сегментов, а затем их посчитать. Поскольку в Java 8 отсутствовал сегмент, очевидно, что сделать это больше невозможно, и, хотя этот подход прост и точен, он жертвует производительностью.
Java 8 объявляетvolatileПеременная baseCount используется для записи количества элементов. Операция модификации этой переменной основана на CAS. Она будет вызываться всякий раз, когда элемент вставляется или удаляется.addCount()функция для подсчета.
private transient volatile long baseCount;
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 尝试使用CAS更新baseCount失败
// 转用CounterCells进行更新
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
// 在CounterCells未初始化
// 或尝试通过CAS更新当前线程的CounterCell失败时
// 调用fullAddCount()，该函数负责初始化CounterCells和更新计数
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
// 统计总数
s = sumCount();
}
if (check >= 0) {
// 判断是否需要扩容，在上文中已经讲过了
}
}
counterCells — это массив с элементом CounterCell, размер массива связан с количеством процессоров текущей машины, и он не будет активно инициализироваться, только после вызоваfullAddCount()функция будет инициализирована.
CounterCell — это простой внутренний статический класс, каждая CounterCell — это ячейка для записи количества:
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;
/**
* A padded cell for distributing counts. Adapted from LongAdder
* and Striped64. See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
аннотация@sun.misc.ContendedИспользуется для решения проблемы ложного обмена. Так называемое ложное совместное использование означает, что несколько переменных хранятся в одной и той же строке кэша (базовой единице кэша ЦП).Когда одна из переменных изменяется, это влияет на другие переменные в той же строке кэша, заставляя их отмечены соответствующим образом. При аннулировании будет затронута частота попаданий в кэш других переменных. Способ решить проблему ложного совместного использования, как правило, состоит в том, чтобы заполнить переменную некоторыми бессмысленными данными-заполнителями, чтобы у нее была эксклюзивная строка кэша.
Схема подсчета ConcurrentHashMap аналогична LongAdder. В случае низкого параллелизма просто используйте операцию CAS для обновления baseCount, но если операция CAS дает сбой один раз, это означает, что несколько потоков конкурируют, тогда для подсчета используется массив CounterCell.Каждый счетчик CounterCell является независимым счетная ячейка.
Каждая нить будет проходитьThreadLocalRandom.getProbe() & mАдрес, чтобы найти принадлежащую ему CounterCell, а затем подсчитать. ThreadLocalRandom — это частный генератор псевдослучайных чисел для потока, и зонд каждого потока отличается (это основано на внутренней реализации ThreadLocalRandom, которая внутренне поддерживает probeGenerator, который является статической константой типа AtomicInteger, всякий раз, когда при инициализации ThreadLocalRandom, probeGenerator сначала увеличивает константу, а затем возвращаемое целое число является зондом текущего потока. Переменная зонда сохраняется в объекте Thread. Можно считать, что зондом каждого потока является его хэш-код в CounterCell. множество.
Этот метод разделяет конкурирующие данные в соответствии с гранулярностью потоков.По сравнению со всеми конкурирующими потоками использование CAS для общей переменной более эффективно с точки зрения производительности.Вот почему LongAdder лучше, чем AtomicInteger, в среде с высокой степенью параллелизма.
fullAddCount()Функция находит соответствующий CounterCell по зонду текущего потока и считает его, если массив CounterCell не инициализирован, инициализирует массив CounterCell и CounterCell. Реализация этой функции такая же, как у класса Striped64 (родительский класс LongAdder).longAccumulate()Функция та же самая, обрабатывайте массив CounterCell как хеш-таблицу, зондом каждого потока является хэш-код, а хэш-функция очень проста.(n - 1) & probe.
Размер массива Countercell всегда равен N-кратному 2. Начальная емкость равна 2. Новая емкость каждого расширения умножается на 2. Это производительность, верхний предел максимальной емкости — это количество процессоров машины.
Таким образом, конфликт коллизий массива CounterCell очень серьезен, потому что его мощность корзины слишком мала. Коллизия означает, что CounterCell будет конкурировать с несколькими потоками. Чтобы решить эту проблему, Дуг Ли использует бесконечный цикл плюс CAS для имитации спин-блокировки для обеспечения безопасности потоков. Реализация спин-блокировки основана наvolatileМодифицированная целочисленная переменная, переменная может иметь только два состояния: 0 и 1, когда она установлена в 0, это означает, что она не заблокирована, а когда она установлена в 1, это означает, что она была заблокирована другими потоками. Эта спин-блокировка используется для защиты безопасности инициализации CounterCell, инициализации массива CounterCell и расширения массива CounterCell.
Счетчик обновлений CounterCell зависит от CAS, каждый цикл будет пытаться обновляться через CAS, в случае успеха выход из бесконечного цикла, в противном случае вызовThreadLocalRandom.advanceProbe()Функция обновляет зонд для текущего потока, а затем перезапускает цикл, надеясь, что следующий адрес CounterCell не будет оспорен другими потоками.
Если два последовательных обновления CAS не увенчались успехом, массив CounterCell будет расширен один раз.Эта операция расширения будет запущена только один раз в текущем цикле и может быть запущена только тогда, когда емкость меньше верхнего предела.
fullAddCount()Основной поток функции выглядит следующим образом:
-
Сначала проверьте, инициализировал ли текущий поток ThreadLocalRandom, если нет, инициализируйте его. ThreadLocalRandom отвечает за обновление зонда потока, который, в свою очередь, является ключом к адресации в массиве.
-
Проверить, был ли инициализирован массив CounterCell.Если он был инициализирован, найти соответствующий CounterCell по зонду.
-
Если эта CounterCell равна нулю, вам нужно сначала инициализировать CounterCell, передав приращение счетчика конструктору, поэтому, если инициализация прошла успешно, это означает, что счетчик обновлений завершен. Процесс инициализации должен получить спин-блокировку.
-
Если он не нулевой, счетчик обновлений реализуется в CounterCell в соответствии с логикой, описанной выше.
-
-
Массив CounterCell не инициализирован, попробуйте получить спин-блокировку и инициализировать его. Процесс инициализации массива также инициализирует CounterCell для записи приращения счетчика, поэтому, если инициализация прошла успешно, счетчик обновления завершен.
-
Если спин-блокировка занята другими потоками, инициализация массива не может быть выполнена, и baseCount приходится обновлять через CAS.
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
// 当前线程的probe等于0，证明该线程的ThreadLocalRandom还未被初始化
// 以及当前线程是第一次进入该函数
if ((h = ThreadLocalRandom.getProbe()) == 0) {
// 初始化ThreadLocalRandom，当前线程会被设置一个probe
ThreadLocalRandom.localInit(); // force initialization
// probe用于在CounterCell数组中寻址
h = ThreadLocalRandom.getProbe();
// 未竞争标志
wasUncontended = true;
}
// 冲突标志
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
// CounterCell数组已初始化
if ((as = counterCells) != null && (n = as.length) > 0) {
// 如果寻址到的Cell为空，那么创建一个新的Cell
if ((a = as[(n - 1) & h]) == null) {
// cellsBusy是一个只有0和1两个状态的volatile整数
// 它被当做一个自旋锁，0代表无锁，1代表加锁
if (cellsBusy == 0) { // Try to attach new Cell
// 将传入的x作为初始值创建一个新的CounterCell
CounterCell r = new CounterCell(x); // Optimistic create
// 通过CAS尝试对自旋锁加锁
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 加锁成功，声明Cell是否创建成功的标志
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
// 再次检查CounterCell数组是否不为空
// 并且寻址到的Cell为空
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
// 将之前创建的新Cell放入数组
rs[j] = r;
created = true;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 如果已经创建成功，中断循环
// 因为新Cell的初始值就是传入的增量，所以计数已经完毕了
if (created)
break;
// 如果未成功
// 代表as[(n - 1) & h]这个位置的Cell已经被其他线程设置
// 那么就从循环头重新开始
continue; // Slot is now non-empty
}
}
collide = false;
}
// as[(n - 1) & h]非空
// 在addCount()函数中通过CAS更新当前线程的Cell进行计数失败
// 会传入wasUncontended = false，代表已经有其他线程进行竞争
else if (!wasUncontended) // CAS already known to fail
// 设置未竞争标志，之后会重新计算probe，然后重新执行循环
wasUncontended = true; // Continue after rehash
// 尝试进行计数，如果成功，那么就退出循环
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
// 尝试更新失败，检查counterCell数组是否已经扩容
// 或者容量达到最大值（CPU的数量）
else if (counterCells != as || n >= NCPU)
// 设置冲突标志，防止跳入下面的扩容分支
// 之后会重新计算probe
collide = false; // At max size or stale
// 设置冲突标志，重新执行循环
// 如果下次循环执行到该分支，并且冲突标志仍然为true
// 那么会跳过该分支，到下一个分支进行扩容
else if (!collide)
collide = true;
// 尝试加锁，然后对counterCells数组进行扩容
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
// 检查是否已被扩容
if (counterCells == as) {// Expand table unless stale
// 新数组容量为之前的1倍
CounterCell[] rs = new CounterCell[n << 1];
// 迁移数据到新数组
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
// 释放锁
cellsBusy = 0;
}
collide = false;
// 重新执行循环
continue; // Retry with expanded table
}
// 为当前线程重新计算probe
h = ThreadLocalRandom.advanceProbe(h);
}
// CounterCell数组未初始化，尝试获取自旋锁，然后进行初始化
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
// 初始化CounterCell数组，初始容量为2
CounterCell[] rs = new CounterCell[2];
// 初始化CounterCell
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
// 初始化CounterCell数组成功，退出循环
if (init)
break;
}
// 如果自旋锁被占用，则只好尝试更新baseCount
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
Для общего количества статистики, если вы можете понять идею CounterCell, это очень просто. Подумайте об этом внимательно, каждое обновление счетчика будет отнесено к определенному CounterCell в массивах baseCount и CounterCell.Чтобы получить общее количество, просто сложите их вместе.
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
фактическиsize()Общее число, возвращаемое функцией, может быть не на 100% точным.Представьте, что произойдет, если ранее пройденный CounterCell снова обновится? Хотя это всего лишь оценка, она приемлема в большинстве сценариев, а производительность намного выше, чем у Java 7.
добавить элемент
Основная логика добавления элементов ничем не отличается от HashMap, а отличающиеся сложные операции, такие как расширение и подсчет, были подробно проанализированы выше, так что в целомputVal()Функция относительно проста, и единственное, на что нужно обратить внимание, это то, что при работе на узле необходимо обеспечить потокобезопасность через блокировку мьютекса, гранулярность этой блокировки мьютекса очень мала, и только ковш, которым необходимо управлять, заблокирован.
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0; // 节点计数器，用于判断是否需要树化
// 无限循环+CAS，无锁的标准套路
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// bucket为null，通过CAS创建头节点，如果成功就结束循环
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// bucket为ForwardingNode
// 当前线程前去协助进行扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
// 节点是链表
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 找到目标，设置value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// 未找到节点，插入新节点到链表尾部
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 节点是红黑树
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 根据bucket中的节点数决定是否树化
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// oldVal不等于null，说明没有新节点
// 所以直接返回，不进行计数
if (oldVal != null)
return oldVal;
break;
}
}
}
// 计数
addCount(1L, binCount);
return null;
}
Что касается операции по удалению элемента, то она находится в функцииreplaceNode(Object key, V value, Object cv),когдаtable[key].valКогда оно равно ожидаемому значению cv (или cv равно null), значением обновленного узла является значение, а если значение равно null, узел удаляется.
remove()функция, вызываяreplaceNode(key, null, null)Чтобы достичь цели удаления целевого узла,replaceNode()Конкретная реализация иputVal()Разницы нет, но работа связанного списка другая, поэтому больше описывать не буду.
Параллельные вычисления
Помимо редизайна ConcurrentHashMap, в Java 8 также появился Stream API, основанный на лямбда-выражениях. Это функциональное расширение объекта коллекции (поэтому не только ConcurrentHashMap, другие коллекции также реализуют этот API) в элегантном способе пакетной обработки, агрегации или обхода данных в коллекции.
Что наиболее важно, он также обеспечивает параллельный режим, который в полной мере использует преимущества многоядерных процессоров для достижения параллельных вычислений. Давайте посмотрим на следующий пример кода:
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
String keys = "ABCDEFG";
for (int i = 1; i <= keys.length(); i++) {
map.put(String.valueOf(keys.charAt(i - 1)), i);
}
map.forEach(2,
(k, v) -> System.out.println("key-" + k + ":value-" + v + ". by thread->" + Thread.currentThread().getName()));
}
Этот код обходит элементы на карте параллельно через два потока (включая основной поток), а затем выводит на консоль, вывод выглядит следующим образом:
key-A:value-1. by thread->main
key-D:value-4. by thread->ForkJoinPool.commonPool-worker-2
key-B:value-2. by thread->main
key-E:value-5. by thread->ForkJoinPool.commonPool-worker-2
key-C:value-3. by thread->main
key-F:value-6. by thread->ForkJoinPool.commonPool-worker-2
key-G:value-7. by thread->ForkJoinPool.commonPool-worker-2
Очевидно, что работают два потока, так как же это достигается? Давайте сначала посмотримforEach()функция:
public void forEach(long parallelismThreshold,
BiConsumer<? super K,? super V> action) {
if (action == null) throw new NullPointerException();
new ForEachMappingTask<K,V>
(null, batchFor(parallelismThreshold), 0, 0, table,
action).invoke();
}
parallelismThresholdколичество потоков, которым необходимо выполнять операцию параллельно,actionэто функция обратного вызова (действие, которое мы хотим выполнить).actionимеет тип BiConsumer и представляет собой FunctionalInterface, используемый для поддержки лямбда-выражений, который принимает два входных параметра и возвращает 0 результатов.
@FunctionalInterface
public interface BiConsumer<T, U> {
/**
* Performs this operation on the given arguments.
*
* @param t the first input argument
* @param u the second input argument
*/
void accept(T t, U u);
Похоже, что ключ к реализации параллельных вычислений лежит в объекте ForEachMappingTask.С помощью его структуры отношений наследования можно обнаружить, что ForEachMappingTask на самом деле является ForkJoinTask.
Параллельные вычисления коллекции реализованы на основе фреймворка Fork/Join, а рабочие потоки поддерживаются пулом потоков ForkJoinPool. Он отстаивает идею «разделяй и властвуй», разбивая большую задачу на несколько мелких задач,fork()функция (немного похожая на Linuxfork()системный вызов для создания дочернего процесса), чтобы запустить рабочий поток для выполнения одной из небольших задач,join()Функция ожидает завершения выполнения рабочих потоков (необходимо дождаться завершения выполнения всех рабочих потоков, прежде чем объединять окончательный результат).Поскольку все мелкие задачи обработаны, это означает, что большая задача также выполнена.
Приведенный выше пример кода предназначен для разложения этой большой задачи обхода на N небольших задач, а затем передачи их двум рабочим потокам для обработки.
static final class ForEachMappingTask<K,V>
extends BulkTask<K,V,Void> {
final BiConsumer<? super K, ? super V> action;
ForEachMappingTask
(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
BiConsumer<? super K,? super V> action) {
super(p, b, i, f, t);
this.action = action;
}
public final void compute() {
final BiConsumer<? super K, ? super V> action;
if ((action = this.action) != null) {
for (int i = baseIndex, f, h; batch > 0 &&
(h = ((f = baseLimit) + i) >>> 1) > i;) {
// 记录待完成任务的数量
addToPendingCount(1);
// 开启一个工作线程执行任务
// 其余参数是任务的区间以及table和回调函数
new ForEachMappingTask<K,V>
(this, batch >>>= 1, baseLimit = h, f, tab,
action).fork();
}
for (Node<K,V> p; (p = advance()) != null; )
// 调用回调函数
action.accept(p.key, p.val);
// 与addToPendingCount()相反
// 它会减少待完成任务的计数器
// 如果该计数器为0，代表所有任务已经完成了
propagateCompletion();
}
}
}
Реализация других функций параллельных вычислений аналогична, но конкретная реализация Задачи отличается, напримерsearch():
public <U> U search(long parallelismThreshold,
BiFunction<? super K, ? super V, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchMappingsTask<K,V,U>
(null, batchFor(parallelismThreshold), 0, 0, table,
searchFunction, new AtomicReference<U>()).invoke();
}
В целях экономии места (честно говоря, сейчас мало кто способен терпеливо читать длинную статью _(:з"∠)_), я не буду много говорить о том, как работает Stream API с использованием Fork/Join. фреймворк и детали реализации, поговорим об этом позже.