面试之java集合

java集合

java集合分类：（普通集合、同步集合、并发集合）

普通集合

Connection接口

List 有序,可重复

ArrayList
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程不安全，效率高

LinkedList
优点: 底层数据结构是双向链表，查询慢，增删快。
缺点: 线程不安全，效率高

Vector
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程安全，效率低

Set 无序,唯一

HashSet
底层数据结构是哈希表。(无序,唯一)
如何来保证元素唯一性?
1.依赖两个方法：hashCode()和equals()

LinkedHashSet
底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
1.由链表保证元素有序
2.由哈希表保证元素唯一

TreeSet
底层数据结构是红黑树。(唯一，有序)

Map接口（key-value 的键值对，key 不允许重复，value 可重复，重复时会覆盖前一个key）

Map中的key：无序的、不可重复的，value：无序的、可重复的

HashMap：无序的，效率高，但不是线程安全的，key和value都允许为null。

TreeMap：有序的，底层使用红黑树，保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序。

LinkedHashMap：作为HashMap的子类，保证在遍历map元素时，可以按照添加的顺序实现遍历。因为它在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个。对于频繁的遍历操作，此类执行效率高于HashMap。

HashTable：线程安全的，但是效率低，不允许null值。

Map 集合即没有实现于 Collection 接口，也没有实现 Iterable 接口，所以不能对 Map 集合进行 for-each 遍历。

同步集合

同步集合可以简单地理解为通过synchronized来实现同步的集合。如果有多个线程调用同步集合的方法，它们将会串行执行。

1. Vector是线程安全的，源码中有很多的synchronized可以看出，而ArrayList不是。导致Vector效率无法和ArrayList相比

2. ArrayList和Vector都采用线性连续存储空间，当存储空间不足的时候，ArrayList默认增加为原来的50%，Vector默认增加为原来的一倍

3. Vector可以设置capacityIncrement，而ArrayList不可以，从字面理解就是capacity容量，Increment增加，容量增长的参数

4. Stack是继承于Vector，基于动态数组实现的一个线程安全的栈

5. arrayList、vector、Stack的共性特点：随机访问速度快，插入和移除性能较差(这是数组的特点，三者的底层均为数组实现)

6. HashMap是非synchronized的，而Hashtable是synchronized的。这说明Hashtable是线程安全的，而且多个线程可以共享一个Hashtable

7. 由于Hashtable是线程安全的，也是synchronized的，所以在单线程环境下比HashMap要慢

8. HashMap可以存在null的键值(key)和值(value),但是Hashtable是不可以的

同步集合在单线程的环境下能够保证线程安全，但是通过synchronized同步方法将访问操作串行化，导致并发环境下效率低下。而且同步集合在多线程环境下的复合操作（迭代、条件运算如没有则添加等）是非线程安全，需要客户端代码来实现加锁。

并发集合

并发集合 是jdk5.0重要的特性，增加了并发包java.util.concurrent.*。Java内存模型、volatile变量及AbstractQueuedSynchronizer(简称AQS同步器)，是并发包众多实现的基础。

常见的并发集合：

1. ConcurrentHashMap：线程安全的HashMap的实现
2. CopyOnWriteArrayList：线程安全且在读操作时无锁的ArrayList
3. CopyOnWriteArraySet：基于CopyOnWriteArrayList，不添加重复元素
4. ArrayBlockingQueue：基于数组、先进先出、线程安全，可实现指定时间的阻塞读写，并且容量可以限制
5. LinkedBlockingQueue：基于链表实现，读写各用一把锁，在高并发读写操作都多的情况下，性能优于ArrayBlockingQueue