集合相关问题

面试系列

集合类结构图

简单介绍ArrayList

• 实现原理
  ArrayList其底层数据结构是数组。在JDK1.8中ArrayList初始化时会被赋值为一个空数组，这时其长度为0，只有在添加元素时才会被分配10个长度的初始容量。当添加的元素达到底层数组上限时，ArrayList会自动扩容，然后使用数组拷贝的方式将原数组的数据逐一复制到新数组上。因此ArrayList的频繁扩容也会大大降低ArrayList的效率，在使用ArrayList的时候如果知道最终的存储容量，则应在初始化时就指定ArrayList的容量。

• ArrayList的优缺点

  • 优点：
    
    • ArrayList底层是以数组实现，是一种随机访问模式，因此获取元素非常快。
    • ArrayList在顺序添加元素时非常方便。
  • 缺点：
    
    • 在删除和插入元素时都涉及到了元素复制，如果要复制的元素很多，那么就比较消耗性能。

图解集合：ArrayList (JDK1.6)

简单介绍LinkedList

• 实现原理
  LinkedList其底层实现是双向链表结构。对于双向链表我认为有两点含义：

  1. 链表中任意一个存储单元都可以通过向前或者向后寻址的方式获取到其前一个存储单元和其后一个存储单元
  2. 链表的尾节点的后一个节点是链表的头结点，链表的头结点的前一个节点是链表的尾节点

• LinkedList的基本存储单元

  private static class Entry<E> {
  E element;
  Entry<E> next;
  Entry<E> previous;
  ...
  }

• LinkedList和ArrayList的对比
  
  1. 对于顺序插入，ArrayList的速度会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入时LinkedList必然慢于ArrayList
  2. 另外，由于LinkedList里面不仅维护了待插入的元素，还维护了前置节点和后置节点，如果一个LinkedList中的节点非常多，那么LinkedList将比ArrayList更耗费一些内存
  3. 对于数据遍历，ArrayList使用最普通的for循环遍历，LinkedList使用foreach循环比较快。ArrayList和LinkedList在使用各自遍历效率最高的方式时，ArrayList的遍历效率会比LinkedList的遍历效率高
  4. 有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：
     
     • LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址
     • ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址
     • 所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。
     • 通过分析可以看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你插入、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为LinkedList整体插入、删除的执行效率比较稳定；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作。

图解集合：LinkedList (JDK1.6)

简单介绍Vector

Vector虽然是线程安全的，但是只是一种相对的线程安全而不是绝对的线程安全，它只能够保证增、删、改、查的单个操作一定是原子的，不会被打断，但是如果组合起来用，并不能保证线程安全性。比如：线程1在遍历一个Vector中的元素、线程2在删除一个Vector中的元素一样，势必产生并发修改异常，也就是fail-fast。

简单介绍CopyOnWriteArrayList

• CopyOnWriteArrayList位于java.util.concurrent包下，可想而知，这个类是为并发而设计的
• 对CopyOnWriteArrayList执行任何可变操作（如：add、set、remove等）都伴随着复制这个动作，即写时复制的方法。由此可见CopyOnWriteArrayList的缺点，就是修改代价十分昂贵，每次修改都伴随着一次的数组复制。

• CopyOnWriteArrayList如何做到线程安全的
  CopyOnWriteArrayList利用“写时复制”机制，也就是当添加新元素时，先从原有的数组中拷贝一份出来，然后在新的数组中做写操作，写完之后，再将原来的数组引用指向新数组。而且CopyOnWriteArrayList的所有可变操作（如：add、set、remove等）都是在锁的保护下进行的。

  # add方法的源码
  public boolean add(E e) {
      //1、先加锁
      final ReentrantLock lock = this.lock;
      lock.lock();
      try {
          Object[] elements = getArray();
          int len = elements.length;
          //2、拷贝数组
          Object[] newElements = Arrays.copyOf(elements, len + 1);
          //3、将元素加入到新数组中
          newElements[len] = e;
          //4、将array引用指向到新数组
          setArray(newElements);
          return true;
      } finally {
          //5、解锁
          lock.unlock();
      }
  }

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

• CopyOnWriteArrayList的优点和缺点

  • 优点:解决的开发工作中的多线程的并发问题。
  • 缺点:
    
    1. 内存占有问题
    2. 数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。

• CopyOnWriteArrayList的使用场景

  1. 不能用于实时读的场景
  2. 合适读多写少的场景
  3. 由于写操作的时候，需要拷贝数组，会消耗内存，不适合数组内容过多的情况

• CopyOnWriteArrayList透露的思想
  如上面的分析CopyOnWriteArrayList表达的一些思想：

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

图解集合：CopyOnWriteArrayList (JDk1.6)
线程安全的CopyOnWriteArrayList介绍

简单介绍HashMap

• 存储结构：K-V键值对形式

• 实现原理
  HashMap的底层数据结构其实是数组和链表的结合体。也就是说当新建一个HashMap的时候，就会初始化一个数组，而数组中的每一项又是一个链表。代码如下：
  
  可以看出，Map.Entry就是数组中的元素，而每个Map.Entry又是一个K-V键值对，持有指向下一个元素的引用，这就构成了链表。

  • 存储实现（put）
    当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标）， 如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

  • 读取实现（get）
    从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

  • 重点

    关注点	结论
    HashMap是否允许为空	Key和Value都允许为空
    HashMap是否允许重复数据	Key重复会覆盖，Value允许重复
    HashMap是否有序	无序，是指遍历HashMap的时候，得到的元素的顺序基本不可能是put的顺序
    HashMap是否线程安全	不是线程安全的

  参考资料：
  图解集合：HashMap (JDk1.6)
  HashMap的实现原理
  http://www.importnew.com/7099.html
  http://www.importnew.com/16301.html

HashMap和HashTable的区别

1、Hashtable是线程安全的，HashTable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是非线程安全的
2、HashTable不允许空的value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制
注意：HashTable已经被淘汰，如果你不需要线程安全，那么使用HashMap，如果需要线程安全，那么使用ConcurrentHashMap。HashTable已经被淘汰了，不要在新的代码中再使用它。

简单介绍ConcurrentHashMap

• 实现原理（为什么是线程安全的）
  ConcurrentHashMap采用了“分段锁”的设计，只有在同一个分段内才存在锁竞争，不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计，分段锁大大的提高了高并发环境下的处理能力。
  在ConcurrentHashMap中的“分段锁”被称为Segment，它类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每一个元素又是一个链表，但同时Segment又继承了ReentrantLock对象。此外ConcurrentHashMap中的HashEntry相对于HashMap中的Entry有一定的差异性：HashEntry中的value以及next都被volatile修饰，这样在多线程读写过程中能够保持它们的可见性，代码如下：

  static final class HashEntry<K,V> {
      final int hash;
      final K key;
      volatile V value;
      volatile HashEntry<K,V> next;
  }

• ConcurrentHashMap的读是否要加锁
  从volatile解读ConcurrentHashMap（jdk1.6.0）无锁读

ConcurrentHashMap总结：ConcurrentHashMap的设计思路
ConcurrentHashMap能完全替代HashTable吗？：HashTable的迭代器是强一致性的，而ConcurrentHashMap是弱一致性的。
http://blog.csdn.net/xuefeng0707/article/details/40834595

简单介绍TreeMap

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。

http://www.cnblogs.com/skywang12345/p/3310928.html

简单介绍HashSet

HashSet 本身就采用 HashMap 来实现的