Java提供的众多集合类由两大接口衍生而来：Collection(单列集合)接口和Map（双列集合）接口

一 、Collection接口

Collection接口定义了一个包含一批对象的集合。接口的主要方法包括：

• size() - 集合内的对象数量

• add(E)/addAll(Collection) - 向集合内添加单个/批量对象

• remove(Object)/removeAll(Collection) - 从集合内删除单个/批量对象

• contains(Object)/containsAll(Collection) - 判断集合中是否存在某个/某些对象

• toArray() - 返回包含集合内所有对象的数组

Collection接口衍生出来的常用集合类：

List类集合

List接口继承自Collection，用于定义以列表形式存储的集合，List接口为集合中的每个对象分配了一个索引(index)，标记该对象在List中的位置，并可以通过index定位到指定位置的对象。

List在Collection基础上增加的主要方法包括：

• get(int) - 返回指定index位置上的对象

• add(E)/add(int, E) - 在List末尾/指定index位置上插入一个对象

• set(int, E) - 替换置于List指定index位置上的对象

• indexOf(Object) - 返回指定对象在List中的index位置

• subList(int,int) - 返回指定起始index到终止index的子List对象

等

List接口的常用实现类：

1. ArrayList

ArrayList基于数组来实现集合的功能，其内部维护了一个可变长的对象数组，集合内所有对象存储于这个数组中，并实现该数组长度的动态伸缩

ArrayList使用数组拷贝来实现指定位置的插入和删除：

插入：

删除：

2. LinkedList

LinkedList基于链表来实现集合的功能，其实现了静态类Node，集合中的每个对象都由一个Node保存，每个Node都拥有到自己的前一个和后一个Node的引用

LinkedList追加元素的过程示例：

ArrayList vs LinkedList

ArrayList的随机访问更高，基于数组实现的ArrayList可直接定位到目标对象，而LinkedList需要从头Node或尾Node开始向后/向前遍历若干次才能定位到目标对象
LinkedList在头/尾节点执行插入/删除操作的效率比ArrayList要高
由于ArrayList每次扩容的容量是当前的1.5倍，所以LinkedList所占的内存空间要更小一些
二者的遍历效率接近，但需要注意，遍历LinkedList时应用iterator方式，不要用get(int)方式，否则效率会很低

3. Vector

Vector和ArrayList很像，都是基于数组实现的集合，它和ArrayList的主要区别在于

• Vector是线程安全的，而ArrayList不是

• 由于Vector中的方法基本都是synchronized的，其性能低于ArrayList

• Vector可以定义数组长度扩容的因子，ArrayList不能

二 、Map接口

Map接口在Collection的基础上，为其中的每个对象指定了一个key，并使用Entry保存每个key-value对，以实现通过key快速定位到对象(value)。Map接口的主要方法包括：

• size() - 集合内的对象数量

• put(K,V)/putAll(Map) - 向Map内添加单个/批量对象

• get(K) - 返回Key对应的对象

• remove(K) - 删除Key对应的对象

• keySet() - 返回包含Map中所有key的Set

• values() - 返回包含Map中所有value的Collection

• entrySet() - 返回包含Map中所有key-value对的EntrySet

• containsKey(K)/containsValue(V) - 判断Map中是否存在指定key/value

• 
  

Map常用实现类

HashMap

HashMap将Entry对象存储在一个数组中，并通过哈希表来实现对Entry的快速访问：

 

由每个Entry中的key的哈希值决定该Entry在数组中的位置。以这种特性能够实现通过key快速查找到Entry，从而获得该key对应的value。在不发生哈希冲突的前提下，查找的时间复杂度是O(1)。

如果两个不同的key计算出的index是一样的，就会发生两个不同的key都对应到数组中同一个位置的情况，也就是所谓的哈希冲突。HashMap处理哈 希冲突的方法是拉链法，也就是说数组中每个位置保存的实际是一个Entry链表，链表中每个Entry都拥有指向链表中后一个Entry的引用。在发生哈希冲突时，将冲突的Entry追加至链表的头部。当HashMap在寻址时发现某个key对应的数组index上有多个Entry，便会遍历该位置上的 Entry链表，直到找到目标的Entry。

HashMap的Entry类：

static class Entry

HashMap由于其快速寻址的特点，可以说是最经常被使用的Map实现类

三 、Set类集合

Set 接口继承Collection，用于存储不含重复元素的集合。几乎所有的Set实现都是基于同类型Map的，简单地说，Set是阉割版的Map。每一个Set内都有一个同类型的Map实例（CopyOnWriteArraySet除外，它内置的是CopyOnWriteArrayList实例），Set把元素作为key存储在自己的Map实例中，value则是一个空的Object。Set的常用实现也包括 HashSet、TreeSet、ConcurrentSkipListSet等，原理和对应的Map实现完全一致

JAVA常见的集合类特点分析

java集合类存放于java.util包中，集合类存放的都是对象的引用，而非对象本身，出于表达上的便利，我们称集合中的对象就是指集合中对象的引用，集合类型主要有3种：set(集）、list(列表）和map(映射)。

Java API中所用的集合类，都是实现了Collection接口，它的一个类继承结构如下：

Collection<--List<--Vector

Collection<--List<--ArrayList

Collection<--List<--LinkedList

Collection<--Set<--HashSet

Collection<--Set<--HashSet<--LinkedHashSet

Collection<--Set<--SortedSet<--TreeSet

 

List(有序,可重复)：      1.Vector  底层数据结构是数组,查询快,增删慢,线程安全,效率低。

                                2.ArrayList 底层数据结构是数组,查询快,增删慢 , 线程不安全,效率高。

                                3.LinkedList 底层数据结构是链表,查询慢,增删快,线程不安全,效率高。

Set(无序,唯一)    ：     1.HashSet 底层数据结构是哈希表; 哈希表依赖两个方法：hashCode()和equals() ,执行顺序：首先判断hashCode()值是否相同,如果是，继续执行equals(),看其返回值如果为true说明元素重复，则不添加 ，如果是false就添加到集合 。若hashCode()值不相同：就直接添加到集合

                                2.LinkedHashSet  底层数据结构由链表和哈希表组成。链表保证元素有序，哈希表保证元素唯一。

                                3.TreeSet 底层数据结构是红黑树。(是一种自平衡的二叉树)  根据比较的返回值是否是0来保证元素唯一性，其元素的排序通常为两种方式,第一种方式为自然排序(元素具备比较性) ，让元素所属的类实现Comparable接口 ， 第二种方式为比较器排序(集合具备比较性) ，让集合接收一个Comparator的实现类对象。

 

map(映射)           :     1.Map集合的数据结构仅仅针对键有效，与值无关。存储的是键值对形式的元素，键唯一，值可重复。 

                                2.hashMap 底层数据结构是哈希表。线程不安全，效率高 ; 哈希表依赖两个方法：hashCode()和equals();hashCode()和equals()执行顺序为 : 首先判断hashCode()值是否相同,如果是true则继续执行equals(),若返回值是true, 则说明元素重复，不添加，反之则添加; 若首先判断hashCode()值是false, 则添加到集合中。

                                3.LinkedHashMap 底层数据结构由链表和哈希表组成；链表保证元素有序， 哈希表保证元素唯一。

                                4.Hashtable 底层数据结构是哈希表。线程安全，效率低； 哈希表依赖两个方法：hashCode()和equals()；hashCode()和equals()执行顺序为 : 首先判断hashCode()值是否相同,如果是true则继续执行equals(),若返回值是true, 则说明元素重复，不添加，反之则添加; 若首先判断hashCode()值是false, 则添加到集合中。

                                5.TreeMap 底层数据结构是红黑树(一种自平衡的二叉树) ，其根据比较的返回值是否是0来保证元素唯一性， 元素的排序通过两种方式：第一种是自然排序(元素具备比较性) 即让元素所属的类实现Comparable接口，第二种是比较器排序(集合具备比较性) ，即让集合接收一个Comparator的实现类对象。

一. Java集合框架概述 
Java平台包括集合框架。 集合框架是用于表示和操作集合的统一体系结构，使集合可以独立于实现细节进行操作。集合框架主要具有以下优势： 
1、通过提供数据结构和算法减少编程工作 
2、提供高性能实现的数据结构和算法来提高程序性能 
3、通过建立共同语言来回传递集合，提供不相关API间的互操作性 
4、通过学习特定的集合API减少学习API的成本 
5、减少了设计和实现集合API的工作量 
6、通过为集合和算法提供标准接口实现软件重用 
二、 集合的关系 
下图是经常使用的集合，他们之间的关系如图： 

    

三、 各个集合的特点及使用场景

1、List：(元素有放入顺序，元素可重复)可以迭代也可以直接根据下标获取元素。List接口有两个常用子类，一个是ArrayList,一个是LinkedList。 

1.1、ArrayList : 基于数组实现的非线程安全的集合。查询元素快，插入，删除中间元素慢。 
1.2、LinkedList : 基于链表实现的非线程安全的集合。查询元素慢，插入，删除中间元素快。 

2、set:(元素无放入顺序，元素不可重复，重复元素会覆盖掉),只能用迭代获取元素。不能直接遍历集合获取。set接口下的常用子类说明； 
2.1、 HashSet： HashSet是Set接口的典型实现，HashSet使用HASH算法来存储集合中的元素，因此具有良好的存取和查找性能。当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该HashCode值决定该对象在HashSet中的存储位置。值得主要的是，HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法的返回值相等。 
2.2、 SortedSet：此接口主要用于排序操作，即实现此接口的子类都属于排序的子类。 
2.2.1、TreeSet：TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。

3、Map: Map的主要特点是键值对的形式，一一对应，且一个key只对应1个value。其常用的Map实现类主要有HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap、weakHashMap等等。其最常使用的有： 
3.1、HashMap使用位桶和链表实现（最近的jdk1.8改用红黑树存储而非链表），它是线程不安全的Map，方法上都没有synchronize关键字修饰,但实现效率较快。 
3.2、Hashtable是线程安全的一个map实现类，它实现线程安全的方法是在各个方法上添加了synchronize关键字。但实现效率较慢。 
3.3、ConcurrentHashMap，这个map实现类是在jdk1.5中加入的，其在jdk1.6/1.7中的主要实现原理是segment段锁，它不再使用和HashTable一样的synchronize一样的关键字对整个方法进行枷锁，而是转而利用segment段落锁来对其进行加锁，以保证Map的多线程安全。 
其实可以理解为，一个ConcurrentHashMap是由多个HashTable组成，所以它允许获取不用段锁的线程同时持有该资源，segment有多少个，理论上就可以同时有多少个线程来持有它这个资源。他吸收了hashmap与hashtable二者的优点。 

一. Java集合框架概述
Java平台包括集合框架。 集合框架是用于表示和操作集合的统一体系结构，使集合可以独立于实现细节进行操作。集合框架主要具有以下优势：
1、通过提供数据结构和算法减少编程工作
2、提供高性能实现的数据结构和算法来提高程序性能
3、通过建立共同语言来回传递集合，提供不相关API间的互操作性
4、通过学习特定的集合API减少学习API的成本
5、减少了设计和实现集合API的工作量
6、通过为集合和算法提供标准接口实现软件重用
二、 集合的关系
下图是经常使用的集合，他们之间的关系如图：

三、 各个集合的特点及使用场景

1、list：(元素有放入顺序，元素可重复)可以迭代也可以直接根据下标获取元素。list接口有两个常用子类，一个是arraylist,一个是linkedList。
1.1、ArrayList : 基于数组实现的非线程安全的集合。查询元素快，插入，删除中间元素慢。
1.2、LinkedList : 基于链表实现的非线程安全的集合。查询元素慢，插入，删除中间元素快。
还有Vector，CopyOnWriteArrayList，二者不经常使用，此处不作介绍。

2、set:(元素无放入顺序，元素不可重复，重复元素会覆盖掉),只能用迭代获取元素。不能直接遍历集合获取。set接口下的常用子类说明；
2.1、 HashSet： HashSet是Set接口的典型实现，HashSet使用HASH算法来存储集合中的元素，因此具有良好的存取和查找性能。当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该HashCode值决定该对象在HashSet中的存储位置。值得主要的是，HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法的返回值相等。
2.2、 SortedSet：此接口主要用于排序操作，即实现此接口的子类都属于排序的子类。
2.2.1、TreeSet：TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。

3、map: map的主要特点是键值对的形式，一一对应，且一个key只对应1个value。其常用的map实现类主要有HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap、weakHashMap等等。其最常使用的有：
3.1、HashMap使用位桶和链表实现（最近的jdk1.8改用红黑树存储而非链表），它是线程不安全的Map，方法上都没有synchronize关键字修饰,但实现效率较快。
3.2、hashTable是线程安全的一个map实现类，它实现线程安全的方法是在各个方法上添加了synchronize关键字。但实现效率较慢。
3.3、ConcurrentHashMap，这个map实现类是在jdk1.5中加入的，其在jdk1.6/1.7中的主要实现原理是segment段锁，它不再使用和HashTable一样的synchronize一样的关键字对整个方法进行枷锁，而是转而利用segment段落锁来对其进行加锁，以保证Map的多线程安全。
其实可以理解为，一个ConcurrentHashMap是由多个HashTable组成，所以它允许获取不用段锁的线程同时持有该资源，segment有多少个，理论上就可以同时有多少个线程来持有它这个资源。他吸收了hashmap与hashtable二者的优点。

以上就是我对最常使用集合的了解，具体使用什么集合类型进行数据获取，可以根据他的优缺点进行实际得考虑。从而提高程序性能。

list：(元素有放入顺序，元素可重复)可以迭代也可以直接根据下标获取元素。list接口有两个常用子类，一个是arraylist,一个是linkedList。
1.1、ArrayList : 基于数组实现的非线程安全的集合。查询元素快，插入，删除中间元素慢。
1.2、LinkedList : 基于链表实现的非线程安全的集合。查询元素慢，插入，删除中间元素快。
还有Vector，CopyOnWriteArrayList，二者不经常使用，此处不作介绍。

2、set:(元素无放入顺序，元素不可重复，重复元素会覆盖掉),只能用迭代获取元素。不能直接遍历集合获取。set接口下的常用子类说明；
2.1、 HashSet： HashSet是Set接口的典型实现，HashSet使用HASH算法来存储集合中的元素，因此具有良好的存取和查找性能。当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该HashCode值决定该对象在HashSet中的存储位置。值得主要的是，HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法的返回值相等。
2.2、 SortedSet：此接口主要用于排序操作，即实现此接口的子类都属于排序的子类。
2.2.1、TreeSet：TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。

3、map: map的主要特点是键值对的形式，一一对应，且一个key只对应1个value。其常用的map实现类主要有HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap、weakHashMap等等。其最常使用的有：
3.1、HashMap使用位桶和链表实现（最近的jdk1.8改用红黑树存储而非链表），它是线程不安全的Map，方法上都没有synchronize关键字修饰,但实现效率较快。
3.2、hashTable是线程安全的一个map实现类，它实现线程安全的方法是在各个方法上添加了synchronize关键字。但实现效率较慢。
3.3、ConcurrentHashMap，这个map实现类是在jdk1.5中加入的，其在jdk1.6/1.7中的主要实现原理是segment段锁，它不再使用和HashTable一样的synchronize一样的关键字对整个方法进行枷锁，而是转而利用segment段落锁来对其进行加锁，以保证Map的多线程安全。
其实可以理解为，一个ConcurrentHashMap是由多个HashTable组成，所以它允许获取不用段锁的线程同时持有该资源，segment有多少个，理论上就可以同时有多少个线程来持有它这个资源。他吸收了hashmap与hashtable二者的优点。