面试官：请手写一个 CopyOnWriteMap！

一、背景Java 求职面试中， List 和 Map可以说是经典的八股文必考知识点。

有些面试官喜欢问 ArrayList 和 HashMap 的相关知识，而有些面试官可能会独辟蹊径，重点考察其他 CopyOnWriteArrayList。

或许，很多同学会说，这有什么难的呢？还不是信手拈来？

但，如果面试官让你现场手写一个 CopyOnWriteMap你是否还能那么淡定从容？

本文将系统介绍下 CopyOnWriteArrayList 的原理、优缺点和使用场景，并根据给出 CopyOnWriteMap 的典型代码实现。

二、探讨2.1 CopyOnWriteArrayList 的源码和原理2.1.1 源码下面是该类的一些关键代码：

代码语言：javascript代码运行次数：0运行复制public class CopyOnWriteArrayList

implements List, RandomAccess, Cloneable, java.io.Serializable {

private static final long serialVersionUID = 8673264195747942595L;

/**

* The lock protecting all mutators. (We have a mild preference

* for builtin monitors over ReentrantLock when either will do.)

*/

final transient Object lock = new Object();

/** The array, accessed only via getArray/setArray. */

private transient volatile Object[] array;

/**

* Gets the array. Non-private so as to also be accessible

* from CopyOnWriteArraySet class.

*/

final Object[] getArray() {

return array;

}

/**

* Sets the array.

*/

final void setArray(Object[] a) {

array = a;

}

/**

* Creates an empty list.

*/

public CopyOnWriteArrayList() {

setArray(new Object[0]);

}

/**

* Appends the specified element to the end of this list.

*

* @param e element to be appended to this list

* @return {@code true} (as specified by {@link Collection#add})

*/

public boolean add(E e) {

synchronized (lock) {

Object[] es = getArray();

int len = es.length;

es = Arrays.copyOf(es, len + 1);

es[len] = e;

setArray(es);

return true;

}

}

/**

* Removes the element at the specified position in this list.

* Shifts any subsequent elements to the left (subtracts one from their

* indices). Returns the element that was removed from the list.

*

* @throws IndexOutOfBoundsException {@inheritDoc}

*/

public E remove(int index) {

synchronized (lock) {

Object[] es = getArray();

int len = es.length;

E oldValue = elementAt(es, index);

int numMoved = len - index - 1;

Object[] newElements;

if (numMoved == 0)

newElements = Arrays.copyOf(es, len - 1);

else {

newElements = new Object[len - 1];

System.arraycopy(es, 0, newElements, 0, index);

System.arraycopy(es, index + 1, newElements, index,

numMoved);

}

setArray(newElements);

return oldValue;

}

}

/**

* Saves this list to a stream (that is, serializes it).

*

* @param s the stream

* @throws java.io.IOException if an I/O error occurs

* @serialData The length of the array backing the list is emitted

* (int), followed by all of its elements (each an Object)

* in the proper order.

*/

private void writeObject(java.io.ObjectOutputStream s)

throws java.io.IOException {

s.defaultWriteObject();

Object[] es = getArray();

// Write out array length

s.writeInt(es.length);

// Write out all elements in the proper order.

for (Object element : es)

s.writeObject(element);

}

/**

* Reconstitutes this list from a stream (that is, deserializes it).

* @param s the stream

* @throws ClassNotFoundException if the class of a serialized object

* could not be found

* @throws java.io.IOException if an I/O error occurs

*/

private void readObject(java.io.ObjectInputStream s)

throws java.io.IOException, ClassNotFoundException {

s.defaultReadObject();

// bind to new lock

resetLock();

// Read in array length and allocate array

int len = s.readInt();

SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len);

Object[] es = new Object[len];

// Read in all elements in the proper order.

for (int i = 0; i < len; i++)

es[i] = s.readObject();

setArray(es);

}

// 省略其他

}从源码可以看出，CopyOnWriteArrayList是一个线程安全的 ArrayList，它的功能和 ArrayList类似，但是它采用了一种读写分离的并发策略。它的底层同样是一个 Object类型的数组，用来存放元素。当对 CopyOnWriteArrayList 进行写操作（增/删/改）时，它会使用 synchronized关键字保证同时只有一个线程对数组进行修改，并且会创建数组的新副本来完成修改操作，然后将原数组引用指向新数组。这样就避免了写操作对读操作造成影响，提高了读操作的性能。

当然，面试官可能会问CopyOnWriteArrayList 中 volatile关键字的作用。

CopyOnWriteArrayList 中 volatile的作用是保证数组引用的可见性和有序性。也就是说，当写操作修改了数组引用时，其他线程可以及时看到最新的数组引用。同时，volatile也防止了指令重排，保证了写操作的原子性。

但是，volatile不能保证数组元素的可见性和有序性。也就是说，如果只修改了数组元素而没有修改数组引用，其他线程可能看不到最新的数组元素。这就可能导致数据一致性的问题。

面试官还有可能会问 CopyOnWriteArrayList 中 transient关键字的作用

CopyOnWriteArrayList 中 transient关键字的作用是在序列化中才起作用，transient变量不会被自动序列化。也就是说，当 CopyOnWriteArrayList对象被序列化时，它的数组元素不会被写入到输出流中。这样做的好处是节省了空间和时间，因为数组元素可能很多，而且可能已经被修改了。

如果要恢复CopyOnWriteArrayList对象的状态，可以使用 writeObject和 readObject方法来自定义序列化和反序列化的逻辑。

2.1.2 CopyOnWriteArrayList 优缺点和适用场景CopyOnWriteArrayList 主要优点：

线程安全，它可以在多线程的环境下保证数据的一致性。它对所有的写操作都使用ReentrantLock来加锁，避免了并发修改异常。读性能高，它对所有的读操作都不加锁，大大提高了“读”操作的并发度。它使用了快照机制来实现迭代器，避免了迭代过程中的同步开销。CopyOnWriteArrayList 主要缺点，比如：

内存占用大，因为写时复制的原理，所以在添加新元素的时候会复制一份，此刻内存中就会有两份对象，比如这个时候有200M，你在复制一份 400M，如果频繁出现这种情况，造成产生频繁的 JVM 的 Yong GC 和 Full GC，严重的会进行 STW。存在数据一致性问题，因为写操作是在新数组上进行的，而读操作是在旧数组上进行的，所以可能会出现“脏读”的问题。也就是说，读操作可能访问到过期的数据。不支持随机访问和迭代器修改，因为 CopyOnWriteArrayList使用了快照机制来实现迭代器。也就是说，迭代器遍历的是数组的一个副本，并不反映数组的实时状态。如果试图用迭代器修改元素，会抛出 UnsupportedOperationException异常。频繁并发写操作性能差。由于采用 synchronized 对写操作进行加锁，因此频繁多线程写容易因线程竞争锁而影响性能。基于CopyOnWriteArrayList 原理和优缺点，我们可以看出它更适合于读多写少的并发场景。

2.2 CopyOnWriteMap 参考代码对于很多面试官，如果你能将上述的原理、优缺点和适用场景对答如流可能就满意了。

然而，真正聪明的面试官更愿意考察你的知识迁移能力，通过让你手写 CopyOnWriteMap 来验证你是真正理解还是突击背诵。

JDK 没有直接给出 CopyOnWriteMap 的代码实现，本文给出 kafka 和 jenkins 中的对应源码，供大家参考。

如果面试时，不仅能写出对应的代码，还能讲出 kafka 和 jenkis 中的实现的异同，也能够增色不少，超出预期。

2.2.1 kafka 实现仓库地址：https://github.com/apache/kafka

org.apache.kafka.common.utils.CopyOnWriteMap 源码：

代码语言：javascript代码运行次数：0运行复制package org.apache.kafka.common.utils;

import java.util.Collection;

import java.util.Collections;

import java.util.HashMap;

import java.util.Map;

import java.util.Set;

import java.util.concurrent.ConcurrentMap;

/**

* A simple read-optimized map implementation that synchronizes only writes and does a full copy on each modification

*/

public class CopyOnWriteMap implements ConcurrentMap {

private volatile Map map;

public CopyOnWriteMap() {

this.map = Collections.emptyMap();

}

public CopyOnWriteMap(Map map) {

this.map = Collections.unmodifiableMap(map);

}

@Override

public boolean containsKey(Object k) {

return map.containsKey(k);

}

@Override

public boolean containsValue(Object v) {

return map.containsValue(v);

}

@Override

public Set> entrySet() {

return map.entrySet();

}

@Override

public V get(Object k) {

return map.get(k);

}

@Override

public boolean isEmpty() {

return map.isEmpty();

}

@Override

public Set keySet() {

return map.keySet();

}

@Override

public int size() {

return map.size();

}

@Override

public Collection values() {

return map.values();

}

@Override

public synchronized void clear() {

this.map = Collections.emptyMap();

}

@Override

public synchronized V put(K k, V v) {

Map copy = new HashMap<>(this.map);

V prev = copy.put(k, v);

this.map = Collections.unmodifiableMap(copy);

return prev;

}

@Override

public synchronized void putAll(Map entries) {

Map copy = new HashMap<>(this.map);

copy.putAll(entries);

this.map = Collections.unmodifiableMap(copy);

}

@Override

public synchronized V remove(Object key) {

Map copy = new HashMap<>(this.map);

V prev = copy.remove(key);

this.map = Collections.unmodifiableMap(copy);

return prev;

}

@Override

public synchronized V putIfAbsent(K k, V v) {

if (!containsKey(k))

return put(k, v);

else

return get(k);

}

@Override

public synchronized boolean remove(Object k, Object v) {

if (containsKey(k) && get(k).equals(v)) {

remove(k);

return true;

} else {

return false;

}

}

@Override

public synchronized boolean replace(K k, V original, V replacement) {

if (containsKey(k) && get(k).equals(original)) {

put(k, replacement);

return true;

} else {

return false;

}

}

@Override

public synchronized V replace(K k, V v) {

if (containsKey(k)) {

return put(k, v);

} else {

return null;

}

}

}该源码的实现非常简单：

（1）写方法上都加上了 synchronized关键字确保线程安全；

（2）修改前都通过 Map copy = new HashMap<>(this.map);拷贝出一个新的 map， 符合“写时复制” 的思想；

对于 map 采用 Collections.unmodifiableMap构造不可修改的 Map 是一大亮点，是代码健壮性的体现。

注意它实现了 ConcurrentMap 即可哭。

还需要注意的是，属性中的 map 加了 volatile关键字，这也是面试官考察的重点。

2.2.2 jenkis 实现仓库地址：https://github.com/jenkinsci/jenkins

hudson.util#CopyOnWriteMap 源码：

代码语言：javascript代码运行次数：0运行复制package hudson.util;

import com.thoughtworks.xstream.converters.MarshallingContext;

import com.thoughtworks.xstream.converters.UnmarshallingContext;

import com.thoughtworks.xstream.converters.collections.MapConverter;

import com.thoughtworks.xstream.converters.collections.TreeMapConverter;

import com.thoughtworks.xstream.io.HierarchicalStreamReader;

import com.thoughtworks.xstream.io.HierarchicalStreamWriter;

import com.thoughtworks.xstream.mapper.Mapper;

import java.util.Collection;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

/**

* {@link Map} that has copy-on-write semantics.

*

*

* This class is suitable where highly concurrent access is needed, yet

* the write operation is relatively uncommon.

*

* @author Kohsuke Kawaguchi

*/

public abstract class CopyOnWriteMap implements Map {

protected volatile Map core;

/**

* Read-only view of {@link #core}.

*/

private volatile Map view;

protected CopyOnWriteMap(Map core) {

update(core);

}

protected CopyOnWriteMap() {

update(Collections.emptyMap());

}

protected void update(Map m) {

core = m;

view = Collections.unmodifiableMap(core);

}

/**

* Atomically replaces the entire map by the copy of the specified map.

*/

public void replaceBy(Map data) {

Map d = copy();

d.clear();

d.putAll(data);

update(d);

}

@Override

public int size() {

return core.size();

}

@Override

public boolean isEmpty() {

return core.isEmpty();

}

@Override

public boolean containsKey(Object key) {

return core.containsKey(key);

}

@Override

public boolean containsValue(Object value) {

return core.containsValue(value);

}

@Override

public V get(Object key) {

return core.get(key);

}

@Override

public synchronized V put(K key, V value) {

Map m = copy();

V r = m.put(key, value);

update(m);

return r;

}

@Override

public synchronized V remove(Object key) {

Map m = copy();

V r = m.remove(key);

update(m);

return r;

}

@Override

public synchronized void putAll(Map t) {

Map m = copy();

m.putAll(t);

update(m);

}

protected abstract Map copy();

@Override

public synchronized void clear() {

update(Collections.emptyMap());

}

/**

* This method will return a read-only {@link Set}.

*/

@Override

public Set keySet() {

return view.keySet();

}

/**

* This method will return a read-only {@link Collection}.

*/

@Override

public Collection values() {

return view.values();

}

/**

* This method will return a read-only {@link Set}.

*/

@Override

public Set> entrySet() {

return view.entrySet();

}

@Override public int hashCode() {

return copy().hashCode();

}

@SuppressWarnings("EqualsWhichDoesntCheckParameterClass")

@Override public boolean equals(Object obj) {

return copy().equals(obj);

}

@Override public String toString() {

return copy().toString();

}

/**

* {@link CopyOnWriteMap} backed by {@link HashMap}.

*/

public static final class Hash extends CopyOnWriteMap {

public Hash(Map core) {

super(new LinkedHashMap<>(core));

}

public Hash() {

}

@Override

protected Map copy() {

return new LinkedHashMap<>(core);

}

public static class ConverterImpl extends MapConverter {

public ConverterImpl(Mapper mapper) {

super(mapper);

}

@Override

public boolean canConvert(Class type) {

return type == Hash.class;

}

@Override

public Object unmarshal(HierarchicalStreamReader reader, UnmarshallingContext context) {

return new Hash((Map) super.unmarshal(reader, context));

}

@Override

public void marshal(Object source, HierarchicalStreamWriter writer, MarshallingContext context) {

super.marshal(((Hash) source).core, writer, context);

}

}

}

/**

* {@link CopyOnWriteMap} backed by {@link TreeMap}.

*/

public static final class Tree extends CopyOnWriteMap {

private final Comparator comparator;

public Tree(Map core, Comparator comparator) {

this(comparator);

putAll(core);

}

public Tree(Comparator comparator) {

super(new TreeMap<>(comparator));

this.comparator = comparator;

}

public Tree() {

this(null);

}

@Override

protected Map copy() {

TreeMap m = new TreeMap<>(comparator);

m.putAll(core);

return m;

}

@Override

public synchronized void clear() {

update(new TreeMap<>(comparator));

}

public static class ConverterImpl extends TreeMapConverter {

public ConverterImpl(Mapper mapper) {

super(mapper);

}

@Override

public boolean canConvert(Class type) {

return type == Tree.class;

}

@Override

public Object unmarshal(HierarchicalStreamReader reader, UnmarshallingContext context) {

TreeMap tm = (TreeMap) super.unmarshal(reader, context);

return new Tree(tm, tm.comparator());

}

@Override

public void marshal(Object source, HierarchicalStreamWriter writer, MarshallingContext context) {

super.marshal(((Tree) source).core, writer, context);

}

}

}

}该类和 kafka 中的实现有些类似，写操作都加同步关键字保证线程安全，也都采用写时复制的策略，但该类更高级。

（1）通过 view 来存储只读的 map ，在每个写操作后都会执行 update 方法，将复制出来的新数组赋值给 map 并且构造一个 Collections.unmodifiableMap 赋值给 view。

（2）该类还基于 TreeMap 和 HashMap 给出了两种实现。

（3）该类还提供了一些新的 API ，如 replaceBy方法。

三、总结很多看似简单的知识深挖起来有不少学问。很多人准备面试题时，容易眼高手低，很多知识点你以为掌握了，其实只是“阅读过”或者 “背诵过” 而已。我们不仅要知其然，还要知其所以然。学习某个技术时，一定要掌握其核心原理，了解其优势和劣势，能够根据情况选择最适合的工具。

所谓：“学以致用”，学习的最终目的还是为了使用。能够具备迁移能力的知识才代表我们真正掌握了该知识，只有能够灵活变通得运用知识，才能发挥出知识的价值。

希望本文能够对大家面试和日常的学习有启发。