Collection接口

Collection接口是所有集合的祖先类。他有两个构造方法，一个无参构造，一个是带Collection参数的构造函数。同时Collection还继承了Iterable接口，所以集合类都可以使用迭代器进行遍历。

特点：

1. Linked开头的适合快速插入,删除元素, linked维护元素插入的次序

2. Set 在 HashMap 的基础上实现, 所以Set结尾的key是不会重复的

3. Tree开头的是每次改变发生排序的, 速度慢

Iterable

Iterable接口有一个iterator变量，实现该接口的对象可以使用“for-each ”循环，进行遍历。该对象有两个方法，一个是遍历时使用的forEach方法，还有一个方法是spliterator方法，该方法返回一个Spliterator对象，该对象也是遍历的对象，相对于iteratot，他是为了并行遍历数据源中的数据而设计的。

List

List接口实现了Collection接口，其中有一些方法如下：

ArrayList和LinkedList区别

1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

ArrayList

实现的接口和类：ArrayList继承了AbstractList类，实现了List接口，RandomAccess接口，Cloneable接口，java.io.Serializable接口。

其中AbstractList类：提供 List 接口的骨干实现，从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。

RandomAccess接口： List(随机访问列表)要实现此接口，而顺序访问不需要实现该接口。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

Cloneable接口：所有类若要使用clone方法必须要实现Clonneable接口，但是这个空接口，以达到标记的作用，不然会报CloneNotSupportedException

java.io.Serializable接口：表示序列化，是一个空接口。序列化，用在将对象编码成字节流（序列化）及从字节流编码重构对象（反序列化）。序列化   为远程通信提供了标准的wire-level协议。

ArrayList是一个数组存储结构，相当于动态的数组。与真实的数组比较，他的容量能够动态增长，和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList

ArrayList构造方法

ArrayList(int initialCapacity)  创建指定大小的集合

ArrayList()   创建默认的list集合

ArrayList(Collection c) 创建以指定集合为模板的一个集合。

ArrayList自己的API

void  ensureCapacity(int minimumCapacity) 如果要增加的数据量很大，应该使用ensureCapacity()方法，该方法的作用是预先设置Arraylist的大小，这样可以大大提高初始化速度。

void   trimToSize() 删除预留的空间

void   removeRange(int fromIndex, int toIndex) 删除一定范围的元素

ArrayList包含了两个重要的对象：elementData 和 size。

(01) elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。

(02) size 则是动态数组的实际大小。

ArrayList特点

(01) ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。

(02) 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。

(03) ArrayList的克隆函数，即是将全部元素克隆到一个数组中。

(04) ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

ArrayList的遍历方式

(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

Integer value = null;

Iterator iter = list.iterator();

while (iter.hasNext()) {

value = (Integer)iter.next();

}

(02) 第二种，随机访问，通过索引值去遍历。

由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。

Integer value = null;

int size = list.size();

for (int i=0; i<size;i++){

value=(Integer)list.get(i);

}

(03) 第三种，for循环遍历。如下：

Integer value = null;

for (Integer integ:list) {

value = integ;

}

遍历时，通过索引值去遍历的效率最高，使用迭代器的效率最低。

toArray（）异常

当我们调用ArrayList中的 toArray()，可能遇到过抛出“java.lang.ClassCastException”异常的情况。下面我们说说这是怎么回事。

ArrayList提供了2个toArray()函数：

Object[] toArray()

T[] toArray(T[] contents)

调用 toArray() 函数会抛出“java.lang.ClassCastException”异常，但是调用 toArray(T[] contents) 能正常返回 T[]。toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型(如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。解决该问题的办法是调用T[] toArray(T[] contents) ， 而不是 Object[] toArray()。

调用 toArray(T[] contents) 返回T[]的可以通过以下几种方式实现。

public static Integer[] vectorToArray1(ArrayListv) { 

  Integer[] newText = new Integer[v.size()]; 

  v.toArray(newText);    r

eturn newText;}

// toArray(T[] contents)调用方式二。最常用！

public static Integer[] vectorToArray2(ArrayListv) { 

  Integer[] newText = (Integer[])

v.toArray(new Integer[0]);   

return newText;}

// toArray(T[] contents)调用方式三

public static Integer[] vectorToArray3(ArrayListv) {

Integer[] newText = new Integer[v.size()];

Integer[] newStrings = (Integer[])v.toArray(newText);

return newStrings;

}

ListIterator

在使用List、ArrayList、LinkedList和Vector的时候可以使用。

与普通迭代器的比较

一．相同点

都是迭代器，当需要对集合中元素进行遍历不需要干涉其遍历过程时，这两种迭代器都可以使用。

二．不同点

1.使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。

2.ListIterator有add方法，可以向List中添加对象，而Iterator不能。

3.ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。

4.ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。

5.都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。

LinkedList

LinkedList继承了AbstractSequentialist类，实现了List接口，Deque接口，Cloneable接口，java.io.Serializable接口

Deque接口：实现队列的接口

LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.

LinkedList的构造函数如下

1. public LinkedList():  ——生成空的链表

2. public LinkedList(Collection col):  复制构造函数

方法：

subList（1，4） 从下标为1的后面4个元素生成子表

add()  添加元素，默认到链表最后，也可以指定位置

addFirst（）

addLast（）

removeFirst（）

removeLast()

clear（）

toArray()

set()

add()

cotains()

使用链表实现栈效果

class StackL {

private LinkedList list = new LinkedList();

public void push(Object v) {

list.addFirst(v);

}

public Object top() {

return list.getFirst();

}

public Object pop() {

return list.removeFirst();

}

使用链表实现队列效果

class Queue {

private LinkedList list = new LinkedList();

public void put(Object v) {

list.addFirst(v);

}

public Object get() {

return list.removeLast();

}

public boolean isEmpty() {

return list.isEmpty();

}

Vector

Vector继承了AbstractList，实现了List，它是一个队列，因此实现了相应的添加、删除、修改、遍历等功能。

Vector实现了RandomAccess接口，因此可以随机访问。

Vector实现了Cloneable，重载了clone()方法，因此可以进行克隆。

Vector实现了Serializable接口，因此可以进行序列化。

Vector的操作是线程安全的。

Vector的数据结构和ArrayList差不多，包含了3个成员变量：elementData，elementCount，capacityIncrement。

（1）elementData是Object[]的数组，初始大小为10，会不断的增长。

（2）elementCount是元素的个数。

（3）capacityIncrement是动态数组增长的系数。

vector的构造方法：

Vector(int initialCapacity, int capacityIncrement)

Vector(int initialCapacity)

Vector()

Vector(Collection c)

Vector有四种遍历方式：

（1）第一种通过迭代器遍历，即通过Iterator去遍历

Integer value=null;

Iterator iter=vector.iterator();

while(iter.hasNext())

{

value=(Interger)iter.next();

}

（2）第二种随机访问，通过索引进行遍历

Integer value=null;

int size=vector.size();

for(int i=0;i<size;i++){

value=vector.get(i);

}

（3）第三种通过for循环的方式

Integer value=null;

for( Integer inte： vector)

{

value=inte;

}

（4）第四种，Enumeration遍历

Integer value=null;

Enumeration enu=vector.elements();

while(enu.hasMoreElements())

{

value=(Integer)enu.nextElement();

}

Set

特点;  无序  不允许重复的

方法：

public int size() ：返回set中元素的数目，如果set包含的元素数大于Integer.MAX_VALUE，返回Integer.MAX_VALUE；

public boolean isEmpty() ：如果set中不含元素，返回true ；

public boolean contains(Object o) ：如果set包含指定元素，返回true ；

public Iterator iterator() ： 返回set中元素的迭代器，元素返回没有特定的顺序，除非set提高该保证的某些类的实例 ；

public boolean add(Object o) ：如果set中不存在指定元素，则向set加入 ；

public boolean remove(Object o) ：如果set中存在指定元素，则从set中删除 ；

public boolean removeAll(Collection c) ：如果set包含指定集合，则从set中删除指定集合的所有元素 ；

public void clear() ：从set中删除所有元素；

特点：

Set最大的特性就是不允许在其中存放的元素是重复的，根据这个特点，我们就可以使用Set 这个接口来实现前面提到的关于商品种类的存储需求。Set 可以被用来过滤在其他集合中存放的元素，从而得到一个没有包含重复新的集合。

TreeSet

无序不允许重复的，用的红黑树的数据结构存储的。

TreeSet则是对我们的Set中的元素进行排序存放。添加到 TreeSet 的元素必须是可排序的。 而同样需要对添加到TreeSet中的类对象实现 Comparable 接口的支持。与HashSet是基于HashMap实现一样，TreeSet同样是基于TreeMap实现的。我们知道TreeMap是一个有序的二叉树，那么同理TreeSet同样也是一个有序的，它的作用是提供有序的Set集合。

方法：

add：将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。

addAll：将指定 collection 中的所有元素添加到此 set 中。

ceiling：返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。

clear：移除此 set 中的所有元素。

clone：返回 TreeSet 实例的浅表副本。属于浅拷贝。

comparator：返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。

contains：如果此 set 包含指定的元素，则返回 true。

descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

descendingSet：返回此 set 中所包含元素的逆序视图。

first：返回此 set 中当前第一个（最低）元素。

floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

headSet：返回此 set 的部分视图，其元素严格小于 toElement。

higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

isEmpty：如果此 set 不包含任何元素，则返回 true。

iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

last：返回此 set 中当前最后一个（最高）元素。

lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

size：返回 set 中的元素数（set 的容量）。

subSet：返回此 set 的部分视图/**    * 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。    */   

23、tailSet：返回此 set 的部分视图

HashSet

HashSet的元素存放顺序和添加进去时候的顺序没有任何关系。如果想要判断两个对象是否是同一个对象 ,通常情况比较地址,但是现在需要通过制定内容来判断是否相同hashCode()  判断的其各个属性的hashcode  而非对象真正的地址

结论: 如果hashcode相同 有可能是相同的对象,hashcode不同 则一定不是同一个对象hashcode相同还需要equals进一步判断，即使用 equals()比如: 如果姓名和年龄都相同 就认为是同一个对象调用过程   首先调用hashcode方法  如果返回值相同则调用equals方法如果返回值不同 则不调用equals 直接认为不是同一对象。

对于HashSet而言，它是基于HashMap来实现的，底层采用HashMap来保存元素。

方法：

iterator()方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层调用HashMap的keySet返回所有的key，这点反应了HashSet中的所有元素都是保存在HashMap的key中，value则是使用的PRESENT对象，该对象为static final

size()返回此 set 中的元素的数量（set 的容量）。底层调用HashMap的size方法，返回HashMap容器的大小。

isEmpty()，判断HashSet()集合是否为空，为空返回 true，否则返回false。

contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

add()如果此 set 中尚未包含指定元素，则添加指定元素。如果此Set没有包含满足(e==null ? e2==null : e.equals(e2)) 的e2时，则将e2添加到Set中，否则不添加且返回false。由于底层使用HashMap的put方法将key = e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有value，但是key保持不变，所以如果将一个已经存在的e元素添加中HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。

remove如果指定元素存在于此 set 中，则将其移除。底层使用HashMap的remove方法删除指定的Entry。

clear从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。

LinkedHashSet

LinkedHashSet 则保持元素的添加顺序。不允许重复的  存储的 双向链表  帮助记录存储的顺序。LinkedHashSet 再去遍历的时候要比HashSet 效率高，但是在添加或者删除修改的时候效率要低(因为其记录顺序要耗费时间)

Map

方法：

特点：Map用于存储键值对，不允许键重复，值可以重复。

遍历方式：

//第一种：普遍使用，二次取值 

  System.out.println("通过Map.keySet遍历key和value：");   

for (String key : map.keySet()) {   

System.out.println("key= "+ key + " and value= " + map.get(key));    }       

//第二种   

System.out.println("通过Map.entrySet使用iterator遍历key和value：");    Iterator> it = map.entrySet().iterator();   

while (it.hasNext()) {    Map.Entryentry = it.next(); 

   System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());    }     

  //第三种：推荐，尤其是容量大时   

System.out.println("通过Map.entrySet遍历key和value"); 

  for (Map.Entryentry : map.entrySet()) {

System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());

}

//第四种

System.out.println("通过Map.values()遍历所有的value，但不能遍历key");

for (String v : map.values()) {

System.out.println("value= " + v);

}

HashMap

HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。 如果需要同步，可以用Collections.synchronizedMap(HashMap map)方法使HashMap具有同步的能力。

HashMap提供了三个构造函数：

HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

HashMap是一种支持快速存取的数据结构，要了解它的性能必须要了解它的数据结构。

每次新建一个HashMap时，都会初始化一个table数组。table数组的元素为Entry节点。其中Entry为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，这是非常重要的，正是由于Entry才构成了table数组的项为链表。

LinkedHashMap

LinkedHashMap保存了记录的插入顺序，在用Iteraor遍历LinkedHashMap时，先得到的记录肯定是先插入的。

TreeMap

TreeMap能够把它保存的记录根据键排序，默认是按升序排序，也可以指定排序的比较器，存储结构为红黑树。

LinkedHashMap保存了记录的插入顺序，在用Iteraor遍历LinkedHashMap时，先得到的记录肯定是先插入的。

其他相关接口和类

AbstractCollection

此类提供了 Collection 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。要实现一个不可修改的 collection，程序员只需扩展此类，并提供 iterator 和 size 方法的实现。（iterator 方法返回的迭代器必须实现 hasNext 和 next。）。要实现可修改的 collection，程序员还必须另外重写此类的 add 方法（否则，会抛出 UnsupportedOperationException），并且 iterator 方法返回的迭代器必须另外实现其 remove 方法。

实现的子类

     AbstractLis

此类提供 List 接口的骨干实现，从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。对于连续的访问数据（如链表），应优先使用AbstractSequentialList

     AbstractQueue

AbstractQueue是 Java Collections Framework 的成员，是一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序，也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象。

     AbstractSet

AbstractSet 类覆盖了 equals() 和 hashCode() 方法，以确保两个相等的集返回相同的散列码。若两个集大小相等且包含相同元素，则这两个集相等。按定义，集散列码是集中元素散列码的总和。因此，不论集的内部顺序如何，两个相等的集会报告相同的散列码。

AbstractMap

java.util 类 AbstractMap java.lang.Object java.util.AbstractMap此类提供了 Map 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

sortedMap

实现了排序的方法，继承该接口的类都需要实现比较方法

sortedSet

实现了排序的方法，继承该接口的类都需要实现比较方法

工具类

Arrays

sort（） 排序方法

asList（） 转换为list

binarySearch（） 二分查找

copyOf()复制

copyOfRange() 复制

equals（） 比较

fill（）填充

hashCode（）

toString（）

collections

addAll（）

binarySearch（）

copy（）复制

fill()

reverse()

Comparator()接口   java.util

compare(T t1,T t2)

equals(object o)

comparable接口 java.lang

compareTo( T t)