集合

为什么会出现集合

我们在编程时需要容器，但是数组的特点是长度固定的，所以集合诞生了。

集合和数组的区别

1、集合的总长度是可变的，数组的总长度是固定的。
2、集合只能存储引用数据类型的数据，而数组可以存储引用数据类型和基本数据类型的数据。
3、集合能够存储各种类型的数据，而数组只能存储单一数据类型

集合关系图

Java集合要从两大接口说起，一为Collection接口，二为Map接口，都继承了Iterable接口。

Iterator接口

Iterator接口提供了为不同类型集合中的元素进行遍历的统一方法。通过Collection接口中的iterator方法可以返回一个Iterator接口的实例（迭代器）。该实例可以通过hasNext()方法检测迭代器中是否有更多的元素，next()方法顺序访问集合的元素等。

注：java集合框架中的所有具体类中都实现了Cloneable和Serializable接口，因此它们的实例都是可复制且可序列化的。

Collection

Collection 被List接口,set接口,Queue接口继承。

List

List接口有三个实现类，ArrayList，LinkedList，Vector；

特点：有索引，精准操作元素；

元素有序，存储及取出时顺序一致；

元素可重复，通过.equals()比较是否重复。

它利用索引(index)，定义了一些特殊方法：

get(int index,E e) 获取指定位置的元素；remove(int index)移除指定位置的元素;

add(int index,E e) 将元素添加到指定位置；set(int index,E e) 用元素替换指定位置的元素；

ArrayList

底层是一个数组，一旦数组长度添加到超过原本的数组长度，那么数组长度会自动膨胀到之前长度的大概1.5倍，这就意味着如果后面不填的话，也会在内存中消耗内存。
ArrayList的优势在与可以通过数组下标快速的进行查询，缺点在于如果在极限情况下 增加和删除 都会消耗大量的时间，比如要在下标0的位置进行增加和删除
因为要让后面的数据前移或者后挪，时间消耗会很大

LinkedList

LinkedList的底层是双向链表，即在一个数据的两头分别指向了之前的数据和之后的数据，所以第一个和最后一个尤其重要，他的缺点在于每个数据占用的内存是一个固定内存 不管你的数据是大还是小 都会消耗那么多内存 而这个内存比数据单个的内存消耗的更多，因为LinkedList没有下标，所以在极限情况下查找上面消耗的时间会更多比如说我要找到集合中最中间的那一个数，可以通过虚假的下标来查找，但是他只会看你给他的下标离第一个数据近还是最后的数据近，从而决定是顺序查找还是逆序查找，但是删除和添加就会快很多，因为不用再对其他的数据进行移位。LinkedList的大部分API和ArrayList相同 但是多了First和Last 因为这两个位置的数据特别重要

Vector

Vector底层也是由数组实现的，用法基本和ArrayList一样
Vector是线程安全的，ArrayList是线程不安全的，ArrayList效率高
ArrayList在算法上做了改进

Set

Set接口被HashSet类实现，被SortedSet接口继承，同时TreeSet类实现SortedSet接口，LinkedHashSet类继承HashSet类；

特点：元素不可重复；

元素无序，存储及取出时顺序不一致；

没有索引，因此不能使用普通For循环遍历；

Set与Collection 接口中的方法基本一致，没有进行功能上的扩充；

HashSet

数据结构：JDK1.8之前：哈希表（数组+单向链表）；JDK1.8之后：哈希表（数组+单向链表+红黑树），当链表长度超过阈
值（8）时，链表将转换为红黑树。

特点：查询快，元素无序，元素不可重复，没有索引；

底层分析：哈希表底层用数组+单向链表实现，即使用链表处理冲突，同一Hash值的元素都存储在一个链表里，但是当位于一个链表中的元素较多，即Hash值相等的元素较多，通过key值依次查找的效率降低。JDK1.8之后，哈希表底层采用数据+单向链表+红黑树实现，当链表长度超过阈值（8）时，链表将转换为红黑树，极大缩短查询时间。

值不能重复，自然排序的 对象引用也不能重复 但是如果对象的属性值都是一样的话 需要重写equals方法和Hashcode方法让计算机以为两个引用是一样的 以达到不同对象的值一样也不能存 无法通过普通for循环进行遍历

TreeSet

TreeSet是SortSet接口中的一个具体子类，其中SortSet为Set的子接口。在LinkedHashSet中，可以通过元素插入的顺序对元素排序，但是有时候需要自定义元素排序的顺序，在TreeSet中，只要对象可比较，即可添加进树形集中，并且可通过以下两种方式进行排序：
1.使用Comparable接口实现。当插入的对象为Comparable实例（如String,Date等）时，就可以通过接口中的compareTo对对象进行排序。此种排序方式为自然顺序。
2.使用比较器接口Comparator实现。有时我们可能需要自定义元素排序的顺序，或者说对象不是Comparable的实例，就可以通过比较器中的compare(object e1, object e2)方法来实现自定义的排序。此种排序方式为比较器顺序。
主要构造方法：

Map

特点：元素包含两个值（key,value）即键值对， key不允许重复，value可以重复, key与value是一一对应的。元素无序；

HashMap

容器里面放置了两组对象，一组key 一组value ，一个key对应了一个value ， 自然排序，而且顺序一直改变

数据结构：JDK1.8之前：哈希表（数组+单向链表）；JDK1.8之后：哈希表（数组+单向链表+红黑树），当链表长度超过阈值（8）时，链表将转换为红黑树。

特点：查询快，元素无序，key不允许重复但可以为null，value可以重复。

TreeMap

数据结构：红黑树

特点：查询快，元素有序，key不允许重复并且不可以为null，value可以重复。

大致和HashMap相同 这里面的key也是像TreeSet一样可以自然排序也可以自定义排序

一些集合面试题

Java 集合框架的基础接口有哪些？

Collection ，为集合层级的根接口。一个集合代表一组对象，这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。
Set ，是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模，被用来代表集合，就如一副牌。
List ，是一个有序集合，可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。
Map ，是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key，每个 key 最多只能映射一个 value 。
一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。

HashSet是如何保证数据不可重复的？

HashSet的底层其实就是HashMap，由于HashMap的K值本身就不允许重复，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V，那么在HashSet中执行这一句话始终会返回一个false，导致插入失败，这样就保证了数据的不可重复性。

HashMap与HashTable的区别？

1、HashMap没有考虑同步，是线程不安全的。Hashtable使用了synchronized关键字，是线程安全的。
2、HashMap允许K/V都为null。后者K/V都不允许为null。
3、HashMap继承自AbstractMap类。而Hashtable继承自Dictionary类。

线程安全和线程不安全区别？

线程安全就是多个并行线程访问共享数据时，采用了加锁机制，当一个线程访问共享数据时，进行保护，其他线程不能进行访问，直到该线程读取完，其他线程才可使用。不会出现数据不一致或者数据污染。线程不安全就是不提供共享数据访问保护，有可能出现多个线程先后更改共享数据，造成所得到的共享数据是脏数据。

Array和ArrayList 有什么区别？

1、Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
2、Array 大小是固定的，ArrayList的大小是动态变化的。
3、ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。

ArrayList和LinkedList的区别？

1、LinkedList实现了List和Deque接口，一般称为双向链表。ArrayList实现了List接口，动态数组。
2、LinkedList在插入和删除数据时效率更高，ArrayList在查找某个index的数据时效率更高。
3、LinkedList比ArrayList需要更多的内存。