[关闭]
@adamhand 2018-12-23T05:07:28.000000Z 字数 24270 阅读 1137

Java集合

一. 集合综述

  Java中的集合主要分为两种：Collection和Map。Collection存储的都是单个元素，而Map存储的都是键值对元素。比较常用的是Map和Collection下面的Set、List，它们可以称为集合的三大类。（注意：List中的元素可以重复，Set中的元素不可以重复，如果有两个元素相同，那么只能放进去一个，Map中的元素键不可以重复，值可以重复，如果键相同，值会覆盖）具体UML图如下：

Collection

1. Set

2. List

3. Queue

Map

二. Collection

  Collection中常见的方法：

  1. boolean add (Object obj)
  2. boolean addAll (Collection coll)
  1. boolean remove (Object obj)
  2. boolean removeAll (Collection coll)
  3. void clear()
  1. boolean contains (Object obj)
  2. boolean containsAll (Collection coll)
  3. boolean isEmpty()
  1. int size()
  2. Iterator iterator()

  Iterator对象必须依赖具体的容器，因为每一个容器的数据结构都不同，所以该容器的对象时在容器内部实现的。对于使用容器者而言，具体的实现并不重要，只要通过容器获取到该实现的迭代器的对象即可，也就是iterator方法。

  1. boolean retainAll(Collection coll);//取交集
  2. Object[] toArray();//将集合转化成数组

1. List

  List中的元素是有序的（存入和取出的顺序一致），元素都有索引，而且可以重复。List中常用的方法有：

1.1 LinkedList

  内部是链表数据结构，是不同步的，增删元素比较快。常用方法如下：

1.2. ArrayList

  内部是数组的数据结构，是不同步的，查询速度比较快，代替了Vector。

1.3. Vector

  内部是数组数据结构，是同步的，增删、查询都很慢。

2. Set

  Set中的元素不可重复的，而且是无序的。

2.1 HashSet

  内部是数据结构是哈希表，是不同步的。
  HashSet是通过hashCode和equals方法来保证对象唯一性的。如果对象的hashCode不同，那么不用判断equals方法，就直接存储到哈希表中；如果对象的hashCode值相同，那么要再次判断对象的equals方法是否为true，若为true，视为相同元素，否则视为不同元素。
如果元素要存储到HashSet集合中，必须覆盖hashCode和equals方法；一般情况下，如果定义的类会产生很多对象，比如人、学生等，通常都需要覆盖hashCode和equals方法。
  当然，hashCode和equals方法是哈希表需要的方法，所以后面的HashMap也要覆盖这两个方法。

2.2 TreeSet

  TreeSet可以对Set集合中的元素进行排序，是不同步的。
  TreeSet是通过比较方法的返回结果来判断对象是否相等的，如果比较方法返回结果为0，就是相同元素，不会被存储。
  TreeSet对元素进行排序的方法有两种：

  • 实现Comparable接口，覆盖compareTo方法。让元素本身具备比较功能。例子如下：
  1. public class Person implements Comparable {
  3.     private int age;
  4.     private String name;
  6.     public Person(int age, String name) {
  7.         this.age = age;
  8.         this.name = name;
  9.     }
  11.     public int getAge() {
  12.         return age;
  13.     }
  15.     public String getName() {
  16.         return name;
  17.     }
  19.     public void setAge(int age) {
  20.         this.age = age;
  21.     }
  23.     public void setName(String name) {
  24.         this.name = name;
  25.     }
  27.     @Override
  28.     public int compareTo(Object o) {
  29.         Person p = (Person) o;
  31.         int tem = this.age - p.age;
  32.         return tem == 0 ? this.name.compareTo(p.name) : tem;
  33.     }
  34. }
  36. /**
  37.  * 是按照自然顺序来排序的，先按照年龄，然后按照名字的字典顺序
  38.  */
  39. public class TreeSetDemoOne {
  40.     public static void main(String[] args) {
  41.         Person p1 = new Person(12, "bob");
  42.         Person p2 = new Person(13,"juliy");
  43.         Person p3 = new Person(14,"jack");
  44.         Person p4 = new Person(12,"rose");
  46.         TreeSet t = new TreeSet();
  47.         t.add(p1);
  48.         t.add(p2);
  49.         t.add(p3);
  50.         t.add(p4);
  52.         Iterator iterator = t.iterator();
  53.         while(iterator.hasNext())
  54.         {
  55.             Person p = (Person) iterator.next();
  56.             System.out.println(p.getAge()+" "+p.getName());
  57.         }
  58.     }
  59. }

  输出结果为：

  1. 12 bob
  2. 12 rose
  3. 13 juliy
  4. 14 jack
  • 让元素具备比较能力的前提是元素本身存在自然顺序，但是如果元素不具备自然顺序或者我们不需要使用自然顺序进行排序，就要使用第二种方法。定义一个类实现Comparator接口，覆盖compare方法，将该类对象作为参数传递给TreeSet集合的构造函数。示例如下：
  1. public class CompareByNameLen implements Comparator {
  2.     @Override
  3.     public int compare(Object o1, Object o2) {
  4.         Person p1 = (Person) o1;
  5.         Person p2 = (Person) o2;
  7.         int temp = p1.getName().length() - p2.getName().length();
  8.         return temp == 0 ? p1.getAge() - p2.getAge() : temp;
  9.     }
  10. }
  12. public class Person {
  13.     private String name;
  14.     private int age;
  16.     public Person(String name, int age) {
  17.         this.name = name;
  18.         this.age = age;
  19.     }
  21.     public String getName() {
  22.         return name;
  23.     }
  25.     public int getAge() {
  26.         return age;
  27.     }
  29.     public void setName(String name) {
  30.         this.name = name;
  31.     }
  33.     public void setAge(int age) {
  34.         this.age = age;
  35.     }
  36. }
  38. /**
  39.  * 先按照姓名长度排序，如果相同再按照年龄大小排序。
  40.  */
  41. public class DemoTwo {
  42.     public static void main(String[] args) {
  43.         Person p1 = new Person("bob",12);
  44.         Person p2 = new Person("bobbo",14);
  45.         Person p3 = new Person("bobbobo",15);
  46.         Person p4 = new Person("bobboboobo",10);
  47.         Person p5 = new Person("bob",10);
  49.         TreeSet t = new TreeSet(new CompareByNameLen());
  50.         t.add(p1);
  51.         t.add(p2);
  52.         t.add(p3);
  53.         t.add(p4);
  54.         t.add(p5);
  56.         Iterator iterator = t.iterator();
  57.         while (iterator.hasNext())
  58.         {
  59.             Person p = (Person) iterator.next();
  60.             System.out.println(p.getAge()+ " "+p.getName());
  61.         }
  62.     }
  63. }

  输出结果为：

  1. 10 bob
  2. 12 bob
  3. 14 bobbo
  4. 15 bobbobo
  5. 10 bobboboobo

2.3 LinkedHashSet

  LinkedHashSet里面的元素是有顺序的，读出的顺序和写入的顺序一致。例子如下：

  1. public class LinkedHashSetDemo {
  2.     public static void main(String[] args) {
  3.         Set<String> linkedHashSet = new LinkedHashSet<>();
  5.         linkedHashSet.add("hahahah");
  6.         linkedHashSet.add("hehaee");
  7.         linkedHashSet.add("haeieieieieie");
  8.         linkedHashSet.add("aafdfd");
  9.         linkedHashSet.add("bfdhfjd");
  11.         Iterator<String> iterator = linkedHashSet.iterator();
  12.         while(iterator.hasNext())
  13.         {
  14.             System.out.println(iterator.next());
  15.         }
  16.     }
  17. }

  输出接结果为：

  1. hahahah
  2. hehaee
  3. haeieieieieie
  4. aafdfd
  5. bfdhfjd

三. Map

  Map集合与Collection集合的区别：

  • Map集合中存储的是键值对；Collection中存储的是单个元素。
  • Map中的存储使用的是put方法；Collection中存储使用的是add方法。
  • Map取出元素，是将Map转成Set，再使用迭代器取出；Collection直接使用迭代器。
  • 如果对象很多，必须使用容器存储；如果元素存在着映射关系，可以优先考虑使用Map或者数组存储；如果没有映射关系，优先考虑使用Collection存储。

1. 从Map中取出元素的几种方法

  1. /**
  2.  * map元素提取的几种方法。
  3.  */
  4. public class MapDemoOne {
  5.     public static void main(String[] args) {
  6.         Map<Integer, String> map = new HashMap<>();
  7.         method(map);
  8.     }
  10.     public static void method(Map<Integer, String> map)
  11.     {
  12.         map.put(8,"zhaoliu");
  13.         map.put(2,"zhaoliu");
  14.         map.put(2,"zhaoliu");
  15.         map.put(5,"wngwu");
  17.         /**
  18.          * 使用map中的value，这种方法的缺陷是只能得到value
  19.          */
  20.         Collection<String> values = map.values();
  21.         Iterator<String> it = values.iterator();
  22.         while(it.hasNext())
  23.         {
  24.             System.out.println(it.next());
  25.         }
  27.         System.out.println();
  28.         /**
  29.          * 使用map中的key
  30.          */
  31.         Set<Integer> keySet = map.keySet();
  32.         Iterator<Integer> it1 = keySet.iterator();
  33.         while(it1.hasNext())
  34.         {
  35.             int key = it1.next();
  36.             String value = map.get(key);
  37.             System.out.println(key+" "+value);
  38.         }
  40.         System.out.println();
  42.         /**
  43.          * 使用entrySet。这个方法将key和value的映射关系存储到Set中，这个映射关系就是Map.Entry
  44.          */
  45.         Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
  46.         Iterator<Map.Entry<Integer, String>> it2 = entrySet.iterator();
  47.         while(it2.hasNext())
  48.         {
  49.             Map.Entry<Integer, String> me = it2.next();
  50.             Integer key = me.getKey();
  51.             String value = me.getValue();
  52.             System.out.println(key+" "+value);
  53.         }
  55.         System.out.println();
  57.         /**
  58.          * 使用for each循环
  59.          */
  60.         for(Map.Entry<Integer, String> entry : map.entrySet())
  61.         {
  62.             System.out.println(entry.getKey()+" "+entry.getValue());
  63.         }
  65.         System.out.println();
  67.         for(Integer key : map.keySet())
  68.         {
  69.             System.out.println(key+" "+map.get(key));
  70.         }
  71.     }
  72. }

2 HashMap

2.1 按Value排序

  注意student类中要实现hashCode和equals方法。

  1. /**
  2.  * 按照Key排序
  3.  */
  4. public class HashMapDemo {
  5.     public static void main(String[] args) {
  6.         HashMap<Integer, String> hs = new HashMap<>();
  7.         hs.put(23,"张三");
  8.         hs.put(24,"李四");
  9.         hs.put(25,"王五");
  10.         hs.put(21,"bob");
  11.         hs.put(22,"alice");
  13.         sortHashMap(hs);
  15.     }
  17.     public static void sortHashMap(Map<Integer, String> hashMap)
  18.     {
  19.         //1.用HashMap构造一个LinkedList
  20.         Set<Map.Entry<Integer, String>> set = hashMap.entrySet();
  21.         LinkedList<Map.Entry<Integer, String>> linkedList = new LinkedList<>(set);
  23.         //2.用Collection的sort方法排序
  24.         Collections.sort(linkedList, new Comparator<Map.Entry<Integer, String>>() {
  25.             @Override
  26.             public int compare(Map.Entry<Integer, String> o1, Map.Entry<Integer, String> o2) {
  27.                 return o1.getValue().compareTo(o2.getValue());
  28.             }
  29.         });
  31.         //3.将排序后的LinkedList赋值LinkedHashMap
  32.         Map<Integer, String> map = new LinkedHashMap<>();
  33.         for(Map.Entry<Integer, String> entry : linkedList)
  34.         {
  35.             map.put(entry.getKey(), entry.getValue());
  36.         }
  38.         for(Map.Entry<Integer, String> entry : map.entrySet())
  39.         {
  40.             System.out.println(entry.getKey()+" "+entry.getValue());
  41.         }
  42.     }
  43. }

2.2 按key排序

  (1)和按value排序差不多，唯一的区别就是在比较的时候变为key的比较。
  (2)因为TreeMap是按照key排列的，所以可以利用TreeMap来对HashMap进行排序。

  1. /**
  2.  * 利用TreeMap对HashMap的key进行排序
  3.  */
  4. public class HashMapDemoTwo {
  5.     public static void main(String[] args) {
  6.         HashMap<Integer, String> hs = new HashMap<>();
  7.         hs.put(23,"张三");
  8.         hs.put(24,"李四");
  9.         hs.put(25,"王五");
  10.         hs.put(21,"bob");
  11.         hs.put(22,"alice");
  13.         sortHashMapByKey(hs);
  14.     }
  16.     public static void sortHashMapByKey(Map<Integer, String> hashMap)
  17.     {
  18.         TreeMap<Integer, String> treeMap = new TreeMap<>(new Comparator<Integer>() {
  19.             @Override
  20.             public int compare(Integer o1, Integer o2) {
  21.                 return Integer.compare(o1, o2);
  22.             }
  23.         });
  25.         treeMap.putAll(hashMap);
  26.         for(Map.Entry<Integer, String> entry : treeMap.entrySet())
  27.         {
  28.             System.out.println(entry.getKey()+" "+entry.getValue());
  29.         }
  30.     }
  31. }

2.3 Value去重

  使用containsValue方法实现去重：

  1. /**
  2.  * value去重
  3.  */
  4. public class HashMapDemoThree {
  5.     public static void main(String[] args) {
  6.         HashMap<Integer, String> hs = new HashMap<>();
  7.         hs.put(23,"张三");
  8.         hs.put(24,"张三");
  9.         hs.put(25,"王五");
  10.         hs.put(21,"bob");
  11.         hs.put(22,"alice");
  13.         System.out.println(hs.toString());
  15.         hs = method(hs);
  17.         System.out.println(hs.toString());
  18.     }
  20.     public static HashMap<Integer, String> method(HashMap<Integer, String> hs){
  21.         HashMap<Integer, String> hashMap = new HashMap<>();
  23.         for(Integer key : hs.keySet()){
  24.             if(!hashMap.containsValue(hs.get(key)))
  25.                 hashMap.put(key, hs.get(key));
  26.         }
  28.         return hashMap;
  29.     }
  30. }

2.4 HashMap线程同步

  1. Map<Integer , String> hs = new HashMap<Integer , String>();
  2. hs = Collections.synchronizedMap(hs);
  1. ConcurrentHashMap<Integer , String> hs = new ConcurrentHashMap<Integer , String>();

3. LinkedHashMap

4. TreeMap

四. 源码分析

List

ArrayList

1. 概览

  实现了 RandomAccess 接口，因此支持随机访问。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。这是理所当然的，因为 ArrayList 是基于数组实现的。

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable

  关键属性。

  1. //数组的默认大小为10
  2. private static final int DEFAULT_CAPACITY = 10;
  4. //一个空数组。当用户指定该 ArrayList 容量为 0 时，返回该空数组。见构造函数
  5. private static final Object[] EMPTY_ELEMENTDATA = {};
  7. /**
  8.  * 一个空数组实例
  9.  * 当用户没有指定 ArrayList 的容量时(即调用无参构造函数)，返回的是该数组。刚创建一个 ArrayList 时，其内数据量为 0。
  10.  * 当用户第一次添加元素时，该数组将会扩容，变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组===>通过  ensureCapacityInternal() 实现
  11.  * 它与 EMPTY_ELEMENTDATA 的区别就是：该数组是默认返回的，而后者是在用户指定容量为 0 时返回。见构造函数。
  12.  */
  13. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  15. /**
  16.  * ArrayList基于数组实现，用该数组保存数据, ArrayList 的容量就是该数组的长度
  17.  * 该值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入 ArrayList 中时，数组将扩容至 DEFAULT_CAPACITY(10)
  18.  * 那么，该数组为什么被transient修饰？transient表示一个域不属于该对象序列化的一部分，但是ArrayList又是能够被序列化的，这样的话，在反序列化的时候，ArrayList中的值不是就会丢失了吗？玄机在于ArrayList中的两个方法：writeObject()和readObject()(这里就不贴出来了，详见第5点，序列化)。ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。
  19. 为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
  20.  */
  21. transient Object[] elementData; // non-private to simplify nested class access

2. 扩容

  添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
  扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

  1. public boolean add(E e) {
  2.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  3.     elementData[size++] = e;
  4.     return true;
  5. }
  7. private void ensureCapacityInternal(int minCapacity) {
  8.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  9.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  10.     }
  11.     ensureExplicitCapacity(minCapacity);
  12. }
  14. private void ensureExplicitCapacity(int minCapacity) {
  15.     modCount++;
  16.     // overflow-conscious code
  17.     if (minCapacity - elementData.length > 0)
  18.         grow(minCapacity);
  19. }
  21. private void grow(int minCapacity) {
  22.     // overflow-conscious code
  23.     int oldCapacity = elementData.length;
  24.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  25.     if (newCapacity - minCapacity < 0)
  26.         newCapacity = minCapacity;
  27.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  28.         newCapacity = hugeCapacity(minCapacity);
  29.     // minCapacity is usually close to size, so this is a win:
  30.     elementData = Arrays.copyOf(elementData, newCapacity);
  31. }

3. 删除元素

需要调用 System.arraycopy() 将 index+1 后面的元素都往前移动，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

  1. public E remove(int index) {
  2.     rangeCheck(index);
  3.     modCount++;
  4.     E oldValue = elementData(index);
  5.     int numMoved = size - index - 1;
  6.     if (numMoved > 0)
  7.         System.arraycopy(elementData, index+1, elementData, index, numMoved);
  8.     elementData[--size] = null; // clear to let GC do its work
  9.     return oldValue;
  10. }

4. Fail-Fast

  fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。
  modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
  在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

  1. private void writeObject(java.io.ObjectOutputStream s)
  2.     throws java.io.IOException{
  3.     // Write out element count, and any hidden stuff
  4.     int expectedModCount = modCount;
  5.     s.defaultWriteObject();
  7.     // Write out size as capacity for behavioural compatibility with clone()
  8.     s.writeInt(size);
  10.     // Write out all elements in the proper order.
  11.     for (int i=0; i<size; i++) {
  12.         s.writeObject(elementData[i]);
  13.     }
  15.     if (modCount != expectedModCount) {
  16.         throw new ConcurrentModificationException();
  17.     }
  18. }

5. 序列化

  ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。
  保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。
  为了防止一个包含大量空对象的数组被序列化，为了优化存储，所以，ArrayList使用transient来声明elementData。 但是，作为一个集合，在序列化过程中还必须保证其中的元素可以被持久化下来，所以，通过重写writeObject 和 readObject方法的方式把其中的元素保留下来。

  1. transient Object[] elementData; // non-private to simplify nested class access

  ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

  1. private void readObject(java.io.ObjectInputStream s)
  2.     throws java.io.IOException, ClassNotFoundException {
  3.     elementData = EMPTY_ELEMENTDATA;
  5.     // Read in size, and any hidden stuff
  6.     s.defaultReadObject();
  8.     // Read in capacity
  9.     s.readInt(); // ignored
  11.     if (size > 0) {
  12.         // be like clone(), allocate array based upon size not capacity
  13.         ensureCapacityInternal(size);
  15.         Object[] a = elementData;
  16.         // Read in all elements in the proper order.
  17.         for (int i=0; i<size; i++) {
  18.             a[i] = s.readObject();
  19.         }
  20.     }
  21. }
  22. private void writeObject(java.io.ObjectOutputStream s)
  23.     throws java.io.IOException{
  24.     // Write out element count, and any hidden stuff
  25.     int expectedModCount = modCount;
  26.     s.defaultWriteObject();
  28.     // Write out size as capacity for behavioural compatibility with clone()
  29.     s.writeInt(size);
  31.     // Write out all elements in the proper order.
  32.     for (int i=0; i<size; i++) {
  33.         s.writeObject(elementData[i]);
  34.     }
  36.     if (modCount != expectedModCount) {
  37.         throw new ConcurrentModificationException();
  38.     }
  39. }

  序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

  1. ArrayList list = new ArrayList();
  2. ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
  3. oos.writeObject(list);

Vector

1. 同步

  它的实现与 ArrayList 类似，但是使用了 synchronized 进行同步。

  1. public synchronized boolean add(E e) {
  2.     modCount++;
  3.     ensureCapacityHelper(elementCount + 1);
  4.     elementData[elementCount++] = e;
  5.     return true;
  6. }
  8. public synchronized E get(int index) {
  9.     if (index >= elementCount)
  10.         throw new ArrayIndexOutOfBoundsException(index);
  12.     return elementData(index);
  13. }

2. 与 ArrayList 的比较

3. 替代方案

  可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。

  1. List<String> list = new ArrayList<>();
  2. List<String> synList = Collections.synchronizedList(list);

  也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

  1. List<String> list = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList

1. 概述

  Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。

2. 什么是CopyOnWrite容器

  CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁(注意，写还是要加锁的)，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。具体过程如下：

3. 写操作

  CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。
这样做是为了避免在多线程并发add的时候，复制出多个副本出来,把数据搞乱了，导致最终的数组数据不是我们期望的。

  1. public boolean add(T e) {
  2.     final ReentrantLock lock = this.lock;
  3.     lock.lock();
  4.     try {
  5.         Object[] elements = getArray();
  6.         int len = elements.length;
  7.         // 复制出新数组
  8.         Object[] newElements = Arrays.copyOf(elements, len + 1);
  9.         // 把新元素添加到新数组里
  10.         newElements[len] = e;
  11.         // 把原数组引用指向新数组
  12.         setArray(newElements);
  13.         return true;
  14.     } finally {
  15.         lock.unlock();
  16.     }
  17. }
  19. final void setArray(Object[] a) {
  20.     array = a;
  21. }

4. 读操作

  由于所有的写操作都是在新数组进行的，这个时候如果有线程并发的写，则通过锁来控制，如果有线程并发的读，则分几种情况：
  (1)如果写操作未完成，那么直接读取原数组的数据；
  (2)如果写操作完成，但是引用还未指向新数组，那么也是读取原数组数据；
  (3)如果写操作完成，并且引用已经指向了新的数组，那么直接从新数组中读取数据。
  可见，CopyOnWriteArrayList的读操作是可以不用加锁的。

  1. public E get(int index) {
  2.     return get(getArray(), index);
  3. }

5. 使用场景

&emsp； 通过上面的分析，CopyOnWriteArrayList 有几个缺点：
  (1)由于写操作的时候，需要拷贝数组，会消耗内存，如果原数组的内容比较多的情况下，可能导致young gc或者full gc
  (2)不能用于实时读的场景，像拷贝数组、新增元素都需要时间，所以调用一个set操作后，读取到数据可能还是旧的,虽然CopyOnWriteArrayList 能做到最终一致性,但是还是没法满足实时性要求；

  CopyOnWriteArrayList 合适读多写少的场景，不过这类慎用,因为谁也没法保证CopyOnWriteArrayList 到底要放置多少数据，万一数据稍微有点多，每次add/set都要重新复制数组，这个代价实在太高昂了。在高性能的互联网应用中，这种操作分分钟引起故障。

6. 自己实现CopyOnWriteMap

  JDKCopyOnWriteMap，但是可以模仿CopyOnWriteArrayList写一个：

  1. import java.util.Collection;
  2. import java.util.Map;
  3. import java.util.Set;
  5. public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable {
  6.     private volatile Map<K, V> internalMap;
  8.     public CopyOnWriteMap() {
  9.         internalMap = new HashMap<K, V>();
  10.     }
  12.     public V put(K key, V value) {
  13.         synchronized (this) {
  14.             Map<K, V> newMap = new HashMap<K, V>(internalMap);
  15.             V val = newMap.put(key, value);
  16.             internalMap = newMap;
  17.             return val;
  18.         }
  19.     }
  21.     public V get(Object key) {
  22.         return internalMap.get(key);
  23.     }
  25.     public void putAll(Map<? extends K, ? extends V> newData) {
  26.         synchronized (this) {
  27.             Map<K, V> newMap = new HashMap<K, V>(internalMap);
  28.             newMap.putAll(newData);
  29.             internalMap = newMap;
  30.         }
  31.     }
  32. }

7. 透露的思想

  • 读写分离，读和写分开
  • 最终一致性
  • 使用另外开辟空间的思路，来解决并发冲突

LinkedList

Map

HashMap

  详见“HashMap--从jdk1.7到jdk1.8”

ConcurrentHashMap

  详见“ConcurrentHashMap--从jdk1.7到jdk1.8”

LinkedHashMap

  LinkedHashMap继承自HashMap，所以很多特性和HashMap中一样，不同的是LinkedHashMap使用双链表来维护节点之间的先后关系。下面主要叙述LinkedHashMap和HashMap的不同。

1. LinkedHashMap的成员变量

  1. private static final long serialVersionUID = 3801124242820219131L;
  3. // 用于指向双向链表的头部
  4. transient LinkedHashMap.Entry<K,V> head;
  5. //用于指向双向链表的尾部
  6. transient LinkedHashMap.Entry<K,V> tail;
  7. /**
  8.  * 用来指定LinkedHashMap的迭代顺序，
  9.  * true则表示按照基于访问的顺序来排列，意思就是**最近使用的entry，放在链表的最末尾**
  10.  * false则表示按照插入顺序来
  11.  */ 
  12. final boolean accessOrder;

  可以看到，LinkedHashMap支持的遍历顺序有两个：插入顺序和访问顺序。具体的区别可以看下面的例子：

  1. public static void testLinkedList(){
  2.     //非accessOrder模式，迭代顺序为插入顺序
  3.     HashMap<String, Integer> map = new LinkedHashMap<>();
  5.     map.put("s1", 1);
  6.     map.put("s2", 2);
  7.     map.put("s3", 3);
  8.     map.put("s4", 4);
  9.     map.put("s5", 5);
  10.     map.put(null, 9);
  11.     map.put("s6", 6);
  12.     map.put("s7", 7);
  13.     map.put("s8", 8);
  14.     map.put(null, 11);
  15.     for(Map.Entry<String,Integer> entry:map.entrySet()){
  16.         System.out.println(entry.getKey()+":"+entry.getValue());
  17.     }
  18.     System.out.println(map);
  20.     System.out.println();
  22.     //accessOrder模式，迭代顺序为最近访问顺序
  23.     HashMap<String, Integer> map1 = new LinkedHashMap<>(16, 0.75f, true);
  25.     map1.put("s1", 1);
  26.     map1.put("s2", 2);
  27.     map1.put("s3", 3);
  28.     map1.put("s4", 4);
  29.     map1.put("s5", 5);
  30.     map1.put(null, 9);
  31.     map1.put("s6", 6);
  32.     map1.put("s7", 7);
  33.     map1.put("s8", 8);
  34.     map1.put(null, 11);
  35.     for(Map.Entry<String,Integer> entry:map1.entrySet()){
  36.         System.out.println(entry.getKey()+":"+entry.getValue());
  37.     }
  38.     System.out.println(map1);
  39. }

  输入结果为：

  1. s1:1
  2. s2:2
  3. s3:3
  4. s4:4
  5. s5:5
  6. null:11
  7. s6:6
  8. s7:7
  9. s8:8
  10. {s1=1, s2=2, s3=3, s4=4, s5=5, null=11, s6=6, s7=7, s8=8}
  12. s1:1
  13. s2:2
  14. s3:3
  15. s4:4
  16. s5:5
  17. s6:6
  18. s7:7
  19. s8:8
  20. null:11
  21. {s1=1, s2=2, s3=3, s4=4, s5=5, s6=6, s7=7, s8=8, null=11}

  注意：如果将上面accessOrder中的的遍历方式改为：

  1. for(Iterator<String> iterator = map.keySet().iterator();iterator.hasNext();){
  2.     String name = iterator.next();
  3.     System.out.println(name+"->"+map.get(name));
  4. }

  结果会报错：

  1. s1->1
  2. Exception in thread "main" java.util.ConcurrentModificationException
  3.     at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(Unknown Source)
  4.     at java.util.LinkedHashMap$KeyIterator.next(Unknown Source)
  5.     at collections.map.LinkedHashMapTest.main(LinkedHashMapTest.java:33)

  这是因为在accessOrder模式下，get()方法会修改LinkedHashMap中的链表结构(具体见下main的get()方法解析)，以便将最近访问的元素放置到链表的末尾，因此，这个操作在集合迭代过程中修改了集合的元素，就会发生报错。所以，当LinkedHashMap工作在这个模式时，不能再迭代器中使用get()操作。Map的遍历建议使用entrySet的方式。

2. LinkedHashMap的构造方法

  跟HashMap类似的构造方法这里就不一一赘述了，里面唯一的区别就是添加了前面提到的accessOrder，默认赋值为false——按照插入顺序来排列，这里主要说明一下不同的构造方法。

  1. //多了一个 accessOrder的参数，用来指定按照LRU排列方式还是顺序插入的排序方式
  2. public LinkedHashMap(int initialCapacity,
  3.                          float loadFactor,
  4.                          boolean accessOrder) {
  5.    super(initialCapacity, loadFactor);
  6.    this.accessOrder = accessOrder;
  7.  }

3. 三个重点实现的函数

  在HashMap中提到了下面的定义：

  1. // Callbacks to allow LinkedHashMap post-actions
  2. void afterNodeAccess(Node<K,V> p) { }
  3. void afterNodeInsertion(boolean evict) { }
  4. void afterNodeRemoval(Node<K,V> p) { }

  LinkedHashMap继承于HashMap，因此也重新实现了这3个函数，顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情，即分别用于get()操作、put()操作、remove()操作之后的后序操作。
  下面通过分析get()、put()和remove()操作来分析这三个函数的作用。

get()方法
  get()方法的源码如下：

  1. public V get(Object key) {
  2.   Node<K,V> e;
  3.   //调用HashMap的getNode的方法，详见HashMap源码解析
  4.   if ((e = getNode(hash(key), key)) == null)
  5.     return null;
  6.   //在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess
  7.   if (accessOrder)
  8.     afterNodeAccess(e);
  9.   return e.value;
  10. }

  从上面的代码可以看到，LinkedHashMap的get方法，调用HashMap的getNode方法后，对accessOrder的值进行了判断，之前提到：

accessOrder为true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾
由此可见，afterNodeAccess(e)就是基于访问的顺序排列的关键，让我们来看一下它的代码：

  1. //此函数执行的效果就是将最近使用的Node，放在链表的最末尾
  2. void afterNodeAccess(Node<K,V> e) {
  3.   LinkedHashMap.Entry<K,V> last;
  4.   //仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
  5.   if (accessOrder && (last = tail) != e) {
  6.     //将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
  7.     LinkedHashMap.Entry<K,V> p =
  8.       (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  9.     //设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
  10.     p.after = null;
  11.     //p前一个节点不存在，情况一
  12.     if (b == null) // ①
  13.       head = a;
  14.     else
  15.       b.after = a;
  16.     if (a != null) 
  17.       a.before = b;
  18.     //p的后一个节点不存在，情况二
  19.     else // ②
  20.       last = b;
  21.     //情况三
  22.     if (last == null) // ③
  23.       head = p;
  24.     //正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
  25.     else {
  26.       p.before = last;
  27.       last.after = p;
  28.     }
  29.     //将p设置为将p设置为尾节点
  30.     tail = p;
  31.     // 修改计数器+1
  32.     ++modCount;
  33.   }
  34. }

  标注的情况如下图所示（特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了）：

  下面来简单说明一下：

  • 正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点。
  • 情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
  • 情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
  • 情况三：p为链表里的第一个节点，head=p

put()方法
  接下来看一下LinkedHashMap是怎么插入Entry的：LinkedHashMap的put方法调用的还是HashMap里的put，不同的是重写了里面的部分方法：

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.     ...
  4.     tab[i] = newNode(hash, key, value, null);
  5.     ...
  6.     e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  7.     ...
  8.     if ((e = p.next) == null) {
  9.       p.next = newNode(hash, key, value, null);
  10.     ...
  11.         afterNodeAccess(e);
  12.     ...
  13.         afterNodeInsertion(evict);
  14.       return null;
  15. }

  省略部分的代码可以参考HashMap的put方法。LinkedHashMap将其中newNode方法以及之前设置下的钩子方法afterNodeAccess和afterNodeInsertion进行了重写，从而实现了加入链表的目的：

  1. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  2.   //秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast
  3.   LinkedHashMap.Entry<K,V> p =
  4.     new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  5.   linkNodeLast(p);
  6.   return p;
  7. }
  9. //顾名思义就是把新加的节点放在链表的最后面
  10. private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  11.   //将tail给临时变量last
  12.   LinkedHashMap.Entry<K,V> last = tail;
  13.   //把new的Entry给tail
  14.   tail = p;
  15.   //若没有last，说明p是第一个节点，head=p
  16.   if (last == null)
  17.     head = p;
  18.   //否则就做准备工作，你懂的 (￣▽￣)"
  19.   else {
  20.     p.before = last;
  21.     last.after = p;
  22.   }
  23. }
  25. //这里笔者也把TreeNode的重写也加了进来，因为putTreeVal里有调用了这个
  26. TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
  27.   TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
  28.   linkNodeLast(p);
  29.   return p;
  30. }
  32. //插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
  33. void afterNodeInsertion(boolean evict) {
  34.   LinkedHashMap.Entry<K,V> first;
  35.   if (evict && (first = head) != null && removeEldestEntry(first)) {
  36.     K key = first.key;
  37.     removeNode(hash(key), key, null, false, true);
  38.   }
  39. }
  41. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  42.   return false;
  43. }

remove()方法
  remove里面设计者也设置了一个钩子方法：

  1. final Node<K,V> removeNode(int hash, Object key, Object value,
  2.                                boolean matchValue, boolean movable) {
  3.   ...
  4.       //node即是要删除的节点
  5.       afterNodeRemoval(node);
  6.   ...
  7. }

  这个方法的源码如下：

  1. void afterNodeRemoval(Node<K,V> e) {
  2.   //与afterNodeAccess一样，记录e的前后节点b，a
  3.   LinkedHashMap.Entry<K,V> p =
  4.     (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  5.   //p已删除，前后指针都设置为null，便于GC回收
  6.   p.before = p.after = null;
  7.   //与afterNodeAccess一样类似，一顿判断，然后b，a互为前后节点
  8.   if (b == null)
  9.     head = a;
  10.   else
  11.     b.after = a;
  12.   if (a == null)
  13.     tail = b;
  14.   else
  15.     a.before = b;
  16. }

4. 迭代器

  迭代器LinkedHashIterator的源码及注释如下：

  1. abstract class LinkedHashIterator {
  2.   //记录下一个Entry
  3.   LinkedHashMap.Entry<K,V> next;
  4.   //记录当前的Entry
  5.   LinkedHashMap.Entry<K,V> current;
  6.   //记录是否发生了迭代过程中的修改
  7.   int expectedModCount;
  9.   LinkedHashIterator() {
  10.     //初始化的时候把head给next
  11.     next = head;
  12.     expectedModCount = modCount;
  13.     current = null;
  14.   }
  16.   public final boolean hasNext() {
  17.     return next != null;
  18.   }
  20.   //这里采用的是链表方式的遍历方式，有兴趣的园友可以去上一章看看HashMap的遍历方式
  21.   final LinkedHashMap.Entry<K,V> nextNode() {
  22.     LinkedHashMap.Entry<K,V> e = next;
  23.     if (modCount != expectedModCount)
  24.       throw new ConcurrentModificationException();
  25.     if (e == null)
  26.       throw new NoSuchElementException();
  27.     //记录当前的Entry
  28.     current = e;
  29.     //直接拿after给next
  30.     next = e.after;
  31.     return e;
  32.   }
  34.   public final void remove() {
  35.     Node<K,V> p = current;
  36.     if (p == null)
  37.       throw new IllegalStateException();
  38.     if (modCount != expectedModCount)
  39.       throw new ConcurrentModificationException();
  40.     current = null;
  41.     K key = p.key;
  42.     removeNode(hash(key), key, null, false, false);
  43.     expectedModCount = modCount;
  44.   }
  45. }

5. 补充：LRU方法

  LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。是内存不够的场景下，淘汰旧内容的策略。
  以下是使用 LinkedHashMap 实现的一个 LRU 缓存：

  • 设定最大缓存空间 MAX_ENTRIES 为 3；
  • 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
  • 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除。
  1. public class LCUCache {
  2.     static class LRUCache<K, V> extends LinkedHashMap<K, V> {
  3.         private static final int MAX_ENTRIES = 3;
  5.         protected boolean removeEldestEntry(Map.Entry eldest) {
  6.             return size() > MAX_ENTRIES;
  7.         }
  9.         LRUCache() {
  10.             super(MAX_ENTRIES, 0.75f, true);
  11.         }
  12.     }
  14.     public static void main(String[] args) {
  15.         LRUCache<Integer, String> cache = new LRUCache<>();
  16.         cache.put(1, "a");
  17.         cache.put(2, "b");
  18.         cache.put(3, "c");
  19.         cache.get(1);
  20.         cache.put(4, "d");
  21.         System.out.println(cache.keySet());
  22.     }
  23. }

  输入结果为：

  1. [3, 1, 4]

6. 参考

  1. https://www.cnblogs.com/joemsu/p/7787043.html
  2. https://www.jianshu.com/p/e406d405e18d
  3. http://www.importnew.com/16695.html
  4. http://www.importnew.com/23178.html
  5. http://www.importnew.com/17561.html
  6. http://www.importnew.com/18706.html
  7. http://www.importnew.com/18726.html
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注