Самая тонкая из всей сети | 21 фотография позволит вам оценить ненадежность коллекции.

Основное содержание этой статьи следующее:

Все в этой статье示例代码обновлено домой гитхаб

Эта статья была включена в мойОнлайн-документация по Java

Серия "Параллелизм в Java должен знать, должен знать":

1. Встречный интервьюер | 14 схем | Никогда не бойся, что тебя спросят изменчиво!

2. Программист был презираем женой поздно ночью, потому что принцип CAS был слишком простым?

3. Используйте стандартные блоки, чтобы объяснить принцип ABA | Жена снова его понимает!

4. Самый тонкий во всей сети | 21 картинка показывает вам ненадежность коллекции

1. Небезопасный для потоков ArrayList

Рамка коллекцииЕсть две категории: карта и коллекция.Под коллекцией находятся список, набор и очередь. Под списком находятся ArrayList, Vector и LinkedList. Как показано ниже:

Параллельный пакет JUCКлассы коллекций в разделе «Коллекции»: Queue, CopyOnWriteArrayList, CopyOnWriteArraySet, ConcurrentMap.

Давайте сначала посмотрим на ArrayList.

1.1 Базовая операция инициализации ArrayList

Прежде всего, давайте рассмотрим использование ArrayList, Далее следует инициализировать ArrayList, а массив хранит значения типа Integer.

new ArrayList<Integer>();

Так что же делает нижний слой?

1.2 Основной принцип ArrayList

1.2.1 Инициализация массива

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Создается пустой массив емкостью 0. Согласно официальному англоязычному комментарию, емкость здесь должна быть 10, но на самом деле она равна 0. О том, почему она не 10, мы поговорим позже.

1.2.1 Операция добавления в ArrayList

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

Дело в этом шаге: elementData[size++] = e; size++ и elementData[xx]=e, эти две операциини один原子操作(Неделимая операция или последовательность операций, которые либо все выполняются успешно, либо ни одна из них не выполняется).

1.2.2 Анализ исходного кода расширения ArrayList

(1) При выполнении операции добавления сначала будет подтверждено, превышен ли размер массива.

ensureCapacityInternal(size + 1);

(2) Рассчитать текущую емкость массива calculateCapacity

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

minCapacity: значение равно 1

elementData: представляет текущий массив

Давайте сначала посмотрим на метод sureCapacityInternal, вызываемый гарантиейCapacityInternal.

calculateCapacity(elementData, minCapacity)

Метод calculateCapacity выглядит следующим образом:

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

elementData: представляет текущий массив, при добавлении первого элемента elementData равен DEFAULTCAPACITY_EMPTY_ELEMENTDATA (пустой массив)

minCapacity: равно 1

DEFAULT_CAPACITY: равно 10

вернуть Math.max(DEFAULT_CAPACITY, minCapacity) = 10

Резюме: Итак, при добавлении элементов в первый раз размер вычисляемого массива равен 10.

(3) Определить текущую емкость.

minCapacity = 10

elementData.length=0

Резюме: поскольку minCapacity > elementData.length, поэтомуДля первого расширения вызовите методrow(), чтобы расширить от 0 до 10..

(4) Вызвать метод роста

старая емкость = 0, новая емкость = 10.

Затем выполните elementData = Arrays.copyOf(elementData, newCapacity);

Выполните операцию копирования массива для текущего массива и размера емкости и назначьте его для elementData.Емкость массива установлена ​​на 10

Значение elementData и значение DEFAULTCAPACITY_EMPTY_ELEMENTDATA будут разными.

(5) Затем присвоить элемент первому элементу массива, а размер увеличивается на 1

elementData[size++] = e;

(6) При добавлении второго элемента значение, передаваемое в параметрsureCapacityInternal, равно 2.

ensureCapacityInternal(size + 1)

размер=1, размер+1=2

(7) При добавлении элементов во второй раз выполнить calculateCapacity

Значение elementData не равно значению DEFAULTCAPACITY_EMPTY_ELEMENTDATA, поэтому верните 2 напрямую.

(8) При добавлении элементов во второй раз выполните sureExplicitCapacity

Поскольку minCapacity равно 2, что меньше текущей длины массива, равной 10, расширение не выполняется и метод роста не выполняется.

(9) Добавьте второй элемент в массив, и размер увеличится на 1

elementData[size++] = e

(10) Когда добавляется 11-й элемент, вызывается метод роста для расширения

minCapacity=11, elementData.length=10, вызвать метод роста.

（11）扩容1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity=10, сначала преобразуйте его в 1010 во вторичной системе, а затем сдвиньте его на один бит вправо, чтобы получить 0101, что соответствует десятичному числу 5, поэтому newCapacity=10+5=15, что равно 15 после расширения в 1,5 раза. .

(12) Резюме

• 1. ArrayList инициализируется как空数组
• 2. Операция добавления ArrayList не является потокобезопасной.
• 3. Когда ArrayList добавляет первый элемент, емкость массива устанавливается равной10
• 4. Когда массив ArrayList превысит текущую емкость, расширьте до1.5倍(Если результат вычисления десятичный, округлить в меньшую сторону), после первого расширения емкость равна 15, а при втором расширении до 22...
• 5. ArrayList скопирует массив в первый раз и после расширения вызоветArrays.copyOfметод.

1.3 Безопасен ли ArrayList в однопоточной среде?

Сцены:

мы проезжаем添加积木的例子Чтобы проиллюстрировать, что ArrayList является потокобезопасным в рамках одного потока.

строительные блоки三角形A,四边形B,五边形C,六边形D,五角星EДобавляйте их в коробку по очереди.В коробке 5 квадратов, и каждый квадрат может положить строительный блок.

Код:

(1) На этот раз мы используем новый класс строительных блоковBuildingBlockWithName

Этот класс строительных блоков может передавать форму формы и имя имени

/**
 * 积木类
 * @author: 悟空聊架构
 * @create: 2020-08-27
 */
class BuildingBlockWithName {
    String shape;
    String name;
    public BuildingBlockWithName(String shape, String name) {
        this.shape = shape;
        this.name = name;
    }
    @Override
    public String toString() {
        return "BuildingBlockWithName{" + "shape='" + shape + ",name=" + name +'}';
    }
}

(2) Инициализировать массив

ArrayList<BuildingBlock> arrayList = new ArrayList<>();

(3) Добавьте треугольник A, четырехугольник B, пятиугольник C, шестиугольник D и пентаграмму E по очереди.

arrayList.add(new BuildingBlockWithName("三角形", "A"));
arrayList.add(new BuildingBlockWithName("四边形", "B"));
arrayList.add(new BuildingBlockWithName("五边形", "C"));
arrayList.add(new BuildingBlockWithName("六边形", "D"));
arrayList.add(new BuildingBlockWithName("五角星", "E"));

(4) ПроверкаarrayListСоответствует ли содержимое и порядок элементов добавленным

BuildingBlockWithName{shape='三角形,name=A}
BuildingBlockWithName{shape='四边形,name=B}
BuildingBlockWithName{shape='五边形,name=C}
BuildingBlockWithName{shape='六边形,name=D}
BuildingBlockWithName{shape='五角星,name=E}

Мы видим, что результаты действительно совпадают.

резюме:В однопоточной среде ArrayList является потокобезопасным.

1.4 ArrayList небезопасен при многопоточности

Сценарий выглядит следующим образом:20 потоков случайным образом добавляют блок любой формы в ArrayList.

(1) Реализация кода: 20 потоков случайным образом сохраняют строительный блок в массиве.

(2) Распечатайте результат: после запуска программы каждый поток сохраняет только один случайный строительный блок.

Строительные блоки будут постоянно храниться в массиве, и несколько потоков будут конкурировать за квалификацию хранения массива.Во время процесса хранения будет выдано исключение:ConcurrentModificationException(Исключение для параллельной модификации)

Exception in thread "10" Exception in thread "13" java.util.ConcurrentModificationException

Это распространенное исключение параллелизма: java.util.ConcurrentModificationException.

1.5 Как решить проблему небезопасности потока ArrayList?

Есть следующие варианты:

• 1. Используйте Vector вместо ArrayList
• 2. Используйте Collections.synchronized(новый ArrayList())
• 3.CopyOnWriteArrayList

1.6 Гарантируется, что Vector является потокобезопасным?

Проанализируем исходный код вектора.

1.6.1 Инициализация вектора

Начальная вместимость 10

public Vector() {
    this(10);
}

1.6.2 Операция добавления является потокобезопасной

Добавить метод добавленsynchronized, чтобы гарантировать, что операция добавления является потокобезопасной (чтобы обеспечить видимость, атомарность, упорядоченность), если вы не понимаете этих концепций, вы можете прочитать предыдущую статью — "Встречный интервьюер | 14 схем | Никогда не бойся быть спрошенным изменчивым!

1.6.3 Расширение вектора в 2 раза

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

Уведомление:емкостиIncrement может быть передано значение во время инициализации, если оно не передано, по умолчанию оно равно 0. Если передано, oldCapacity+capacityIncrement устанавливается для первого расширения и удваивается для второго расширения.

недостаток:Хотя потокобезопасность гарантируется, но из-за добавления эксклюзивных блокировокsynchronized, вызовет блокировку, поэтомуСнижение производительности.

1.6.4 Используйте стандартные блоки для имитации операции добавления вектора

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

1.7 Используйте Collections.synchronizedList для обеспечения безопасности потоков

Мы можем использовать метод Collections.synchronizedList, чтобы обернуть ArrayList.

List<Object> arrayList = Collections.synchronizedList(new ArrayList<>());

Почему это потокобезопасно после такой инкапсуляции?

Анализ исходного кода:Поскольку Collections.synchronizedList инкапсулирует список, все методы работы со спискомsynchronizedключевое слово (кроме iterator()), которое эквивалентно блокировке для всех операций, поэтому его использование потокобезопасно (кроме перебора массивов).

Уведомление:При переборе массива синхронизацию необходимо выполнять вручную. Официальный пример выглядит следующим образом:

synchronized (list) {
     Iterator i = list.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
}

1.8 Используйте CopyOnWriteArrayList для обеспечения потокобезопасности

1.8.1 Идея CopyOnWriteArrayList

• Копирование при записи: копирование при записи, идея разделения чтения и записи.
• Операция записи: при добавлении элементов не добавляйте их непосредственно в текущий контейнер, а сначала скопируйте массив, а после добавления элементов в новый массив укажите ссылку исходного контейнера на новый контейнер. Поскольку массив изменяется с помощью ключевого слова volatile, когда массив переназначается, другие потоки могут сразу узнать (видимость volatile)
• Операция чтения: при чтении массива читать старый массив без блокировки.
• Разделение чтения-записи: операция записи — копирование нового массива для записи, а операция чтения — чтение старого массива, поэтому это разделение чтения-записи.

1.8.2 Как использовать

CopyOnWriteArrayList<BuildingBlockWithName> arrayList = new CopyOnWriteArrayList<>();

1.8.3 Анализ базового исходного кода

Процесс добавления:

• Сначала определите реентерабельную блокировкуReentrantLock
• Перед добавлением элемента получите блокировкуlock.lock()
• При добавлении элементов сначала скопируйте текущий массивArrays.copyOf
• При добавлении элементов разверните +1 (len + 1)
• После добавления элемента укажите ссылку массива на только что добавленный массивsetArray(newElements)

Почему другие потоки могут узнать об этом сразу после переназначения массива?

Поскольку массив здесь изменен с помощью volatile,哇，又是volatile, это ключевое слово прекрасно ^_^

 private transient volatile Object[] array;

1.8.4 Разница между ReentrantLock и синхронизированным

划重点

Тот же пункт:

• 1. Оба используются для координации многопоточного доступа к общим объектам и переменным.
• 2. Все блокировки являются реентерабельными, один и тот же поток может получить одну и ту же блокировку несколько раз.
• 3. Оба гарантируют видимость и взаимное исключение

разница:

• 1. ReentrantLock показывает получение и освобождение блокировок, а синхронизированный неявно захватывает и снимает блокировки.
• 2. ReentrantLock может реагировать на прерывания, но синхронизированный не может реагировать на прерывания, что обеспечивает большую гибкость при обработке недоступности блокировки.
• 3. ReentrantLock — это уровень API, синхронизированный — это уровень JVM.
• 4. ReentrantLock может реализовать справедливую и нечестную блокировку.
• 5. ReentrantLock может связывать несколько условий через Condition
• 6. Базовая реализация отличается, synchronized — это синхронная блокировка, использующая пессимистическую стратегию параллелизма, lock — синхронная неблокирующая, использующая оптимистическую стратегию параллелизма.

1.8.5 Разница между блокировкой и синхронизацией

• 1. Lock должен получить блокировку и снять блокировку вручную. Это как разница между АКПП и МКПП
• 1.Lock — это интерфейс, а synchronized — это ключевое слово в Java, а synchronized — это встроенная языковая реализация.
• 2.synchronized автоматически освобождает блокировку, занятую потоком, при возникновении исключения, поэтому это не вызовет феномен взаимоблокировки; и когда в блокировке возникает исключение, если блокировка активно не снимается через unLock(), скорее всего, вызвать явление взаимоблокировки, поэтому при использовании блокировки вам необходимо снять блокировку в блоке finally.
• 3.Lock может заставить поток, ожидающий блокировки, реагировать на прерывание, а синхронизированный - нет.При использовании синхронизированного ожидающий поток будет ждать вечно и не может реагировать на прерывание.
• 4. С помощью блокировки вы можете узнать, успешно ли получена блокировка, но не синхронизирована.
• 5.Lock может повысить эффективность операций чтения несколькими потоками за счет реализации блокировок чтения-записи.

2. Поточно-небезопасный HashSet

С предыдущим обширным объяснением небезопасности потока ArrayList и того, как использовать другие методы для обеспечения безопасности потока, теперь должно быть легче понять HashSet.

2.1 Использование HashSet

Использование заключается в следующем:

Set<BuildingBlockWithName> Set = new HashSet<>();
set.add("a");

Начальная мощность = 10, коэффициент загрузки = 0,75 (когда количество элементов достигает 75% мощности, начинается расширение)

2.2 Основной принцип HashSet

public HashSet() {
    map = new HashMap<>();
}

Нижний слой по-прежнему HashMap().

Тестовый сайт:Почему операция добавления HashSet должна передавать только один параметр (значение), а HashMap — два параметра (ключ и значение)

2.3 Операция добавления HashSet

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Экзаменационный ответ:Поскольку в операции добавления HashSet ключ равен переданному значению, а значение — ПРИСУТСТВУЮЩЕЕ, а ПРИСУТСТВУЮЩЕЕ — это новый объект();, поэтому на карту передается ключ = e, значение = новый объект. Хэш заботится только о ключе, а не о значении.

Почему HashSet небезопасен:Базовая операция добавления не гарантирует видимости и атомарности. Так что не потокобезопасно.

2.4 Как обеспечить безопасность потоков

• 1. Используйте Collections.synchronizedSet

  Set<BuildingBlockWithName> set = Collections.synchronizedSet(new HashSet<>());
  

• 2. Используйте CopyOnWriteArraySet

  CopyOnWriteArraySet<BuildingBlockWithName> set = new CopyOnWriteArraySet<>();
  

2.5 Нижний слой CopyOnWriteArraySet по-прежнему использует CopyOnWriteArrayList.

public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}

3. Поточно-небезопасный HashMap

3.1 Использование HashMap

Точно так же HashMap, как и HashSet, также небезопасен для потоков в многопоточной среде.

Map<String, BuildingBlockWithName> map = new HashMap<>();
map.put("A", new BuildingBlockWithName("三角形", "A"));

3.2 Небезопасное решение потока HashMap:

• 1.Collections.synchronizedMap

Map<String, BuildingBlockWithName> map2 = Collections.synchronizedMap(new HashMap<>());

• 2.ConcurrentHashMap

ConcurrentHashMap<String, BuildingBlockWithName> set3 = new ConcurrentHashMap<>();

3.3 Принцип ConcurrentHashMap

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

4. Другие коллекции

LinkedList:Небезопасный поток, такой же, как ArrayListНабор деревьев:Небезопасный поток, такой же, как HashSetСвязанныйHashSet:Небезопасный поток, такой же, как HashSetКарта дерева:То же, что и HashMap, поток небезопасенХеш-таблица:потокобезопасность

Суммировать

В первой части этой статьи подробно описывается лежащий в основе принцип расширения коллекции ArrayList и демонстрируется, что небезопасность потоков ArrayList приведет к созданию并发修改异常. Затем с помощью анализа исходного кода объясняются три способа обеспечения безопасности потоков:

• Vectorсквозьaddдобавить перед методомsynchronizedдля обеспечения безопасности потоков
• Collections.synchronized()Это обертывание массива и добавление его перед методом работы с массивомsynchronizedдля обеспечения безопасности потоков
• CopyOnWriteArrayListпройти через写时复制для обеспечения безопасности резьбы.

Во второй части объясняется небезопасность потоков HashSet, которая обеспечивает безопасность потоков двумя способами:

• Collections.synchronizedSet
• CopyOnWriteArraySet

В третьей части объясняется небезопасность потоков HashMap, которая гарантируется двумя способами:

• Collections.synchronizedMap
• ConcurrentHashMap

Кроме того, в процессе объяснения также подробно сравнивается разница между ReentrantLock и синхронизированным и Lock и синхронизированным.

Пасхальные яйца:Вы умны, вы, должно быть, обнаружили, что в коллекции не хватает одноговажные вещи:ЭтоQueue. Ждем продолжения?

Шлюха? Вперед -> Смотреть -> Нравится - Любимое! ! !

Я Вуконг, кодовый фермер, который стремится стать сильнее! Я собираюсь стать Супер Сайяном!

Кроме того, вы можете выполнить поиск «Архитектура чата Wukong» или PassJava666 в WeChat и добиться прогресса вместе! мойдомашняя страница гитхаба, Подписывайтесь на меняSpring CloudАктуальный проект"До свидания"