集合

概述:

集合是java中存储数据一种容器，可以分为单列集合Collection和双列集合Map。单列集合Collection又分为List和Set，这两个继承Collection集合；List下有ArrayList，Vector，LinkedList；Set下有HashSet，TreeSet，LinkedHashSet；双列集合Map又分为Hashtable，HashMap，TreeMap，也是继承Map集合。

Java集合类图

1.单列集合：Collection：接口

–List 有序,可重复

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

–Set 无序,唯一

HashSet
底层数据结构是哈希表。(无序,唯一)
如何来保证元素唯一性?
1.依赖两个方法：hashCode()和equals()
LinkedHashSet
底层数据结构是链表和哈希表。
1.由链表保证元素有序
2.由哈希表保证元素唯一
TreeSet
底层数据结构是红黑树。(唯一，有序)
1.如何保证元素排序的呢?
自然排序
比较器排序
2.如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定

TreeSet元素排序和唯一性的使用方式：
1.自然排序(Comparable)
自定义类实现Comparable接口并重写compareTo(Object obj)方法。
compareTo()方法和集合中的对象比较，在compareTo()中按指定属性进行排序
2.比较器排序(Comparator)
自定义类实现Comparator接口并重写compare()方法。

2.双列集合：map接口（键值对的存值方式）

–HashMap

结构：哈希表结构 : 数组+链表+红黑树（JDK1.8增加了红黑树部分）

特点：线程不安全

安全能力：可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力

唯一性：通过哈希表结构配合对象的hashCode和equals方法就可以保证键的唯一性.

–LinkedHashMap

结构：哈希表，但是额外还有链表，从而维护顺序。

特点：线程不安全，Key和Value都允许空

–TreeMap

结构：红黑树

带有键的大小排序功能。

–Hashtable

线程安全

3.对集合的理解

存储对象的容器，为了方便对多个对象的操作，存储对象，集合是存储对象最常用的一种方式。集合中可以存储任意类型的对象, 而且长度可变。在程序中有可能无法预先知道需要多少个对象, 那么用数组来装对象的话, 长度不好定义, 而集合解决了这样的问题。

集合面试题

1.ArrayList,Vector, LinkedList的区别？

ArrayList和Vector都是使用数组方式存储数据，它们都允许直接按序号索引元素，但是插入元素要涉及内存操作，所以查数据快而插入数据慢

Vector由于使用了synchronized方法（线程安全），效率比ArrayList差；

LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

2.TreeMap，TreeSet如何实现Key 的唯一性

他们底层是数据结构的实现是：维护了一棵二叉树。容器中添加元素的时候，他们有是怎么判断是否有相同元素的？我们都直到 TreeMap TreeSet 她们都是有序的存储数据。为了维护数据的唯一性。再存入数据的时候，他们会调用元素中实现的 Comparable 的 compareTo() 方法（代码1）。或者集合本身创建的时候传入了迭代器（代码2）. 具体的实现是：调用比较方法，返回-1 的时候，添加到左子树，返回1 的时候添加到右子树。返回0 有相同数据不添加该元素！

3.HashMap和Hashtable的区别？

相同点：

底层都是数组+链表实现，都是双列集合

jdk1.8版本后,HashMap多了红黑树结构

都是键不能重复，但是值可以重复

1.线程同步的区别：

HashMap是线程不同步的。

Hashtable是线程同步的。

2.存储数据的区别：

HashMap可以存储null键和null值。

Hashtable不能存储null键和null值。

4.List, Set ,Map的区别

1) 重复性

List 允许有重复元素。任何数量的重复元素都可以在不影响现有重复元素的值及其索引的情况下插入到 List。
Set 不允许重复。Set 以及所有实现了 Set 接口的类都不允许重复值的插入。
Map 以键值对的形式对元素进行存储。Map 不允许重复键但允许重复值。

2) 空值

List 允许任意数量的空值。
Set 最多允许一个空值的出现。
Map 只允许出现一个键无值，但允许任意数量的空值。

3) 排序

List 及其所有实现类保持了每个元素的插入顺序。
Set 中的元素都是无序的；但某些 Set 的实现类以某种顺序对其中的元素进行排序，比如 LinkedHashSet 按照元素的插入顺序进行排序。
Map 跟 Set 一样对元素进行无序存储，但其某些实现类对元素进行了排序。比如，TreeMap 依据键对其中的元素进行升序排序而 LinkedHashMap 则按照每个元素的插入次序进行排序。