关于JAVA的集合框架近期也会逐渐同步跟新出来，欢迎小伙伴们多提意见
Сегодня я начну с исходного кода серии сборников JAVA, а также постараюсь прочитать исходный код по-разному и под разными углами и почерпнуть некоторые идеи из исходного кода. HashMap — одна из самых часто используемых коллекций, до JDK1.7 было много споров, с одной стороны, это проблема эффективности запросов после увеличения объема данных, и проблема потокобезопасности. Эта статья начнется с исходного кода двух разных версий JDK1.7 и 1.8, чтобы изучить, как оптимизируется HashMap и возникновение проблем с безопасностью потоков.
jdk1.7
Основное отличие HashMap в 1.7 и 1.6:
- Добавлен параметр jdk.map.althashing.threshold для jdk, чтобы контролировать, использовать ли новый алгоритм хеширования типа String во время раскрытия.
- Инициализация таблицы в методе построения 1.6 перенесена в метод put.
- Метод переноса в 1.6 выполняет нулевую операцию над узлами старой таблицы (существует проблема многопоточности), которая была удалена в 1.7.
определение
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap наследуется от AbstractMap и реализует Map, Cloneable и Serializable. Поскольку реализован интерфейс Serializable, то есть сериализация может быть достигнута, как вы можете видеть из следующего введения переменных-членов, таблица [] украшена переходным механизмом, который имеет место для большинства классов в структуре коллекции. После ознакомления с соответствующей информацией и объединения объяснений различных великих богов в Интернете, вот краткое изложение:
-
Уменьшите ненужную сериализацию нулей
table 以及 elementData中存储的数据的数量通常情况下是要小于数组长度的（扩容机制），这个在数据越来越多的情况下更为明显（数据变多，伴随着冲突概率变大，同时也伴随着扩容）。如果使用默认的序列化，那些没有数据的位置也会被存储，就会产生很多不必要的浪费。 -
Проблемы совместимости с разными виртуальными машинами
由于不同的虚拟机对于相同hashCode产生的Code值可能是不一样的，如果使用默认的序列化，那么反序列化后，元素的位置和之前的是保持一致的，可是由于hashCode的值不一样了，那么定位到的桶的下标就会不同，这很明显不是我们想看到的
Сериализация HashMap не использует метод сериализации по умолчанию, а использует пользовательский метод сериализации для завершения путем переопределения метода writeObject.
Переменные-члены
- Начальная емкость по умолчанию 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- Максимальная емкость
static final int MAXIMUM_CAPACITY = 1 << 30;
- Коэффициент нагрузки по умолчанию
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- пустой экземпляр таблицы
static final Entry<?,?>[] EMPTY_TABLE = {};
- таблица, массив Entry
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
- размер, общее количество ключей-значений в карте
transient int size;
- Порог, когда общее количество ключей-значений в карте достигает этого значения, расширять емкость
int threshold;
- коэффициент нагрузки
final float loadFactor;
- Количество модификаций (механизм fial-fast)
transient int modCount;
- Порог по умолчанию для альтернативного хеширования (если используется новый алгоритм хеширования типа String)
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
- Управляет повторным хешированием, значение по умолчанию равно 0, что будет подробно объяснено позже.
transient int hashSeed = 0;
- Внутренний класс, инициализируемый после запуска ВМ
jdk.map.althashing.threshold
Параметр в JDK, по умолчанию равен -1, если установлено значение 1, это заставит использовать новый алгоритм хеширования типа String.
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
внутренняя структура
- Запись, 4 атрибута (ключ, значение, следующий узел, хеш-значение)
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
Конструктор
- Конструктор без аргументов, начальная емкость по умолчанию 16, коэффициент загрузки 0,75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
- Конструктор с одним параметром, коэффициент загрузки по умолчанию 0,75.
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- Конструктор с двумя параметрами, установка мощности и коэффициента загрузки
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;
threshold = initialCapacity;
init();
}
- метод init, метод шаблона, если есть подклассы, которые необходимо расширить, их можно реализовать самостоятельно
void init() {
}
основной метод
- хэш-метод
final int hash(Object k) {
int h = hashSeed;
//默认0，如果不是0，并且key是String类型，才使用新的hash算法（避免碰
//撞的优化？）
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//把高位的值移到低位参与运算，使高位值的变化会影响到hash结果
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- Определить позицию в таблице по значению хеша, длина кратна 2 Расширение HashMap основано на кратности 2. Из этого видно, что для метода indexFor его конкретная реализация заключается в выполнении битовых операций через вычисленное кодовое значение и длину массива -1, тогда для 2^N в It сказано, что после преобразования длины минус один в двоичную, она становится все единицей (длина 16, len-1=15, двоичная равна 1111), поэтому преимущество этой настройки в том, что на нас будет влиять каждый бит вычисляемого значения кода. Цель определения позиции индекса — обеспечить лучшее хэширование данных в разные сегменты.
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
положить метод
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
//如果表没有初始化，则以阈值threshold的容量初始化表
inflateTable(threshold);
}
if (key == null)
//如果key值为null，调用putForNullKey方法，所以hashmap可以插入key和value为null的值
return putForNullKey(value);
//计算key的hash值
int hash = hash(key);
//计算hash值对应表的位置，即表下标
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//如果hash值相等并且（key值相等或者key的equals方法相等），
//则覆盖，返回旧的value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改字数+1
modCount++;
//如果没找到key没找到，则插入
addEntry(hash, key, value, i);
return null;
}
- метод инициализации таблицы,Вместимость стола должна быть кратна 2(раундUpToPowerOf2)
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
- Получает наименьшее кратное 2, большее или равное заданному значению
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
- highOneBit: возвращает наибольшее кратное 2, которое меньше заданного значения.
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1); //其余位不管，把最高位的1覆盖到第二位，使前2位都是1
i |= (i >> 2); //同样的，把第3、4位置1，使前4位都是1
i |= (i >> 4); //...
i |= (i >> 8); //...
i |= (i >> 16); //最高位以及低位都是1
return i - (i >>> 1); //返回最高位为1，其余位全为0的值
}
- Метод initHashSeedAsNeeded определяет необходимость повторного хеширования при расширении передачи.
final boolean initHashSeedAsNeeded(int capacity) {
//hashSeed默认0，currentAltHashing为false
boolean currentAltHashing = hashSeed != 0;
//参照上面的Holder类的静态块，jdk.map.althashing.threshold默认-1，Holder.ALTERNATIVE_HASHING_THRESHOLD为Integer.MAX_VALUE，如果jdk.map.althashing.threshold设置了其他非负数，可以改变Holder.ALTERNATIVE_HASHING_THRESHOLD的值，如果不超过Integer.MAX_VALUE，则useAltHashing为true
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) { //改变hashSeed的值，使hashSeed!=0，rehash时String类型会使用新hash算法
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
- HashMap помещает пару ключ-значение с нулевым ключом в таблицу [0]
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
- Вставьте новую пару ключ-значение
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //如果键值对数量达到了阈值，则扩容
hash = (null != key) ? hash(key) : 0; //null的hash值为0
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
-
пробка для головы, то есть вставить новую запись в позицию заголовка списка table[bucketIndex]
Объяснение метода вставки заголовка: Как правило, данные, вставленные после значения по умолчанию, будут запрашиваться чаще.
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
получить метод
public V get(Object key) {
if (key == null)
return getForNullKey(); //如果key为null，直接去table[0]中找
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
- Метод getEntry относительно прост: сначала найдите позицию хеш-значения в таблице, затем зациклите связанный список, чтобы найти запись, если она существует, верните запись, иначе верните ноль.
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
- метод удаления
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i]; //前一个节点
Entry<K,V> e = prev; //当前节点
while (e != null) {
Entry<K,V> next = e.next; //下一个节点
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e) //如果相等，说明需要删除的是头节点，头节点直接等于next
table[i] = next;
else
prev.next = next; //如果不是头节点，前一个的next等于下一个节点，删除当前节点
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
Метод изменения размера, расширение (выделение)
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //如果容量已经达到MAXIMUM_CAPACITY，不扩容
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//initHashSeedAsNeeded方法决定是否重新计算String类型的hash值
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
- метод переноса, перенести все узлы старой таблицы в новую таблицу
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/**
*重新计算hash值在新表中的位置（旧表中一条链表中的数据
*最多会分成两条存在新表中，即oldTable[index]中的节点会存到
*newTable[index]和newTable[index+oldTable.length]中）
*/
int i = indexFor(e.hash, newCapacity);
//头插法插入到新表中
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
jdk1.8
1.8 HashMap имеет много изменений по сравнению с 1.7
- Структура Entry становится структурой Node,хэш-переменная с окончательным объявлением, то есть перефразировать нельзя
- Способ вставки узла изпробка для головысталвставка хвоста
- представилкрасно-черное дерево
- метод tableSizeFor, алгоритм хеширования и т. д.
определение
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
Переменные-члены
- Начальная емкость по умолчанию
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- Максимальная емкость
static final int MAXIMUM_CAPACITY = 1 << 30;
- Коэффициент нагрузки по умолчанию 0,75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- Порог преобразования связанного списка в красно-черное дерево равен 8.
static final int TREEIFY_THRESHOLD = 8;
- Порог красно-черного дерева для связного списка равен 6
static final int UNTREEIFY_THRESHOLD = 6;
- Минимальная емкость таблицы, необходимая для преобразования связанного списка в красно-черное дерево, равна 64, то есть когда длина связанного списка достигает критического значения 8 для преобразования в красно-черное дерево, если емкость таблицы меньше чем 64, связанный список не будет преобразован в красно-черное дерево в это время, а таблица будет расширена, чтобы уменьшить длину связанного списка.
static final int MIN_TREEIFY_CAPACITY = 64;
- таблица, массив узлов
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
- Общее количество узлов
transient int size;
- Модификации
transient int modCount;
- Порог расширения
int threshold;
- коэффициент нагрузки
final float loadFactor;
структура
- Структура узла, реализует Entry, хэш-значение объявляется окончательным и больше не является переменным, то есть операции перехеширования в 1.7 не существует
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Конструктор
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
- Параметр представляет собой метод построения карты, сначала вычислите требуемый размер емкости, а затем вызовите метод putVal для вставки узла.
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- Метод tableSizeFor по заданному значению инициализированной емкости таблицы возвращает фактическую инициализированную емкость таблицы (должна быть кратна 2).По сравнению с 1.7 этот метод оптимизирован и более лаконичен.
static final int tableSizeFor(int cap) {
int n = cap - 1; //先进行-1操作，当cap已经是2的倍数时，最后+1，返回该数本身
n |= n >>> 1; //右移1位，再进行或操作，然后赋值给n，使最高位的1的下一位也变成1
n |= n >>> 2; //右移2位，使最高2位的1右移覆盖后2位的值，即最高4位均为1
n |= n >>> 4; //右移4位...
n |= n >>> 8; //右移8位...
n |= n >>> 16; //右移16位...
//如果cap<=0，返回1，如果>MAXIMUM_CAPACITY,返回MAXIMUM_CAPACITY，否则，最后的n+1操作返回大于等于cap的最小的2的倍数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
основной метод
- Алгоритм хеширования упрощен, а высокое 16-битное смещение напрямую объединяется по ИЛИ.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
положить метод
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* onlyIfAbsent 如果是true，不存在才插入，存在则不改变原有的值
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//如果table为null或者length为0，调用resize扩容方法（没有单独的///初始化方法了）
n = (tab = resize()).length;
//i = (n - 1) & //hash]计算hash值对应表中的位置，如果链表头为null，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果key存在，赋值给e，后面统一判断是否插入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是树节点，调用putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//循环tab[i = (n - 1) & //hash]上的链表，binCount记录链表的长度，用来判断是否转化为树结//构
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//如果key没找到，直接插入
p.next = newNode(hash, key, value, null);
// -1 for 1st，如果长度达到了8，就转化为树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
// key存在，如果onlyIfAbsent为false，替换value，如果onlyIfAbsen//t 为true，原有值为null，也会替换，否则不变更原有值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //LinkedHashMap重写使用
return oldValue;
}
}
++modCount; //修改次数+1
if (++size > threshold) //如果size达到了扩容的阈值，则进行扩容操作
resize();
afterNodeInsertion(evict); //LinkedHashMap重写用的
return null;
}
получить метод
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
- Метод getNode очень прост, (n - 1) & hash вычисляет нижний индекс таблицы, соответствующий значению ключа, находит связанный список, сначала оценивает головной узел, а затем выполняет поиск в цикле.Если головной узел является узлом дерева , вызвать метод getTreeNode узла дерева
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // 先判断第一个节点
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
метод удаления
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal //如果是true，value也要相等
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {//找到对应的头节点
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//先判断头节点
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode) //如果是树，调用树的getTreeNode方法
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { //循环链表
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) { //matchValue为true时，value也要相等才删除节点
if (node instanceof TreeNode) //树节点的删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //如果是头节点，把头节点的下个节点赋值给头节点
tab[index] = node.next;
else //把当前节点的next节点赋值给上一个节点的next（删除当前节点）
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); //空方法，LinkedHashMap重写用
return node;
}
}
return null;
}
метод изменения размера (расширение)
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //如果旧表已经初始化过了
if (oldCap >= MAXIMUM_CAPACITY) { //达到上限，不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果容量大于等于16，并且*2小于上限，扩容2倍，新表容量=旧表*2，新阈值=旧阈值*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 初始化表，有参构造函数中把需要初始化的容量赋值给了threshold
newCap = oldThr;
else { // 如果没有给定容量，默认初始化16，阈值16*0.75=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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;
/**
* 如果旧表里有值，需要把旧表里的值重新计算放到新表里
* hash & (oldCap*2-1)计算新表中的位置，只可能得到两种结果（把新表分成两个小表）
* hash & (oldCap-1) 放在前面的表里 和 hash & (oldCap-1) + oldCap 放在后面的表里
* hash & oldCap == 0 就是第一种结果， !=0 就是第二种结果
*/
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //头节点是null，直接赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //树节点处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { //循环链表
next = e.next;
if ((e.hash & oldCap) == 0) { //分配到前面表里的放在一个链表里
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //分配到后面表里的放在一个链表里
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { //放到新表里
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Вопросы безопасности многопоточности
HashMap не является потокобезопасным
- В JDK1.7, когда два потока одновременно выполняют операцию вставки и одновременно выполняют метод createEntry, получается один и тот же головной узел e, второй поток перезапишет операцию вставки первого потока, а данные, вставленные первым нить потеряется.Метод вставки хвоста в JDK1.8Есть и такая проблема: два потока захватывают один и тот же узел, а затем присваивают новую пару ключ-значение следующему узлу, а последующая операция присваивания перезаписывает предыдущую.
- JDK1.7 и JDK1.8При расширении карты, поскольку следующий узел узла изменится, на самом деле значение ключа есть, но операция чтения возвращает null.
- В версии 1.7, когда два потока выполняют операции расширения одновременно, это может вызватьБесконечный цикл связанного списка,Процесс формирования:
- Теперь есть карта:
- Поток 1 выполняет операцию расширения, выполняет метод передачи и блокируется после назначения узлов e и next.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
- Поток 2 выполняет операцию расширения и завершает расширение, создавая newTable2.
- В этот момент соединение между узлом e и next показано на рисунке выше.Если поток 1 продолжает выполняться, процесс выполнения выглядит следующим образом:
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
```java
```java
e = next;
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
- В этот момент связанный список образует бесконечный цикл.
- Метод передачи в 1.8 был изменен и не будет вызывать бесконечный цикл.
Суммировать
- Структура HashMap, основной метод
- Разница между 1.7 и 1.8
- Насчет красно-черной части дерева, она будет добавлена позже