最近面试时经常遇到java集合类的问题，在网上搜索，做笔记
百度的照片
集合的类型主要有三种： set (集)、list (列表)和map (映射)。
集合接口分为Collection和Map，list、set实现了Collection接口
列表总结：
可以重复，也可以从索引中取出附加数据，使其与插入顺序一致，还可以包含空元素
ArrayList:的基本数据结构使数组结构的array查询速度更快，添加和删除速度更慢。 由于以数组的形式保存，所以随机访问非常快。
Vector :底层为数组结构的array，与ArrayList相同，查询速度快，增删慢；
LinkedList:的基础是使用链表结构，添加删除速度快，查询稍慢；
ArrayList和Vector的区别：
1 .如果集合中的元素数大于当前集合中数组的长度，则向量增长率为当前数组长度的100%，ArryaList增长率为当前数组长度的50%。 因此，如果要在集合中使用数据量大的数据，则使用向量会有好处
2 .因为线程同步ArrayList是线程异步的，所以Vector线程是安全的，但由于每个方法都添加了同步，因此有效地小于ArrayList
Set总结：
数据无序且唯一的实现类不是线程安全的类，解决方案： setset=collections.sysnchronizedset (set对象)；
hashSet:set接口(set接口继承了Collection接口) )是最常用的实现类，顾名思义，在基础上使用哈希表)散列/散列算法其基础其实也是数组，存在的意义是提供查询速度，插入速度也比较快，但应用于少量数据的插入操作，是判断两个对象是否相等的规则。 1、equals为true、hashCode的值相同。 要求：哈希表中存在的所有对象元素都必须复盖equals和hashCode方法。
linked hashset :由于继承了hashset类，因此其基础还使用了哈希表数据结构，但为了保持数据的优先添加顺序，还添加了链表结构。 但是，由于经常添加一种数据结构，所以效率很低，不推荐。 如果集合需要避免元素突然重叠，则还需要记录元素的优先添加顺序。 选择使用链接集
TreeSet:Set接口实现类还具有set接口的一般特性，不同之处在于他也实现了SortSet接口。 在此基础上采用了红黑树算法(各节点为黑或红根节点为黑各叶节点为黑如果一个节点为红则对于他的两个子节点为黑各节点，从该节点到其所有后代叶节点的简单路径红黑树是众多“平衡”搜索树之一，保证最坏情况下基本操作集合的时间复杂度为O(lgn )。 推广：二叉搜索树的性质：或空树； 或者，如果左子树不为空，则是具有左子树所有节点的值小于该根节点的值的性质的二叉树； 在右子树不为空的情况下，右子树的所有节点的值大于根节点的值； 左、右子树也分别是二叉排序树。 如果子树为空，则搜索不成功。 请注意，TreeSet集合只能存储对同一类型对象的引用。
Tree最重要的是两种排序方法：自然排序和客户端排序
自然排序； 因为实现了Comparable接口，所以TreeSet可以调用对象的ComparableTo )方法来比较集合的大小，并按升序排序。 这种排序方法称为自然排序。 其中实现Comparable接口的有BigDecimal、BigInteger、Byte、Double、Float、Integer、Long、Short (按数字大小排序) Character
客户化排序：其实就是实现java.util.ComparatorType接口提供的具体排序方法。 类型是具体比较对象的类型。 他有比较的方法，例如如果比较(x，y )的返回值大于0，则表示x大于y，可以在按照自己的想法排序时改写比较
地图总结：
java的映射(Map )是一组映射关键对象和值对象的集合，每个元素都包含关键对象和值对象。 其中，值对象可以是Map类型的数据，因此Map支持多级别映射。 Map中的键是唯一的，但值可以不是唯一的。 Map集合有两个称为HashMap的实现，它们使用哈希表完成。 它和HashSet都是利用哈希表进行的。 区别在于，在哈希表的每个桶中，HashSet只有key，HashMap在每个key上乘以value。 另一种是TreeMap，它提供了一个SortMap界面，即红黑树数据结构，与TreeSet一样，提供了两种排序方式：自然排序和客户化排序。 哈希表不提供排序。
HashMap :在哈希表实现原理中，首先用一个数组表示位桶。 每个位时段的实现最多使用1.8个链表，但如果每个位时段的数据较多，则使用链表查询
的效率就会不高，因此在1.8之后，当位桶的数据超过阈值（8）的时候，就会采用红黑树来存储该位桶的数据（在阈值之前还是使用链表来进行存储），所以，哈希表的实现包括数组+链表+红黑树，在使用哈希表的集合中我们都认为他们的增删改查操作的时间复杂度都是O(1)的，不过常数项很大，因为哈希函数在进行计算的代价比较高,HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。TreeMap：TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。TreeMap 实现了Cloneable接口，意味着它能被克隆。TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
HashTable:Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value，线程安全。