java集合类

java集合提供两大接口衍生：Collection和Map接口

1.Collection接口包含一批对象的集合；

2.Map接口在Collection基础上，为每个对象指定key，并使用Entry保存每个key-value对，实现通过key快速定位到对象；

3.List类集合

     List接口继承自Collection，用于定义以列表形式存储的集合，List接口为集合中的每个对象分配了一个索引(index)，标记该对象在List中的位置，并可以通过index定位到指定位置的对象。

4.List接口常用的实现类

       4.1ArrayList：基于数组来实现集合的功能，其内部维护了一个可变长的对象数组，集合内所有对象存储于这个数组中，并实现该数组长度的动态伸缩。

       4.2LinkedList：基于链表来实现集合的功能，其实现了静态类Node，集合中的每个对象都由一个Node保存，每个Node都拥有到自己的前一个和后一个Node的引用

注意：1）ArrayList随机访问高，基于数组实现可直接定位目标对象，ListedList需从头Node或尾Node遍历才能定位到目标对象。

2）linkedList在头/尾节点执行插入/删除操作的效率比ArrayList要高

3）ArrayList每次扩容的容量是当前的1.5倍，所以LinkedList所占的内存空间要更小一些

4）两者遍历效率接近，LinkedList遍历需要iterator方式，不使用get()方式，否则效率很低。

        4.3Vector：与ArrayList一样都是基于数组实现的集合，区别在于vector是线程安全（常用方法基本都是synchronized）；vector可以定义数组长度扩容因子，ArrayList不能。

        4.4CopyOnWriteArrayList：可以认为ArrayList线程安全版，主要 CopyOnWriteArrayList在写操作会先复制出一个副本，在新的副本上执行操作，然后修改引用。这种机制让 CopyOnWriteArrayList可以对读操作不加锁，这就使CopyOnWriteArrayList的读效率远高于Vector。 CopyOnWriteArrayList的理念比较类似读写分离，适合读多写少的多线程场景。但要注意，CopyOnWriteArrayList只能保证数据的最终一致性，并不能保证数据的实时一致性，如果一个写操作正在进行中且并未完成，此时的读操作无法保证能读到这个写操作的结果。

注意：二者均是线程安全的、基于数组实现的List

Vector是【绝对】线程安全的，CopyOnWriteArrayList只能保证读线程会读到【已完成】的写结果，但无法像Vector一样实现读操作的【等待写操作完成后再读最新值】的能力

CopyOnWriteArrayList读性能远高于Vector，并发线程越多优势越明显

CopyOnWriteArrayList占用更多的内存空间

5.Map类集合

       将key和value封装至Entry对象中，Map存储的元素实际是Entry。调用keySet()和values()时才将keySet和values对象实例化。

Map接口常用实现类：

       5.1.HashMap:将Entry对象存储在数组中，通过哈希表实现对Entry的快速访问。每个Entry中key的哈希值决定Entry在数组中的位置。通过key快速找到Entry，获得key对应的value。如果两个不同key计算的index一样，也就是两个不同的key对应数组同一个位置（哈希冲突），HashMap处理冲突的方法是拉链法，也就说每个位置保存实际是一个Entry链表，链表中每个Entry都拥有指向链表中后一个Entry引用。当发生哈希冲突时，冲突的Entry追加至链表的头部。当HashMap寻址时发现某个Key对应数组index上有多个Entry，便会遍历该位置上Entry链表。直到找到。

       5.2.HashTable实现思路和HashMap一致，都是通过数组存储Entry，以key的哈希值计算Entry在数组中index，用拉链法解决哈希冲突。最大的区别HashTable是线程安全的

      5.3.ConcurrentHashMap:是HashMap线程安全版，比HashTable更加高效的并发性能。

       HashTable在读写会锁定整个Entry数组，所以数据越多性能越差。ConcurrentHashMap使用分离锁思路解决并发性能，将Entry数组拆分16个Segment中，通过Hash算法决定Entry应存储在那个Segment。这样实现写操作只对一个Segment加锁。提高并发写性能。

在读操作，ConcurrentHashMap绝大多数不需要加锁，其Entry中value是volatile，保证value被修改时线程可见性，无需加锁便实现线程安全的读操作。

HashEntry类

static final class HashEntry {

final int hash;

final K key;

volatile V value;

volatile HashEntry next;

}

      注意：ConcurrentHashMap保证读操作能获取到已存在Entry的value的最新值，同时也能保证读操作可获取到已完成的写操作的内容，但如果写操作是在创建一个新的Entry，那么在写操作没有完成时，读操作是有可能获取不到这个Entry的。

总结：1.三者数据存储机制原理基本一致

         2.HashMap不是线程安全的，多线程除了不能保证数据一致性，还可能在rehash阶段引发Entry链表成环，导致死循环

         3.HashTable线程安全，保证数据一致但性能问题，并发越多性能越差

         4.ConcurrentHashMap线程是线程安全的，使用分离锁和volatile方法极大提升读写性能，同时保证大多数情况下数据一致性。但不能绝对保证（一个线程向Map加入Entry还没结束之前，其他线程不能读到新加入的Entry）

        5.4LinkedHashMap 与HashMap一致，不同在于前者在Entry基础上增加到前一个插入和后一个插入Entry的引用，实现按照Entry插入顺序进行遍历。

        5.5TreeMap 基于红黑树实现Map，其Entry类拥有左右子节点和父节点的引用，同时记录自己的颜色

static final class Entry implements Map.Entry {

K key;

V value;

Entry left = null;

Entry right = null;

Entry parent;

boolean color = BLACK;

}

红黑树是高效的平衡二叉树，及任何结点值都大于左结点，小于右节点，所以TreeMap能够实现Entry排序和快速查找。

6.Set类集合

       set接口继承Collection，存储不含重复元素。每个Set内都有一个同类型Map实例，set把元素作为key存储在自己Map实例中，value则是一个空的Object。

Set的常用实现也包括 HashSet、TreeSet、ConcurrentSkipListSet等，原理和对应的Map实现完全一致

7.Queue/Deque类集合

        Queue和Deque接口继承Collection接口，实现FIFO（先进先出）的集合。二者的区别在于，Queue只能在队尾入队，队头出队，而Deque接口则在队头和队尾都可以执行出/入队操作

ConcurrentLinkedQueue是基于链表实现的队列，队列中每个Node拥有到下一个Node的引用。由于Node类的成员都是volatile的，所以ConcurrentLinkedQueue自然是线程安全的

面试题：

1.ArrayList和LinkedList有什么区别

        ArrayList是基于动态数组的结构，使用索引在数组中查找和读取速度很快，时间复杂度O(1)，删除数据开销很大。LinkedList插入或删除效率高时间复杂度O(1)，它不需要改变数组大小，也不需要装满后重新装入新数组。LinkedList需要更多的内存每个节点都会存储数据和前后节点的位置。

2.用过哪些Map类，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们内部原理分别是什么，比如存储方式，hashcode，扩容，默认容量等？

      2.1.HashMap线程不安全，允许有null值，HashTable线程安全，不允许有null值，效率低，每个方法都是synchronized

      2.2 HashMap将Entry存储在数组中，通过哈希值实现Entry快速访问，当产生HashMap冲突采用拉链法。

        2.3 ConcurrentHashMap是hashMap线程安全版，HashTable在读写锁定整个Entry数组性能差，ConcurrentHashMap使用分离锁思路解决并发性能，将Entry数组拆分16个Segment中，通过Hash算法决定Entry应存储在那个Segment。这样实现写操作只对一个Segment加锁提高并发写性能，在读操作时，value值通过volatile修饰的，达到线程可见性。

        2.4HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。HashMap默认的初始化大小为16，之后每次扩充为原来的2倍。

3.JAVA8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计怎么设计？

       JDK8放弃Segment分段锁，启用全新的方式：CAS算法，其实底层依然使用数组”+链表+红黑树方式思想。

4. 有没顺序的Map实现类，如果有，他们是怎么保证有序的 ？

       TreeMap和LinkedHashMap是有序的。（TreeMap默认升序，LinkedHashMap则记录了插入顺序）。

5.hashset与hashMap区别

        HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。

public boolean add(Object o)方法用来在Set中添加元素，当元素值重复时则会立即返回false，如果成功添加的话会返回true。

HashSet和HashMap的区别

*HashMap**HashSet*

HashMap实现了Map接口HashSet实现了Set接口

HashMap储存键值对HashSet仅仅存储对象

使用put()方法将元素放入map中使用add()方法将元素放入set中

HashMap中使用键对象来计算hashcode值HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false

HashMap比较快，因为是使用唯一的键来获取对象HashSet较HashMap来说比较慢

参考：http://weizhan.51cto.com/article/view/591c117ef2dd875f6f298f42?is_share=1