1、Collection表示一个组纯数据,该集合继承了Iterable，Iterable是遍历集合的工具，即我们通常通过Iterator迭代器来遍历集合，我们说Collection依赖于Iterable，是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象。ListIterator是专门为遍历List而存在的
Collection类主要有三个接口：

• Set表示不允许有重复元素的集合
• List表示允许有重复元素的集合，每个元素都有它的索引，第一个元素的索引值是0。List的实现类有LinkListed,ArrayList,Vector,Stack
• Queue主要用于存储数据，而不是处理数据

2、Map表示一组key-value对

二、List接口实现类

（1）ArrayList（非线程安全）

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。
ArrayList擅长于随机访问。同时ArrayList是非同步的。

（2）LinkedList（非线程安全）

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。
由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));

（3）Vector（线程安全）

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

Vector与ArrayList的主要区别：

• Vector是线程安全的，源码中有很多的synchronized可以看出，而ArrayList不是。导致Vector效率无法和ArrayList相比
• ArrayList和Vector都采用线性连续存储空间，当存储空间不足的时候，ArrayList默认增加为原来的50%，Vector默认增加为原来的一倍
• Vector可以设置capacityIncrement，而ArrayList不可以，从字面理解就是capacity容量，Increment增加，容量增长的参数（ArrayList三个构造函数，Vector四个构造函数）

（4）Stack（线程安全）

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

三、Set接口的实现类

（1）HashSet（非线程安全）

HashSet 是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序(这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致)，而且HashSet允许使用null 元素。HashSet是非同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。 HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。

HashSet的实现方式大致如下，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象。

HashSet使用和理解中容易出现的误区:

a.HashSet中存放null值
HashSet中是允许存入null值的，但是在HashSet中仅仅能够存入一个null值。

b.HashSet中存储元素的位置是固定的
HashSet中存储的元素的是无序的，这个没什么好说的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的。

c.必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

（2）LinkedHashSet（非线程安全）

LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

（3）TreeSet（非线程安全）

TreeSet是一个有序集合，其底层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

注意：TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

使用方法：

1.自然顺序(Comparable)

TreeSet类的add()方法中会把存入的对象提升为Comparable类型

调用对象的compareTo()方法和集合中的对象比较

根据compareTo()方法返回的结果进行存储

2.比较器顺序(Comparator)

创建TreeSet的时候可以制定 一个Comparator

如果传入了Comparator的子类对象, 那么TreeSet就会按照比较器中的顺序排序

add()方法内部会自动调用Comparator接口中compare()方法排序

调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数

区别：

TreeSet构造函数什么都不传, 默认按照类中Comparable的顺序(没有就报错ClassCastException)

TreeSet如果传入Comparator, 就优先按照Comparator

四、Map接口的实现类

（1）HashMap（非线程安全）

JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。如果出现了大量hash冲突,那么遍历链表的时候,会比较慢。JDK 1.8里面，当链表的长度大于阀值(默认为8)的时候,会使用红黑树来存储数据,以便加快key的查询速度。

（2）HashTable（线程安全）

Hashtable存储的内容是键值对(key-value)映射，其底层实现是一个Entry数组+链表；

Hashtable和HashMap一样也是散列表，存储元素也是键值对；

HashMap允许key和value都为null，而Hashtable都不能为null，Hashtable中的映射不是有序的；

Hashtable和HashMap扩容的方法不一样，Hashtable中数组默认大小11，扩容方式是 old*2+1。

HashMap中数组的默认大小是16，而且一定是2的指数，增加为原来的2倍。

Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口）；

Hashtable大部分类用synchronized修饰，证明Hashtable是线程安全的。

（3）LinkedHashMap（非线程安全）

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
由于LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

（4）TreeMap

TreeMap 是一个有序的key-value集合，非同步，基于红黑树（Red-Black tree）实现，每一个key-value节点作为红黑树的一个节点。TreeMap存储时会进行排序的，会根据key来对key-value键值对进行排序，其中排序方式也是分为两种，一种是自然排序，一种是定制排序，具体取决于使用的构造方法。

自然排序(默认)：TreeMap中所有的key必须实现Comparable接口，并且所有的key都应该是同一个类的对象，否则会报ClassCastException异常。

定制排序：定义TreeMap时，创建一个comparator对象，该对象对所有的treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口。

TreeMap判断两个元素相等的标准：两个key通过compareTo()方法返回0，则认为这两个key相等。

如果使用自定义的类来作为TreeMap中的key值，且想让TreeMap能够良好的工作，则必须重写自定义类中的equals()方法，TreeMap中判断相等的标准是：两个key通过equals()方法返回为true，并且通过compareTo()方法比较应该返回为0。

    // 静态内部类用来表示节点类型
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;     // 键
    V value;   // 值
    Entry<K,V> left;    // 指向左子树的引用（指针）
    Entry<K,V> right;   // 指向右子树的引用（指针）
    Entry<K,V> parent;  // 指向父节点的引用（指针）
    boolean color = BLACK; // 
}

（5）ConcurrentHashMap

底层结构跟hashmap一样，都是通过数组+链表+红黑树实现的，不过它要保证线程安全性，所以在源码上要复杂一些

线程安全是通过CAS和synchronized实现的

五、HashSet与HashMap判断元素重复

（1）JDK规范（equals与hashcode方法）

这个问题主要是针对映射相关的操作（当类需要放在HashTable、HashMap、HashSet等等hash结构的集合）
查询的时候是通过key查询的
在Java API文档中关于hashCode方法有以下几点规定：

• 在java应用程序执行期间，如果在equals方法比较中所用的信息没有被修改，那么在同一个对象上多次调用hashCode方法时必须一致地返回相同的整数。如果多次执行同一个应用时，不要求该整数必须相同。
• 如果两个对象通过调用equals方法是相等的，那么这两个对象调用hashCode方法必须返回相同的整数。
• 如果两个对象通过调用equals方法是不相等的，不要求这两个对象调用hashCode方法必须返回不同的整数。但是程序员应该意识到对不同的对象产生不同的hash值可以提供哈希表的性能。

示例：

一个类只重写了equals，将这个类放到hash结构的集合当中，key相等，value却不相等（key1和key2相等，通过key1、key2查出不同的结果）

public class test {
    public static void main(String[] args) {
    Value value = new Value(2);
    Map<Key,Value> map2 = new HashMap<Key,Value>();
    Key k1 = new Key("A");
    Key k2 = new Key("A");
    map2.put(k1, value);
    System.out.println("k1.equals(k2):"+k1.equals(k2));
    System.out.println("map2.get(k1):"+map2.get(k1));
    System.out.println("map2.get(k2):"+map2.get(k2));
    }
    static class Key{
    private String k;
    public Key(String key){
        this.k=key;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Key){
            Key key=(Key)obj;
            return k.equals(key.k);
        }
        return false;
    }
    }
    static class Value {
    private int v;
    public Value(int v) {
        this.v = v;
    }
    }
    }
结果：
k1.equals(k2):true
map2.get(k1):test.test$Value@1540e19d
map2.get(k2):null

（2）判断原理

其实HashSet的底层本身就是通过HashMap来实现的,所以他的判断原理和HashMap是一样的,也是先判断hashcode再判断equals。
HashSet不能添加重复的元素，当调用add（Object）方法时候，
首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；

如果已存在则调用Object对象的equals方法判断是否返回true，如果为true则说明元素已经存在，如为false则插入元素。