Почему HashMap меняется с вставки головы на вставку хвоста

Публичный аккаунт WeChat:I am CR7
Если у вас есть какие-либо вопросы или предложения, пожалуйста, оставьте сообщение ниже;
Последнее обновление: 2018-09-21

предисловие

Подробно проанализирован принцип реализации вставки элемента HashMap в jdk1.8, подробнее см.:Вставка элемента HashMap. После публикации статьи друг задал такой вопрос: «Jdk1.7 использует вставку заголовка, почему в jdk1.8 она изменена на вставку хвоста?». Некоторые люди говорят, что это просто так делает бог Java, и в этом нет особой пользы. В то время, поскольку я не читал исходный код 1.7 внимательно, ответить было непросто. Настоящая статья написана для проведения подробного анализа этой проблемы.

статическая постоянная

Исходный код:

 1/**
 2 * 默认初始大小，值为16，要求必须为2的幂
 3 */
 4static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 5
 6/**
 7 * 最大容量，必须不大于2^30
 8 */
 9static final int MAXIMUM_CAPACITY = 1 << 30;
10
11/**
12 * 默认加载因子，值为0.75
13 */
14static final float DEFAULT_LOAD_FACTOR = 0.75f;
15
16/**
17 * HashMap的空数组
18 */
19static final Entry<?,?>[] EMPTY_TABLE = {};
20
21/**
22 * 可选的默认哈希阈值
23 */
24static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

     Уведомление:В jdk1.7 HashMap использует массив + односвязный список для хранения элементов по умолчанию.Когда элемент имеет конфликт хэшей, он будет сохранен в односвязном списке в этом месте. Это отличается от 1.8.За исключением массивов и односвязных списков, когда количество элементов в односвязном списке превышает 8, он будет преобразован в хранилище красно-черного дерева, что разумно снижает временную сложность обхода элементов из O( n) до O (logn)).

Конструктор

1. Конструктор без аргументов:

1public HashMap() {
2    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
3}

2. Конструктор с параметрами, задающими начальную емкость:

1public HashMap(int initialCapacity) {
2    this(initialCapacity, DEFAULT_LOAD_FACTOR);
3}

3. Конструктор с параметрами, задающими начальную мощность и коэффициент загрузки:

 1public HashMap(int initialCapacity, float loadFactor) {
 2    if (initialCapacity < 0)
 3        throw new IllegalArgumentException("Illegal initial capacity: " +
 4                                           initialCapacity);
 5    if (initialCapacity > MAXIMUM_CAPACITY)
 6        initialCapacity = MAXIMUM_CAPACITY;
 7    if (loadFactor <= 0 || Float.isNaN(loadFactor))
 8        throw new IllegalArgumentException("Illegal load factor: " +
 9                                           loadFactor);
10
11    this.loadFactor = loadFactor;
12    threshold = initialCapacity;//和jdk8不同，初始阈值就是初始容量，并没做2次幂处理
13    init();
14}

4. Конструктор с параметрами, указывающими коллекцию Map:

 1public void putAll(Map<? extends K, ? extends V> m) {
 2        int numKeysToBeAdded = m.size();
 3        if (numKeysToBeAdded == 0)
 4            return;
 5
 6        if (table == EMPTY_TABLE) {
 7            inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
 8        }
 9
10        if (numKeysToBeAdded > threshold) {
11            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
12            if (targetCapacity > MAXIMUM_CAPACITY)
13                targetCapacity = MAXIMUM_CAPACITY;
14            int newCapacity = table.length;
15            while (newCapacity < targetCapacity)
16                newCapacity <<= 1;
17            if (newCapacity > table.length)
18                resize(newCapacity);
19        }
20
21        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
22            put(e.getKey(), e.getValue());
23    }

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

добавить элемент

1. Исходный код:

 1public V put(K key, V value) {
 2    if (table == EMPTY_TABLE) {
 3        inflateTable(threshold);//初始化数组
 4    }
 5    if (key == null)//key为null，做key为null的添加
 6        return putForNullKey(value);
 7    int hash = hash(key);//计算键值的哈希
 8    int i = indexFor(hash, table.length);//根据哈希值获取在数组中的索引位置
 9    for (Entry<K,V> e = table[i]; e != null; e = e.next) {//遍历索引位置的单链表，判断是否存在指定key
10        Object k;
11        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//key已存在则更新value值
12            V oldValue = e.value;
13            e.value = value;
14            e.recordAccess(this);
15            return oldValue;
16        }
17    }
18
19    modCount++;
20    addEntry(hash, key, value, i);//key不存在，则插入元素
21    return null;
22}
23
24private V putForNullKey(V value) {
25    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
26        if (e.key == null) {//key为null已存在，更新value值
27            V oldValue = e.value;
28            e.value = value;
29            e.recordAccess(this);
30            return oldValue;
31        }
32    }
33    modCount++;
34    addEntry(0, null, value, 0);//不存在则新增，key为null的哈希值为0
35    return null;
36}
37
38void addEntry(int hash, K key, V value, int bucketIndex) {
39    if ((size >= threshold) && (null != table[bucketIndex])) {//插入位置存在元素，并且元素个数大于等于新增阈值
40        resize(2 * table.length);//进行2倍扩容
41        hash = (null != key) ? hash(key) : 0;//扩容中可能会调整哈希种子的值，所以重新计算哈希值
42        bucketIndex = indexFor(hash, table.length);//重新计算在扩容后数组中的位置
43    }
44
45    createEntry(hash, key, value, bucketIndex);//添加元素
46}
47
48//计算对象哈希值
49final int hash(Object k) {
50    int h = hashSeed;
51    if (0 != h && k instanceof String) {//String采用单独的算法
52        return sun.misc.Hashing.stringHash32((String) k);
53    }
54
55    h ^= k.hashCode();//利用哈希种子异或哈希值，为了进行优化，增加随机性
56
57    h ^= (h >>> 20) ^ (h >>> 12);
58    return h ^ (h >>> 7) ^ (h >>> 4);//这里的移位异或操作属于扰乱函数，都是为了增加哈希值的随机性，降低哈希冲突的概率
59}
60
61void createEntry(int hash, K key, V value, int bucketIndex) {
62    Entry<K,V> e = table[bucketIndex];
63    table[bucketIndex] = new Entry<>(hash, key, value, e);//新增元素插入到数组索引位置，原来元素作为其后继节点，即采用头插入方法
64    size++;
65}

2. Блок-схема:

3. Пример:

инициализировать массив

1. Исходный код:

 1//根据指定的大小，初始化数组
 2private void inflateTable(int toSize) {
 3    // Find a power of 2 >= toSize
 4    int capacity = roundUpToPowerOf2(toSize);
 5
 6    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//根据容量和加载因子计算阈值，最大为2^30+1
 7    table = new Entry[capacity];//创建指定容量大小的数组
 8    initHashSeedAsNeeded(capacity);
 9}
10
11//获取大于指定值的最小2次幂，最大为2^30
12private static int roundUpToPowerOf2(int number) {
13    // assert number >= 0 : "number must be non-negative";
14    return number >= MAXIMUM_CAPACITY
15            ? MAXIMUM_CAPACITY
16            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
17}

2. Описание:

Что касается начального числа хеша, то оно предназначено для оптимизации хеш-функции и придания ей более случайного значения, тем самым снижая вероятность коллизии хэшей. Через частный статический класс Holder в HashMap при запуске JVM укажите значение -Djdk.map.althashing.threshold=, чтобы установить необязательный порог хэша, чтобы решить, следует ли корректировать начальное значение хэша в initHashSeedAsNeeded.

 1private static class Holder {
 2
 3    /**
 4     * Table capacity above which to switch to use alternative hashing.
 5     */
 6    static final int ALTERNATIVE_HASHING_THRESHOLD;
 7
 8    static {
 9        String altThreshold = java.security.AccessController.doPrivileged(
10            new sun.security.action.GetPropertyAction(
11                "jdk.map.althashing.threshold"));//通过-Djdk.map.althashing.threshold=值指定可选哈希阈值
12
13        int threshold;
14        try {
15            threshold = (null != altThreshold)
16                    ? Integer.parseInt(altThreshold)
17                    : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;//默认为Integer.MAX_VALUE
18
19            // disable alternative hashing if -1
20            if (threshold == -1) {
21                threshold = Integer.MAX_VALUE;
22            }
23
24            if (threshold < 0) {
25                throw new IllegalArgumentException("value must be positive integer.");
26            }
27        } catch(IllegalArgumentException failed) {
28            throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
29        }
30
31        ALTERNATIVE_HASHING_THRESHOLD = threshold;//指定可选的哈希阈值，在initHashSeedAsNeeded作为是否初始化哈希种子的判定条件
32    }
33}
34
35//根据容量决定是否需要初始化哈希种子
36final boolean initHashSeedAsNeeded(int capacity) {
37    boolean currentAltHashing = hashSeed != 0;//哈希种子默认为0
38    boolean useAltHashing = sun.misc.VM.isBooted() &&
39            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//如果容量大于可选的哈希阈值，则需要初始化哈希种子
40    boolean switching = currentAltHashing ^ useAltHashing;
41    if (switching) {
42        hashSeed = useAltHashing
43            ? sun.misc.Hashing.randomHashSeed(this)//生成一个随机的哈希种子
44            : 0;
45    }
46    return switching;
47}

Расширение

1. Исходный код:

 1//按照指定容量进行数组扩容
 2void resize(int newCapacity) {
 3    Entry[] oldTable = table;
 4    int oldCapacity = oldTable.length;
 5    if (oldCapacity == MAXIMUM_CAPACITY) {//原有容量达到最大值，则不再扩容
 6        threshold = Integer.MAX_VALUE;
 7        return;
 8    }
 9
10    Entry[] newTable = new Entry[newCapacity];
11    transfer(newTable, initHashSeedAsNeeded(newCapacity));
12    table = newTable;
13    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//按照扩容后容量重新计算阈值
14}
15
16//将元素重新分配到新数组中
17void transfer(Entry[] newTable, boolean rehash) {
18    int newCapacity = newTable.length;
19    for (Entry<K,V> e : table) {//遍历原数组
20        while(null != e) {
21            Entry<K,V> next = e.next;
22            if (rehash) {//扩容后数组需要重新计算哈希
23                e.hash = null == e.key ? 0 : hash(e.key);
24            }
25            int i = indexFor(e.hash, newCapacity);//计算新数组中的位置
26            e.next = newTable[i];//采用头插入法，添加到新数组中
27            newTable[i] = e;
28            e = next;
29        }
30    }
31}

2. Вопрос:

Вышеупомянутый код расширения, выполняемый в параллельных условиях, вызовет часто упоминаемую проблему формирования связанного списка.Ниже приведен пример для анализа:
2.1 Исходное состояние:

Резьба 1 вставляет 18, резьба 2 вставляет 26. В это время поток 1 обнаруживает, что размер равен 6, и расширяет емкость. Поток 2 обнаруживает, что размер равен 6, и также увеличивает емкость.
2.2 Поток 1 выполняет:
Поток 1 первым получает права на выполнение ЦП, выполняет передачу () Средний код:

 1for (Entry<K,V> e : table) {
 2    while(null != e) {
 3        Entry<K,V> next = e.next;//线程1执行到此行代码，e为10，next为2。此时CPU调度线程2执行。
 4        if (rehash) {
 5            e.hash = null == e.key ? 0 : hash(e.key);
 6        }
 7        int i = indexFor(e.hash, newCapacity);
 8        e.next = newTable[i];
 9        newTable[i] = e;
10        e = next;
11    }
12}

2.3 Поток 2 выполняет:
Поток 2 в это время получает процессорное исполнение и выполняет код в transfer():

 1for (Entry<K,V> e : table) {
 2    while(null != e) {
 3        Entry<K,V> next = e.next;
 4        if (rehash) {
 5            e.hash = null == e.key ? 0 : hash(e.key);
 6        }
 7        int i = indexFor(e.hash, newCapacity);
 8        e.next = newTable[i];
 9        newTable[i] = e;
10        e = next;
11    }
12}

Первый обход: e равно 10, next равно 2, rehash равно false, i равно 2, newTable[2] равно null, 10.next равно null, newTable[2] равно 10, e равно 2.
Второй обход: e равно 2, next равно null, rehash равно false, i равно 2, newTable[2] равно 10, 2.next равно 10, newTable[2] равно 2, e равно null.
Третий обход: e равен нулю, выход из цикла.
Обратите внимание, что в это время следующий элемент 2 в исходной таблице указывает на 10.

2.4 Поток 1 выполняет:

 1for (Entry<K,V> e : table) {
 2    while(null != e) {
 3        Entry<K,V> next = e.next;//线程1执行到此行代码，e为10，next为2。CPU调度线程1继续执行。
 4        if (rehash) {
 5            e.hash = null == e.key ? 0 : hash(e.key);
 6        }
 7        int i = indexFor(e.hash, newCapacity);
 8        e.next = newTable[i];
 9        newTable[i] = e;
10        e = next;
11    }
12}

В настоящее время: e равно 10, next равно 2, rehash равно false, i равно 2, newTable[2] равно null, модификация: 10.next равно null, newTable[2] равно 10 и e равно 2.
Второй обход: текущий: e равен 2, следующий равен 10 [результат после выполнения потока 2], rehash равен false, i равен 2, newTable[2] равен 10, модификация: 2.next равен 10, newTable[2] равно 2, а е равно 10.
Третий обход: текущий: e равно 10, next равно null, rehash равно false, i равно 2, newTable[2] равно 2, модификация: 10.next равно 2, newTable[2] равно 10, e равно null, выход из цикла .
В этот момент связанный список образует цикл, и если вы будете искать его, вы попадете в бесконечный цикл! ! !

3. Описание:

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

Суммировать

На основе приведенного выше анализа, вот сводка изменений в HashMap между 1.7 и 1.8:

• 1.7 Использовать массив + односвязный список, 1.8 После того, как односвязный список превысит определенную длину, он изменится на хранилище красно-черного дерева
• 1.7 Необходимо пересчитывать хеш-значение и позицию индекса при расширении емкости.В 1.8 хеш-значение не пересчитывается, а новая позиция индекса вычисляется умелым использованием операции & с емкостью после расширения емкости.
• 1.7 Вставка элементов в односвязный список использует метод вставки начала, а 1.8 — метод вставки хвоста.

Изучая исходный код HashMap в jdk1.7 и 1.8, я глубоко понял истину: все конструкции имеют свои причины. Как учащиеся, мы должны постоянно спрашивать себя, почему он разработан таким образом и каковы его преимущества. С таким отношением к обучению, я думаю, в ближайшем будущем ты им станешь.
В конце статьи спасибо за вашу поддержку Добро пожаловать, чтобы отсканировать QR-код ниже, чтобы обратить внимание. Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение.