java八股文面试[数据结构]—

java八股文面试[数据结构]——集合框架

Java集合体系框架

Java集合类主要由两个根接口Collection和Map派生出来的。

Collection派生出了三个子接口：

Map接口派生：

Map代表的是存储key-value对的集合，可根据元素的key来访问value。

因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。

Java集合List

List代表了有序可重复集合，可直接根据元素的索引来访问。

List接口常用的实现类有：ArrayList、LinkedList、Vector。

List集合特点

集合中的元素允许重复
集合中的元素是有顺序的，各元素插入的顺序就是各元素的顺序
集合中的元素可以通过索引来访问或者设置

ArrayList

ArrayList是一个动态数组，也是我们最常用的集合，是List类的典型实现。

它允许任何符合规则的元素插入甚至包括null，每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。

随着容器中的元素不断增加，容器的大小也会随着增加，在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。

所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

ArrayList擅长于随机访问，同时ArrayList是非同步的。

Vector

与ArrayList相似，但是Vector是同步的，它的操作与ArrayList几乎一样。

LinkedList

LinkedList是采用双向循环链表实现，LinkedList是List接口的另一个实现，除了可以根据索引访问集合元素外，LinkedList还实现了Deque接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。

Java List总结

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

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

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

Java集合Set

Set扩展Collection接口,无序集合，不允许存放重复的元素。

Set接口常用的实现类有：HashSet、LinkedHashSet、TreeSet

HashSet

HashSet是Set集合最常用实现类，是其经典实现。

HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。

LinkedHashSet

底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。

（面试题：设计一个记录存储顺序的HashSet思路）

TreeSet

底层数据结构采用二叉树来实现，元素唯一且已经排好序,唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。

Java Set总结

1）HashSet

底层其实是包装了一个HashMap实现的
底层数据结构是数组+链表 + 红黑树
具有比较好的读取和查找性能，可以有null 值
通过equals和HashCode来判断两个元素是否相等
非线程安全

2）LinkedHashSet

继承HashSet，本质是LinkedHashMap实现
底层数据结构由哈希表(是一个元素为链表的数组)和双向链表组成。
有序的，根据HashCode的值来决定元素的存储位置，同时使用一个链表来维护元素的插入顺序
非线程安全，可以有null 值

3）TreeSet

是一种排序的Set集合，实现了SortedSet接口，底层是用TreeMap实现的，本质上是一个红黑树原理
排序分两种：自然排序（存储元素实现Comparable接口）和定制排序（创建TreeSet时，传递一个自己实现的Comparator对象）
正常情况下不能有null值，可以重写Comparable接口局可以有null值了。

Java集合Queue

队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

PriorityQueue

PriorityQueue保存队列元素的顺序并不是按照加入的顺序，而是按照队列元素的大小进行排序的。
PriorityQueue不允许插入null元素。

Deque

Deque接口是Queue接口的子接口，它代表一个双端队列,当程序中需要使用“栈”这种数据结构时，推荐使用ArrayDeque。

Java集合Map

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。

1.HashMap

Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。

它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。

可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap类。

2.Hashtable

Hashtable和HashMap从存储结构和实现来讲有很多相似之处，不同的是它承自Dictionary类，而且是线程安全的，另外Hashtable不允许key和value为null，并发性不如ConcurrentHashMap。

Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

3.LinkedHashMap

LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现，它维护着一个双重链接列表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

4.TreeMap

TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序（自然顺序），也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

5.Map总结

hashtable TreeMap key不可以为null

速记：线程安全的有：Vector Hashtable ConcurrentHashMap

其他知识点：

怎么确保一个集合不能被修改？
可以使用 Collections. unmodififiableCollection(Collection c) 方法来创建一个只读集合，这样改变
集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

如何边遍历边移除 Collection 中的元素？
边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下：
一种最常见的错误代码如下：
运行以上错误代码会报 ConcurrentModifificationException 异常。这是因为当使用
foreach(for(Integer i : list)) 语句时，会自动生成一个 iterator 来遍历该 list ，但同时该 list 正在被
Iterator.remove() 修改。 Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

Iterator 和 ListIterator 有什么区别？
Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List 。
Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前 / 后遍历）。
ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元
素、获取前面或后面元素的索引位置。

多线程场景下如何使用 ArrayList ？
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方
法将其转换成线程安全的容器后再使用。

为什么 ArrayList 的 elementData 加上 transient 修饰？
ArrayList 中的数组定义如下：
private transient Object[] elementData;
再看一下 ArrayList 的定义：
List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++) {
System.out.println(synchronizedList.get(i));
}
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。 transient 的作用
是说不希望 elementData 数组被序列化，重写了 writeObject 实现：
每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后
遍历 elementData ，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后
的文件大小。