集合与同步集合的比较 - 版本历史

Eijux：/* 对比 */

2022-11-30T11:06:33Z

对比

←上一版本		2022年11月30日 (三) 19:06的版本
第141行：		第141行：
	\| 对比		\| 对比
	\|		\|
	# ~~使用“Synchronized”锁定同步变量（锁定对象）；~~		# 使用“<span style="color: blue">Synchronized</span>”锁定同步变量（锁定对象）；
	# 迭代器方法不同步；		# 迭代器方法不同步；
	\|		\|
	# ~~使用“ReentrantLock”锁定修改操作代码块；~~		# 使用“<span style="color: blue">ReentrantLock</span>”锁定修改操作代码块；
	# 迭代器方法同步；		# 迭代器方法同步；
	\|}		\|}
	~~# 同步的方式不一样~~
	#:
	#:
	~~# 是否同步；~~

	== Map ==		== Map ==

Eijux：/* 为什么不推荐 Vector（和Stack） */

2020-10-21T05:09:34Z

为什么不推荐 Vector（和Stack）

←上一版本		2020年10月21日 (三) 13:09的版本
第14行：		第14行：
	=== 为什么不推荐 Vector（和Stack） ===		=== 为什么不推荐 Vector（和Stack） ===
	*（Stack 继承于 Vector）都使用“synchronized”修饰方法（包括读操作），实现同步；		*（Stack 继承于 Vector）都使用“synchronized”修饰方法（包括读操作），实现同步；


	因为：		因为：
	# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；		# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；

Eijux：/* 为什么不推荐 HashTable */

2020-10-21T05:09:12Z

为什么不推荐 HashTable

←上一版本		2020年10月21日 (三) 13:09的版本
第159行：		第159行：

	=== 为什么不推荐 HashTable ===		=== 为什么不推荐 HashTable ===
			* 使用“synchronized”修饰方法（包括读操作），实现同步；


	因为：		因为：
	# 对于不需要同步的场景：HashMap没有锁开销更适用；		# 对于不需要同步的场景：HashMap没有锁开销更适用；
	# ~~对于需要同步的场景：和synchronizedMap实现的功能一样，却不能有null；~~		# 对于需要同步的场景：ConcurrentHashMap的锁粒度更低更合适；
	# Hashtable继承了被弃用的父类“Dictionary”；		# Hashtable继承了被弃用的父类“Dictionary”；
	#: Dictionary：除了常规的get，put请求外，还提供了一些遍历的方法，返回的是“Enumeration”类型（Enumeration接口，已经被功能更多更方便的Iterator替换了）		#: Dictionary：除了常规的get，put请求外，还提供了一些遍历的方法，返回的是“Enumeration”类型（Enumeration接口，已经被功能更多更方便的Iterator替换了）

Eijux：/* 为什么不推荐 Vector（和Stack） */

2020-10-21T05:05:19Z

为什么不推荐 Vector（和Stack）

←上一版本		2020年10月21日 (三) 13:05的版本
第13行：		第13行：

	=== 为什么不推荐 Vector（和Stack） ===		=== 为什么不推荐 Vector（和Stack） ===
	*（Stack 继承于 ~~Vector）~~		*（Stack 继承于 Vector）都使用“synchronized”修饰方法（包括读操作），实现同步；
	因为：		因为：
	# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；		# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；
第19行：		第19行：
	#: 通常需要同步一个整个序列的操作，同步单个操作是不安全的。		#: 通常需要同步一个整个序列的操作，同步单个操作是不安全的。
	#: 如：在Vector上进行迭代操作，仍然需要手动加一个锁，以避免其他人同时更改集合，否则将导致“ConcurrentModificationException”；		#: 如：在Vector上进行迭代操作，仍然需要手动加一个锁，以避免其他人同时更改集合，否则将导致“ConcurrentModificationException”；


	=== SynchronizedList 与 CopyOnWriteArrayList ===		=== SynchronizedList 与 CopyOnWriteArrayList ===

Eijux：/* ConcurrentHashMap */

2020-10-21T05:02:24Z

ConcurrentHashMap

←上一版本		2020年10月21日 (三) 13:02的版本
第262行：		第262行：
	*# 在JDK1.8之前，采用'''分段锁（“Segment”）'''：每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响（实际就是对桶加锁）；		*# 在JDK1.8之前，采用'''分段锁（“Segment”）'''：每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响（实际就是对桶加锁）；
	*# JDK1.8之后，取消了Segment字段，采用'''行锁'''：直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率；		*# JDK1.8之后，取消了Segment字段，采用'''行锁'''：直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率；
	*		* 读不加锁，写操作加锁；
			*: '''volatile'''关键字已经足以保证线程在读取数据时不会读取到脏数据，所以没有加锁的必要；

	==== 对比 ====		==== 对比 ====

Eijux：/* synchronizedMap 与 ConcurrentHashMap */

2020-10-21T04:59:09Z

synchronizedMap 与 ConcurrentHashMap

@@ 第172行： / 第172行： @@
 ==== synchronizedMap ====
-synchronizedMap：（与“SynchronizedList”类似）<s>使用内部锁（Synchronized）修饰每一个方法</s>，锁住的是整个Table对象；
+部分源码：
 <syntaxhighlight lang="java">
 private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
      final Object mutex;        // Object on which to synchronize
@@ 第184行： / 第186行： @@
+     }
 </syntaxhighlight>
-* synchronizedMap 的“entrySet()”方法返回的是“SynchronizedSet<E>”；
+    public V put(K key, V value) {
-*“SynchronizedSet”（、“SynchronizedList”）继承自“SynchronizedCollection”，其迭代器“Iterator”操作并不加锁；
+        return putVal(key, value, false);
-==== ConcurrentHashMap ====
+    /** Implementation for put and putIfAbsent */
-ConcurrentHashMap 实现了更细粒度的加锁：
+    final V putVal(K key, V value, boolean onlyIfAbsent) {
-* 在JDK1.8之前，采用'''分段锁（“Segment”）'''：每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响（实际就是对桶加锁）；
+        if (key == null || value == null) throw new NullPointerException();
-* JDK1.8之后，取消了Segment字段，采用'''行锁'''：直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率；
+        int hash = spread(key.hashCode());
 ==== 对比 ====
 {| class="wikitable"
-! synchronizedMap !! ConcurrentHashMap
+! !!  synchronizedMap !! ConcurrentHashMap
 |-
-对比
+| 对比
+|
-# 同步整个对象，只有一把锁
+# '''同步整个对象，只有一把锁'''
 # 对整个对象加锁：只允许同一时间内至多一个线程操作整个Map
 # 读写操作都需要加锁

Eijux：/* SynchronizedList 与 CopyOnWriteArrayList */

2020-10-21T04:44:59Z

SynchronizedList 与 CopyOnWriteArrayList

←上一版本		2020年10月21日 (三) 12:44的版本
第22行：		第22行：

	=== SynchronizedList 与 CopyOnWriteArrayList ===		=== SynchronizedList 与 CopyOnWriteArrayList ===
	~~二者主要区别在于实现~~
	~~# 同步的方式不一样（操作加锁；修改复制、操作加锁）；~~
	~~# 使用的锁不一样（内部锁、ReentrantLock）；~~
	~~# 迭代器方法是否同步；~~

			==== SynchronizedList ====
	~~SynchronizedList~~ 部分源码：		部分源码：
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java" line highlight="8,13,16,19,23,26">
	public int ~~indexOf(Object o~~) {		static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
	synchronized (mutex) {return list.~~indexOf~~(o);}		...
			SynchronizedList(List<E> list) {
			super(list);
			this.list = list;
			}
			SynchronizedList(List<E> list, Object mutex) {
			super(list, mutex);
			this.list = list;
			}
			...
			public E get(int index) {
			synchronized (mutex) {return list.get(index);}
	}		}
	public int ~~lastIndexOf(Object o~~) {		public void add(int index, E element) {
	synchronized (mutex) {~~return~~ list.~~lastIndexOf~~(o);}		synchronized (mutex) {list.add(index, element);}
	}		}
			public E remove(int index) {
	public ~~boolean addAll~~(int index~~, Collection<? extends E> c~~) {		synchronized (mutex) {return list.remove(index);}
	synchronized (mutex) {return list.~~addAll~~(index~~, c~~);}
	}		}
			...
	public ListIterator<E> listIterator() {		public ListIterator<E> listIterator() {
	return list.listIterator(); // Must be manually synched by user		return list.listIterator(); // Must be manually synched by user
	}		}

	public ListIterator<E> listIterator(int index) {		public ListIterator<E> listIterator(int index) {
	return list.listIterator(index); // Must be manually synched by user		return list.listIterator(index); // Must be manually synched by user
第50行：		第55行：
	</syntaxhighlight>		</syntaxhighlight>
	由源码可以看出：		由源码可以看出：
			* 继承于“SynchronizedCollection”，都是'''使用Synchronized锁住了对象的同步变量（对整个对象加锁）'''；
	* synchronizedList是将List集合作为参数来创建的synchronizedList集合；		* synchronizedList是将List集合作为参数来创建的synchronizedList集合；
	* 采用内部锁（'''synchronized'''~~）的方法，所开销大（依赖于Java版本对synchronized优化了）；~~		* 采用内部锁（'''synchronized'''）开销大（依赖于Java版本对synchronized优化了）；
	* 迭代器（ListIterator）方法却没有加锁处理；		* 迭代器（ListIterator）方法却没有加锁处理；


	CopyOnWriteArrayList 部分源码：		==== CopyOnWriteArrayList ====
	<syntaxhighlight lang="java">		部分源码：
			<syntaxhighlight lang="java" line highlight="7,11,35">
			public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	/** The array, accessed only via getArray/setArray. */		/** The array, accessed only via getArray/setArray. */
	private volatile transient Object[] array;//保证了线程的可见性		private volatile transient Object[] array;//保证了线程的可见性
			...
			@SuppressWarnings("unchecked")
			private E get(Object[] a, int index) {
			return (E) a[index];
			}
			...
	public void add(int index, E element) {		public void add(int index, E element) {
	final ReentrantLock lock = this.lock;		final ReentrantLock lock = this.lock;
第67行：		第80行：
	int len = elements.length;		int len = elements.length;
	if (index > len \|\| index < 0)		if (index > len \|\| index < 0)
	throw new IndexOutOfBoundsException("Index: "+index+		throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
	", Size: "+len);
	Object[] newElements;		Object[] newElements;
	int numMoved = len - index;		int numMoved = len - index;
第76行：		第88行：
	newElements = new Object[len + 1]; //将add的参数赋值		newElements = new Object[len + 1]; //将add的参数赋值
	System.arraycopy(elements, 0, newElements, 0, index);		System.arraycopy(elements, 0, newElements, 0, index);
	System.arraycopy(elements, index, newElements, index + 1,		System.arraycopy(elements, index, newElements, index + 1, numMoved);
	numMoved);
	}		}
	newElements[index] = element;		newElements[index] = element;
第99行：		第110行：
	Object[] newElements = new Object[len - 1];		Object[] newElements = new Object[len - 1];
	System.arraycopy(elements, 0, newElements, 0, index);		System.arraycopy(elements, 0, newElements, 0, index);
	System.arraycopy(elements, index + 1, newElements, index,		System.arraycopy(elements, index + 1, newElements, index, numMoved);
	numMoved);
	setArray(newElements); //将原数组指向新的数组		setArray(newElements); //将原数组指向新的数组
	}		}
第118行：		第128行：
	由其源码可以看出：		由其源码可以看出：
	:执行add方法和remove方法的时候，分别创建了一个当前数组长度+1和-1的数组，将数据copy到新数组中，然后执行修改操作。修改完之后调用setArray方法来指向新的数组。		:执行add方法和remove方法的时候，分别创建了一个当前数组长度+1和-1的数组，将数据copy到新数组中，然后执行修改操作。修改完之后调用setArray方法来指向新的数组。
	* 使用'''~~ReentrantLock~~'''~~可重入锁来保证同步；~~		* '''使用“ReentrantLock”对修改操作代码块加锁'''；
	* 并且使用volatile修饰数组来保证修改后的可见性；		* 并且使用volatile修饰数组来保证修改后的可见性；
	* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；		* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；


			==== 对比 ====
			二者主要区别在于实现：
			{\| class="wikitable"
			! !! SynchronizedList !! CopyOnWriteArrayList
			\|-
			\| 对比
			\|
			# 使用“Synchronized”锁定同步变量（锁定对象）；
			# 迭代器方法不同步；
			\|
			# 使用“ReentrantLock”锁定修改操作代码块；
			# 迭代器方法同步；
			\|}
			# 同步的方式不一样
			#:
			#:
			# 是否同步；

	== Map ==		== Map ==

Eijux：/* Map */

2020-10-21T04:21:34Z

Map

←上一版本		2020年10月21日 (三) 12:21的版本
第123行：		第123行：

	== Map ==		== Map ==

			Map 相关的有：
			# HashMap、TreeMap、SortedMap、LinkedHashMap：线程不安全；
			# Hashtable：线程安全（但不推荐使用）；
			# synchronizedMap：线程安全，Collections子类实现；
			# ConcurrentHashMap：线程安全，采用修改copy的方法解决同步问题；

			=== 为什么不推荐 HashTable ===
			因为：
			# 对于不需要同步的场景：HashMap没有锁开销更适用；
			# 对于需要同步的场景：和synchronizedMap实现的功能一样，却不能有null；
			# Hashtable继承了被弃用的父类“Dictionary”；
			#: Dictionary：除了常规的get，put请求外，还提供了一些遍历的方法，返回的是“Enumeration”类型（Enumeration接口，已经被功能更多更方便的Iterator替换了）


			* HashTable的 K，V 都不能是null；

			=== synchronizedMap 与 ConcurrentHashMap ===

			==== synchronizedMap ====
			synchronizedMap：（与“SynchronizedList”类似）<s>使用内部锁（Synchronized）修饰每一个方法</s>，锁住的是整个Table对象；


			关于'''“锁住整个对象”，是因为“使用Synchronized锁住了对象的同步变量”'''，而非单纯用Synchronized修饰方法：（[[Synchronized关键字的使用]]）
			<syntaxhighlight lang="java">
			private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
			final Object mutex; // Object on which to synchronize
			...
			public V put(K key, V value) {
			synchronized (mutex) {return m.put(key, value);}
			}
			</syntaxhighlight>


			* synchronizedMap 的“entrySet()”方法返回的是“SynchronizedSet<E>”；
			*“SynchronizedSet”（、“SynchronizedList”）继承自“SynchronizedCollection”，其迭代器“Iterator”操作并不加锁；

			==== ConcurrentHashMap ====
			ConcurrentHashMap 实现了更细粒度的加锁：
			* 在JDK1.8之前，采用'''分段锁（“Segment”）'''：每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响（实际就是对桶加锁）；
			* JDK1.8之后，取消了Segment字段，采用'''行锁'''：直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率；

			==== 对比 ====
			{\| class="wikitable"
			! synchronizedMap !! ConcurrentHashMap
			\|-
			对比
			\|
			# 同步整个对象，只有一把锁
			# 对整个对象加锁：只允许同一时间内至多一个线程操作整个Map
			# 读写操作都需要加锁
			# SynchronizedHashMap会返回“Iterator”，当遍历时进行修改会抛出异常“ConcurrentModificationException”
			\|
			# 不同步整个Map，'''使用多个锁'''实现
			# '''只对哈希表的某一个key加锁'''（或分段加锁）
			# '''读不加锁，写操作加锁'''
			# 在对象层次上不存在锁（即不会阻塞线程）
			# ConcurrentHashMap不会抛出“ConcurrentModificationException”，即使一个线程在遍历的同时，另一个线程尝试进行修改
			\|}

Eijux：/* List = */

2020-10-21T02:54:18Z

List =

←上一版本		2020年10月21日 (三) 10:54的版本
第4行：		第4行：
	集合框架中的集合、映射，一般都不是线程安全的，而实现线程安全也有几种方式。		集合框架中的集合、映射，一般都不是线程安全的，而实现线程安全也有几种方式。

	== List ===		== List ==

	List相关的有：		List相关的有：
第121行：		第121行：
	* 并且使用volatile修饰数组来保证修改后的可见性；		* 并且使用volatile修饰数组来保证修改后的可见性；
	* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；		* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；


	== Map ==		== Map ==

2020年10月21日 (三) 02:54 Eijux

2020-10-21T02:54:07Z

←上一版本		2020年10月21日 (三) 10:54的版本
第1行：		第1行：
	[[category:Java]]		[[category:Java]]

			== 关于集合、同步集合 ==
			集合框架中的集合、映射，一般都不是线程安全的，而实现线程安全也有几种方式。

			== List ===

			List相关的有：
			# Vector：线程安全（但不推荐使用）；
			# ArrayList、LinkedList：线程不安全；
			# SynchronizedList：线程安全，Collections子类实现；
			# CopyOnWriteArrayList：线程安全，采用修改copy的方法解决同步问题；

			=== 为什么不推荐 Vector（和Stack） ===
			*（Stack 继承于 Vector）
			因为：
			# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；
			# 对于需要同步的场景：Vector 对操作方法加锁，却没有对迭代器操作加锁；
			#: 通常需要同步一个整个序列的操作，同步单个操作是不安全的。
			#: 如：在Vector上进行迭代操作，仍然需要手动加一个锁，以避免其他人同时更改集合，否则将导致“ConcurrentModificationException”；


			=== SynchronizedList 与 CopyOnWriteArrayList ===
			二者主要区别在于实现
			# 同步的方式不一样（操作加锁；修改复制、操作加锁）；
			# 使用的锁不一样（内部锁、ReentrantLock）；
			# 迭代器方法是否同步；


			SynchronizedList 部分源码：
			<syntaxhighlight lang="java">
			public int indexOf(Object o) {
			synchronized (mutex) {return list.indexOf(o);}
			}
			public int lastIndexOf(Object o) {
			synchronized (mutex) {return list.lastIndexOf(o);}
			}

			public boolean addAll(int index, Collection<? extends E> c) {
			synchronized (mutex) {return list.addAll(index, c);}
			}

			public ListIterator<E> listIterator() {
			return list.listIterator(); // Must be manually synched by user
			}

			public ListIterator<E> listIterator(int index) {
			return list.listIterator(index); // Must be manually synched by user
			}
			</syntaxhighlight>
			由源码可以看出：
			* synchronizedList是将List集合作为参数来创建的synchronizedList集合；
			* 采用内部锁（'''synchronized'''）的方法，所开销大（依赖于Java版本对synchronized优化了）；
			* 迭代器（ListIterator）方法却没有加锁处理；


			CopyOnWriteArrayList 部分源码：
			<syntaxhighlight lang="java">
			/** The array, accessed only via getArray/setArray. */
			private volatile transient Object[] array;//保证了线程的可见性

			public void add(int index, E element) {
			final ReentrantLock lock = this.lock;
			lock.lock();
			try {
			Object[] elements = getArray();
			int len = elements.length;
			if (index > len \|\| index < 0)
			throw new IndexOutOfBoundsException("Index: "+index+
			", Size: "+len);
			Object[] newElements;
			int numMoved = len - index;
			if (numMoved == 0)
			newElements = Arrays.copyOf(elements, len + 1); //copy一份比当前数组长度+1的array数组
			else {
			newElements = new Object[len + 1]; //将add的参数赋值
			System.arraycopy(elements, 0, newElements, 0, index);
			System.arraycopy(elements, index, newElements, index + 1,
			numMoved);
			}
			newElements[index] = element;
			setArray(newElements); //将原数组指向新的数组
			} finally {
			lock.unlock();
			}
			}

			public E remove(int index) {
			final ReentrantLock lock = this.lock;
			lock.lock();
			try {
			Object[] elements = getArray();
			int len = elements.length;
			E oldValue = get(elements, index);
			int numMoved = len - index - 1;
			if (numMoved == 0)
			setArray(Arrays.copyOf(elements, len - 1)); //copy一份比当前数组长度-1的array数组
			else {
			Object[] newElements = new Object[len - 1];
			System.arraycopy(elements, 0, newElements, 0, index);
			System.arraycopy(elements, index + 1, newElements, index,
			numMoved);
			setArray(newElements); //将原数组指向新的数组
			}
			return oldValue;
			} finally {
			lock.unlock();
			}
			}

			/**
			* 将原数组指向新的数组
			*/
			final void setArray(Object[] a) {
			array = a;
			}
			</syntaxhighlight>
			由其源码可以看出：
			:执行add方法和remove方法的时候，分别创建了一个当前数组长度+1和-1的数组，将数据copy到新数组中，然后执行修改操作。修改完之后调用setArray方法来指向新的数组。
			* 使用'''ReentrantLock'''可重入锁来保证同步；
			* 并且使用volatile修饰数组来保证修改后的可见性；
			* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；


			== Map ==

集合与同步集合的比较 - 版本历史

Eijux：​/* 对比 */

Eijux：​/* 为什么不推荐 Vector（和Stack） */

Eijux：​/* 为什么不推荐 HashTable */

Eijux：​/* 为什么不推荐 Vector（和Stack） */

Eijux：​/* ConcurrentHashMap */

Eijux：​/* synchronizedMap 与 ConcurrentHashMap */

Eijux：​/* SynchronizedList 与 CopyOnWriteArrayList */

Eijux：​/* Map */

Eijux：​/* List = */

2020年10月21日 (三) 02:54 Eijux

Eijux：/* 对比 */

Eijux：/* 为什么不推荐 Vector（和Stack） */

Eijux：/* 为什么不推荐 HashTable */

Eijux：/* 为什么不推荐 Vector（和Stack） */

Eijux：/* ConcurrentHashMap */

Eijux：/* synchronizedMap 与 ConcurrentHashMap */

Eijux：/* SynchronizedList 与 CopyOnWriteArrayList */

Eijux：/* Map */

Eijux：/* List = */