HashMap небезопасен при многопоточности (JDK1.7)

Java

Анализ в этой статье основан на HashMap JDK1.7.

Проблемы, вызванные HashMap в случае многопоточности

  1. После многопоточной операции put операция get приводит к бесконечному циклу.
  2. Многопоточная операция размещения, приводящая к потере элемента.

Снова появляется сцена бесконечного цикла

public class HashMapTest extends Thread {

    private static HashMap<Integer, Integer> map = new HashMap<>(2);
    private static AtomicInteger at = new AtomicInteger();

    @Override
    public void run() {
        while (at.get() < 1000000) {
            map.put(at.get(), at.get());
            at.incrementAndGet();
        }
    }


    public static void main(String[] args) {
        HashMapTest t0 = new HashMapTest();
        HashMapTest t1 = new HashMapTest();
        HashMapTest t2 = new HashMapTest();
        HashMapTest t3 = new HashMapTest();
        HashMapTest t4 = new HashMapTest();
        HashMapTest t5 = new HashMapTest();
        t0.start();
        t1.start();
        t2.start();
        t3.start();
        t4.start();
        t5.start();

        for (int i = 0; i < 1000000; i++) {
            Integer integer = map.get(i);
            System.out.println(integer);
        }
    }
}

Повторно выполнить несколько раз, если это произойдет, то это означает бесконечный цикл:

Из приведенного выше видно, что Thread-7 вызвал бесконечный цикл из-за расширения HashMap.

Анализ HashMap

Развернуть исходный код ключевого контента

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

нормальный процесс расширения

Давайте сначала посмотрим на обычный процесс перефразирования в случае одного потока:

  1. Предположим, что наш алгоритм хеширования представляет собой простой ключевой мод на размер таблицы (т.е. длину массива).
  2. Вверху находится старая хеш-таблица, в которой размер HASH-таблицы равен 2, поэтому ключи = 3, 5 и 7 конфликтуют с позицией таблицы [1] после мода 2.
  3. Далее HASH-таблица расширяется, resize=4, после чего снова выполняется распределение всех хэшей, процесс выглядит следующим образом:

С одним потоком все выглядит великолепно, а процесс масштабирования довольно плавный. Далее давайте посмотрим на расширение в случае параллелизма.

Расширение в случае параллелизма

  1. Есть две нити, отмеченные красным и синим.

  2. Когда поток 1 выполняет пятую строку кода, он приостанавливается из-за планирования ЦП (после выполнения следующим является 7), и поток 2 выполняется, и поток 2 заканчивает выполнение вышеуказанного кода. Давайте посмотрим на состояние в это время

  1. Затем CPU переключается на поток 1, выполняет 4-12 строк кода (пятая строка уже выполнена) и сначала устанавливает Entry со значением ключа 3:

Примечание: поток 2 завершил выполнение, и теперь все записи в таблице являются самыми последними, то есть следующий из 7 равен 3, а следующий из 3 равен нулю; теперь первый цикл закончился, и 3 был размещен правильно.

  1. Посмотрите, что будет дальше:
    • e=next=7;
    • e!=null, цикл продолжается
    • next=e.next=3
    • e.next 7 указывает на 3
    • Поместите 7 эту запись, как показано на рисунке:

  1. После размещения 7 запустите код:
    • e=next=3;
    • Суждение не пустое, продолжайте цикл
    • next= e.next здесь следующее из 3 равно null
    • e.next=7, следующее из 3 указывает на 7.
    • Поместите 3 эту запись, состояние в это время показано на рисунке.

В это время фактически происходит бесконечный цикл: 3 перемещает положение головы узла, чтобы указать на запись 7, до этого следующая из 7 также указывает на запись 3.

  1. Затем код выполняется вниз, e=next=null, и в этот момент условное суждение завершает цикл. Это расширение закончилось. Однако, если есть последующий запрос (будь то итерация или расширение запроса), он зависнет и умрет на позиции table[3]. Теперь вернитесь к Демо в начале статьи, которое висит на методе переноса в стадии расширения.

Основные причины проблемы:Если две соседние записи до расширения по-прежнему размещены в одной и той же позиции таблицы после расширения, возникнет ОШИБКА бесконечного цикла.. В сложных производственных средах эта ситуация, хотя и необычная, может возникнуть.

Многопоточная операция размещения, приводящая к потере элемента

Давайте представим проблему недостающих элементов. На этот раз мы выбираем порядок 3, 5, 7, чтобы продемонстрировать:

  1. Если поток приостанавливается планированием ЦП, как только поток выполняется до строки 5:

  1. Выполнение второго потока завершено:

  1. В это время выполняется первый поток, и запись 7 размещается первой:

  1. Затем поместите 5 эту запись:

  1. Поскольку следующее из 5 равно нулю, операция расширения в это время завершается, что приводит к потере записи 3.

Улучшения в JDK 8

JDK 8 использует метод битового ведра + связанный список/красно-черное дерево.Когда длина связанного списка битового ведра превышает 8, связанный список будет преобразован в красно-черное дерево.

HashMap не будет вызывать бесконечный цикл из-за многопоточного размещения (JDK 8 использует начало и конец, чтобы гарантировать, что порядок связанного списка такой же, как и раньше; повторное хеширование JDK 7 инвертирует элементы связанного списка), но все равно будет могут быть такие недостатки, как потеря данных (сам параллелизм). Поэтому рекомендуется использовать ConcurrentHashMap в случае многопоточности.

Почему поток небезопасен

Проблемы, которые могут возникнуть, когда HashMap является параллельным, в основном состоят из двух аспектов:

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

  2. Если несколько потоков обнаружат, что количество элементов превышает размер массива * loadFactor одновременно, несколько потоков будут расширять массив Node одновременно, пересчитывая позицию элемента и копируя данные, но в итоге только один поток расширит массив, назначенный таблице, то есть данные других потоков будут потеряны, а также будут потеряны данные, помещенные соответствующими потоками.

Категории