Требуется простое объяснение, как чередование блокировок работает с ConcurrentHashMap

Согласно Java Concurrency in Practice, глава 11.4.3 гласит:

Разделение блокировок иногда может быть расширено до блокирования разделов на переменном наборе независимых объектов, и в этом случае это называется чередованием блокировок. Например, реализация ConcurrentHashMap использует массив из 16 блокировок, каждая из которых защищает 1/16 хэш-сегментов; ведро N охраняется замком N мод 16.

У меня все еще есть проблемы с пониманием и визуализацией механизма блокировки замков и ведер. Может кто-нибудь объяснить это хорошими понимающими словами :)

Заранее спасибо.


person GedankenNebel    schedule 22.04.2013    source источник


Ответы (3)


Хеш-карта строится на основе массива, где хеш-функция сопоставляет объект с элементом в базовом массиве. Скажем, базовый массив имеет 1024 элемента - ConcurrentHashMap фактически превращает его в 16 различных подмассивов по 64 элемента, например {0, 63}, {64, 127} и т. Д. Каждый подмассив имеет свою собственную блокировку, поэтому изменение подмассива {0, 63} не влияет на подмассив {64, 127} - один поток может писать в первый подмассив, в то время как другой поток записывает во второй подмассив.

person Zim-Zam O'Pootertoot    schedule 22.04.2013
comment
Хорошо, я понял. Но как насчет того, чтобы два или более потока пытались изменить все в подмассиве {0,63}? - person GedankenNebel; 22.04.2013
comment
Затем он первым приходит первым - первый поток, получивший блокировку, вносит свои изменения, затем, когда он заканчивает, второй поток вносит свои изменения. ConcurrentHashMap имеет такие методы, как replace, чтобы гарантировать, что второй поток случайно не перезапишет изменения первого потока. - person Zim-Zam O'Pootertoot; 22.04.2013
comment
Я не думаю, что на самом деле он первым пришел, первым обслужен, насколько я понимаю (у меня нет точной цитаты, но я узнал это из Java Concurrency in Practice), справедливость гарантируется только тогда, когда она явная, например, в конструкторах для разных явные Lock реализации, такие как ReentrantLock, или очереди, такие как ArrayBlockingQueue. (Я знаю, что это старая ветка, извините) - person Marcelo; 26.10.2015
comment
Я очень кратко рассмотрел реализацию Java 8, и я не вижу массивов уровня сегмента. Я знаю, что приведенный выше ответ написан до java 8. Но может ли кто-нибудь уточнить, что теперь сегменты - это не что иное, как отдельные сегменты или строки в таблице? Слово «блокировка чередования» устарело, поскольку мы не выполняем блокировку для чередования строк? - person Giri; 01.04.2017

Разница между блокировкой в ​​Collections.synchronizedMap() и ConcurrentHashMap заключается в следующем:

Если несколько потоков будут обращаться к Collections.synchronizedMap() часто, возникнет много конфликтов, поскольку каждый метод синхронизируется с использованием общей блокировки (т. Е. Если поток X вызывает метод на Collections.synchronizedMap(), все другие потоки будут заблокированы от вызова любого метода на Collections.synchronizedMap() пока поток X не вернется из вызванного им метода).

ConcurrentHashMap имеет переменное количество блокировок (по умолчанию 16), каждая из которых защищает сегмент ключей в ConcurrentHashMap. Таким образом, для ConcurrentHashMap со 160 ключами каждый замок будет защищать 10 элементов. Следовательно, методы, работающие с ключом (get, put, set и т. Д.), Блокируют доступ только к другим методам, работающим с ключом, ключи которого находятся в том же сегменте. Например, если поток X вызывает put(0, someObject), а затем поток Y вызывает put(10, someOtherObject), эти вызовы могут выполняться одновременно, и потоку Y не нужно ждать, пока поток X вернется из put(0, someObject). Пример приведен ниже.

Кроме того, некоторые методы, такие как size() и isEmpty(), вообще не защищены. Хотя это обеспечивает больший параллелизм, это означает, что они не являются строго согласованными (они не отражают состояние, которое одновременно изменяется).

public static void main(String[] args) {
  ConcurrentHashMap<Integer, Object> map = new ConcurrentHashMap<>(160);

  new Thread(new Runnable() {
    @Override
    public void run() {
      map.put(0, "guarded by one lock");
    }
  }.start();

  new Thread(new Runnable() {
    @Override
    public void run() {
      map.put(10, "guarded by another lock");
    }
  }.start();

  new Thread(new Runnable() {
    @Override
    public void run() {
      // could print 0, 1, or 2
      System.out.println(map.count());
    }
  }.start();
}
person ashish_388235    schedule 22.04.2013
comment
HashMap в java не является потокобезопасным, HashTable - это. Первый сценарий, о котором вы говорите, касается HashTable. - person Big O; 03.12.2015

Ключевым понятием здесь является «ведро». вместо того, чтобы использовать глобальную блокировку для всей этой хэш-таблицы, он использует одну небольшую блокировку для каждого сегмента. Это также хороший аналог сортировки по корзине, которая может улучшить сложность сортировки.

person BufBills    schedule 17.06.2015