面试官：请手写一个 CopyOnWriteMap！

明明如月学长

发布于 2023-03-11 09:50:03

2760

发布于 2023-03-11 09:50:03

一、背景

Java 求职面试中， List 和 Map可以说是经典的八股文必考知识点。有些面试官喜欢问 ArrayList 和 HashMap 的相关知识，而有些面试官可能会独辟蹊径，重点考察其他 CopyOnWriteArrayList。或许，很多同学会说，这有什么难的呢？还不是信手拈来？但，如果面试官让你现场手写一个 CopyOnWriteMap你是否还能那么淡定从容？

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

二、探讨

2.1 `CopyOnWriteArrayList` 的源码和原理

2.1.1 源码

下面是该类的一些关键代码：

public class CopyOnWriteArrayList<E>
    implements List<E>, 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 源码：

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<K, V> implements ConcurrentMap<K, V> {

    private volatile Map<K, V> map;

    public CopyOnWriteMap() {
        this.map = Collections.emptyMap();
    }

    public CopyOnWriteMap(Map<K, V> 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<java.util.Map.Entry<K, V>> entrySet() {
        return map.entrySet();
    }

    @Override
    public V get(Object k) {
        return map.get(k);
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public Set<K> keySet() {
        return map.keySet();
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public Collection<V> values() {
        return map.values();
    }

    @Override
    public synchronized void clear() {
        this.map = Collections.emptyMap();
    }

    @Override
    public synchronized V put(K k, V v) {
        Map<K, V> copy = new HashMap<>(this.map);
        V prev = copy.put(k, v);
        this.map = Collections.unmodifiableMap(copy);
        return prev;
    }

    @Override
    public synchronized void putAll(Map<? extends K, ? extends V> entries) {
        Map<K, V> copy = new HashMap<>(this.map);
        copy.putAll(entries);
        this.map = Collections.unmodifiableMap(copy);
    }

    @Override
    public synchronized V remove(Object key) {
        Map<K, V> 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 源码：

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<K, V> implements Map<K, V> {
    protected volatile Map<K, V> core;
    /**
     * Read-only view of {@link #core}.
     */
    private volatile Map<K, V> view;

    protected CopyOnWriteMap(Map<K, V> core) {
        update(core);
    }

    protected CopyOnWriteMap() {
        update(Collections.emptyMap());
    }

    protected void update(Map<K, V> m) {
        core = m;
        view = Collections.unmodifiableMap(core);
    }

    /**
     * Atomically replaces the entire map by the copy of the specified map.
     */
    public void replaceBy(Map<? extends K, ? extends V> data) {
        Map<K, V> 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<K, V> m = copy();
        V r = m.put(key, value);
        update(m);

        return r;
    }

    @Override
    public synchronized V remove(Object key) {
        Map<K, V> m = copy();
        V r = m.remove(key);
        update(m);

        return r;
    }

    @Override
    public synchronized void putAll(Map<? extends K, ? extends V> t) {
        Map<K, V> m = copy();
        m.putAll(t);
        update(m);
    }

    protected abstract Map<K, V> copy();

    @Override
    public synchronized void clear() {
        update(Collections.emptyMap());
    }

    /**
     * This method will return a read-only {@link Set}.
     */
    @Override
    public Set<K> keySet() {
        return view.keySet();
    }

    /**
     * This method will return a read-only {@link Collection}.
     */
    @Override
    public Collection<V> values() {
        return view.values();
    }

    /**
     * This method will return a read-only {@link Set}.
     */
    @Override
    public Set<Entry<K, V>> 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<K, V> extends CopyOnWriteMap<K, V> {
        public Hash(Map<K, V> core) {
            super(new LinkedHashMap<>(core));
        }

        public Hash() {
        }

        @Override
        protected Map<K, V> 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<K, V> extends CopyOnWriteMap<K, V> {
        private final Comparator<K> comparator;

        public Tree(Map<K, V> core, Comparator<K> comparator) {
            this(comparator);
            putAll(core);
        }

        public Tree(Comparator<K> comparator) {
            super(new TreeMap<>(comparator));
            this.comparator = comparator;
        }

        public Tree() {
            this(null);
        }

        @Override
        protected Map<K, V> copy() {
            TreeMap<K, V> 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方法。

三、总结

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

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

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-03-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度