JAVA集合框架

一、集合框架

在实际开发中，需要将对象根据不同的需求而存储在特定的数据结构容器中。但是数组虽然是一种用来存储数据的数据结构，但是它的局限性很低，很难满足各种的需求，所以JDK出现了用来满足各种需求的框架——集合框架。

“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型。 常见的集合类有：1）实现Collection接口的：List接口、Set接口。

2）实现Map接口的。

二、Collection接口

Collection接口表示了如何把一组对象作为它的元素。JDK没有直接提供Collection接口的实现，Collection接口的实现依赖于两个继承自自己的接口：Set和List。所有通过实现Collection接口的子接口的类应该提供两个标准的构造器：一个不需要参数的构造器，用来创建一个空的集合，另外一个需要一个类型作为参数的构造器，用来创建一个和参数的类型相同的元素的集合。

int size()：返回这个集合中的元素的数量。

boolean isEmpty()：返回集合是否包含元素，如果没有的话，返回true。 boolean contains(E e)：如果这个集合包含某个指定的元素，返回true。

Iterator<E> iterator()：返回这个集合中的所有元素的迭代。

boolean add(E e)：向集合中添加新的元素，如果添加成功，返回true。 boolean remove(E e)：从集合中删除指定元素，如果删除成功，返回true。

boolean containsAll(Collection<?> c)：这个集合是否包含指定集合中的所有的元素。 boolean addAll(Collection<? extends E> c)：添加指定的集合中的所有元素到这个集合中。

boolean removeAll(Collection<?> c)：删除当前集合中与给定集合相同的元素。在这个调用返回之后，这个集合将不包含和指定的集合一样的元素。

boolean retainAll(Collection<?> c)：从这个集合中删除所有不包含在指定的集合中的所有元素。

<T> T[] toArray(T[] a)：返回一个包含集合中所有的元素的数组。

void clear()：从集合中删除所有的元素。

boolean equals(Object obj)：比较这个集合和指定对象是否相等。

int hashCode()：返回这个集合的哈希值。

三、List接口

List 接口继承了 Collection 接口，用于定义一个允许重复项的有序集合。可以将List理解为存放对象的数组，只不过其元素个数可以动态的增加或者减少。该接口不但能够对列表的一部分进行处理，还添加了面向位置的操作。

面向位置的操作包括插入某个元素或 Collection 的功能，还包括获取、除去或更改元素的功能。在 List 中搜索元素可以从列表的头部或尾部开始，如果找到元素，还将报告元素所在的位置 :

void add(int index, Object element): 在指定位置index上添加元素element。

boolean addAll(int index, Collection c): 将集合c的所有元素添加到指定位置index。 Object get(int index): 返回List中指定位置的元素。

int indexOf(Object o): 返回第一个出现元素o的位置，否则返回-1。

int lastIndexOf(Object o) ：返回最后一个出现元素o的位置，否则返回-1。

Object remove(int index) ：删除指定位置上的元素。

Object set(int index, Object element) ：用元素element取代位置index上的元素，并且返回旧的元素。

在“集合框架”中有两种常规的 List 实现ArrayList 和 LinkedList，分别用动态数组和链表的方式实现List接口。可以认为ArrayList和LinkedList的方法在逻辑上完全一样，只是在性能上有一定的差别。如果要支持随机访问，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可选的集合。但如果，您要频繁的从列表的中间位置添加和除去元素，而只要顺序的访问列表元素，那么，LinkedList 实现更好。

1）LinkedList类

LinkedList类——链表实现的List，在删除或插入时只需改变链表“指针”，即可实现。

(1) void addFirst(Object o): 将对象o添加到列表的开头

void addLast(Object o)：将对象o添加到列表的结尾

(2) Object getFirst(): 返回列表开头的元素

Object getLast(): 返回列表结尾的元素

(3) Object removeFirst(): 删除并且返回列表开头的元素

Object removeLast():删除并且返回列表结尾的元素

(4) LinkedList(): 构建一个空的链接列表

LinkedList(Collection c): 构建一个链接列表，并且添加集合c的所有元素

“使用这些新方法，您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面向端点的数据结构。”

2）ArrayList类

ArrayList类——动态数组实现的List，可以通过下标迅速的索引到对应的元素，但在删除和移动时移动较多元素。

ArrayList类封装了一个动态再分配的Object[]数组。每个ArrayList对象有一个capacity。这个capacity表示存储列表中元素的数组的容量。当元素添加到ArrayList时，它的capacity在常量时间内自动增加。

在向一个ArrayList对象添加大量元素的程序中，可使用ensureCapacity方法增加capacity。这可以减少增加重分配的数量。

(1) void ensureCapacity(int minCapacity): 将ArrayList对象容量增加minCapacity

(2) void trimToSize(): 整理ArrayList对象容量为列表当前大小。程序可使用这个操作减少ArrayList对象存储空间。

四、List高级—数据结构：Queue队列

队列是常用的数据结构，可以将（Queue）队列看成特殊的线性表，队列限制了对线性表的访问方式，即只能从线性表的一段添加（offer）元素，从另一端取出（poll）元素。 队列遵循先进先出（FIFO）原则。

JDK中提供了Queue接口，同时使得LinkedList实现该接口（Queue经常要进行插入和删除的操作，而LinkedList在这方面效率最高）。

Queue接口中的主要方法：

Boolean offer（E e） 讲一个对象添加到队尾，添加成功则返回true。

E pool（） 从队首删除并返回一个元素。

E peek（) 返回队首的元素（但并不删除）。

五、List高级—数据结构：Deque栈

栈也是常用的数据结构，栈（Deque）则是Queue的子接口，定义了所谓的“双端队列”，即从队列的两端分别可以入队（offer）和出队（poll），如果将Deque限制为只能从一段入队

和出队，则可实现“栈（Stack）”的数据结构，对于栈而言，入栈称之为push，出栈称为pop。 栈遵循先进后出（FILO）原则。

Deque常用的方法：

E push（） 压入，向栈中存入数据。

E pop（） 取出，从栈中取出数据。

E peek（） 获取栈顶位置的元素，但不取出。

六、Set接口

Set 接口也是Collection 接口的子接口，但是与Collection 或List 接口不同的是，Set接口中不能加入重复的元素，是因为Set判断两个对象相同不是使用==运算符，而是根据equals方法。即两个对象用equals方法比较返回true，Set就不能接受两个对象。同时Set集合里多个对象之间没有明显的顺序。

其实Set具有与Collection完全一样的接口，除了注释不一样其他都一样，也就是Set根本没有对Collection扩展，只是对add,equals，hashCode的定义说明不一样，因为Set是不允许重复元素的。但是要注意的是：虽然Set和Collection中的方法一样，但是他们是完全不一样的，List可以自动为Collection，但是绝对不可以转为Set的。

遍历Set集合的元素只有一种方式，迭代器。同时set集合不支持索引，也不具备List集合的get（）方法。

Set 接口的常用子类:

1）散列的存放： HashSet

HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。 HashSet的特点：

（1）HashSet不是同步的，多个线程访问是需要通过代码保证同步

（2）集合元素值可以使null。

HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode（）方法返回值也相等。

其实原理是这样的：HashSet的底层采用HashMap来存放数据，HashMap的put()方法是这样的：

public V put(K key, V value) {

if (key == null)

return putForNullKey(value);

int hash = hash(key.hashCode());//----------1----------

int i = indexFor(hash, table.length);//-----------2---------

for (Entry<K,V> e = table[i]; e != null; e = e.next) {//-----------3

---------

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}//------------------4--------------------

modCount++;

addEntry(hash, key, value, i);

return null;

}

当向HashMap中添加元素的时候，首先计算元素的hashcode值，然后根据1处的代码计算出Hashcode的值，再根据2处的代码计算出这个元的存储位置如果这个位置为空，就将元素添加进去；如果不为空，则看3-4的代码，遍历索引为i的链上的元素，如果key重复，则替换并返回oldValue值。

2 ）有序的存放：TreeSet

TreeSet是SortedSet接口的唯一实现，是按排序二叉树算法来存储元素的，TreeSet可以确保集合元素处于排序状态（元素是有序的）。

七、Map

→Map用于保存具有映射关系的数据（key-vlaue）。Map的key不允许重复，即同一个Map对象的任何两个key通过equals方法比较总是返回false。

→Map集合与Set集合元素的存储形式很像，如Set接口下有HashSet、LinkedHashSet、SortedSet（接口）、TreeSet、EnumSet等实现类和子接口，而Map接口下则有HashMap、LinkedHashMap、SortedMap（接口）、TreeMap、EnumMap等实现类和子接口。 →Map的value非常类似List：元素与元素之间可以重复，每个元素可以根据索引（key）来查找。

→Map有时也称为字典，或关联数组。

→Map接口中定义如下方法：

void clear(); 删除Map对象中所有key-value对。

boolean containsKey(Object key) :查询Map中是否包含指定key，如果包含则返回true。

boolean containsValue(Object value): 查询Map中是否包含一个或多个value，如果包含则返回true。

Set entrySet(): 返回Map中所有包含的key-value对组成的Set集合，每个集合元素都是Map.Entry(Entry是Map的内部类）对象。

Object get(Obejct key): 返回指定key所对应的value；如果此Map中不包含key，则返回null。

boolean isEmpty(): 查询该Map是否为空（即不包含任何key-value对），如果为空则返回true。

Set keySet(): 返回该Map中所有key所组成的set集合。

Object put(Object key, Object value): 添加一个key-value对，如果当前Map中已有一个与该key相等的key-value对，则新的key-value对会覆盖原来的key-value对。 Object remove(Object key): 删除指定key对应的key-value对，返回被删除key所关联的value，如果该key不存在，返回null。

int size(): 返回该Map里的key-value对的个数。

Collection values(): 返回该Map里所有value组成的Collection。

Map中包括一个内部类：Entry。该类封装了一个key-value对，Entry包含三个方法： Object getkey():返回该Entry里包含的key值。

Object getValue():返回该Entry里包含的value值。

Object setValue():设置该Entry里包含的value值，并返回新设置的value值。 →可以把Map理解成一个特殊的Set，只是该Set里包含的集合元素是Entry对象，而不是普通对象。

→遍历Map有三种方式：

1、遍历map中的所有key

public Set keySet() 调用keySet（）方法会返回一个Set集合的实例，其中保留的元素为Map中所有的Key。

2、遍历Map中所有的键值对Entry

public Set entrySet() 调用entrySet（）方法会返回一个Set集合的实例，其中保存的元素为Map中的每一组键值对，每一个键值对用一个Entry实例保存。

3、遍历Map中所有的value(不常用)。

→Map接口提供了大量的实现类，如HashMap和Hashtable等，以及HashMap的子类，LinkedHashMap,还有SortedMap子接口及该接口的实现类TreeMap。

1）、HashMap和Hashtable实现类

HashMap和Hashtable都是Map接口的实现类，Hashtable是一个古老的Map实现类，它从JDK1.0起就有，它包含两个烦琐的方法：elements()(类似于Map接口定义的values()方法）和keys()（类似于Map接口定义的keySet()方法)，现在很少使用这两种方法。 两点区别：

Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高些；但如果多线程访问同一个Map对象，使用Hashtable实现类更好。 Hashtable不允许使用null作为key和value，如果为null，则引发NullPointerException异常；但HashMap可以使用null作为key或value。

由于HashMap里的可以不能重复，所以HashMap里最多只有一对key-value值为null，但可以有无数多项key-value对的value为null。

HashMap重写了toString()方法方法总是返回如下格式的字符串：{key1 = value1，key2 = value2..}

HashMap、Hashtable判断两个key相等的标准是：两个key通过equasl方法比较返回ture,两个key的hashCode值相等。

LinkedHashMap类

HashMap有一个子类：LinkedHashMap,它也是双向链表来维护key-value对的次序，该链表定义了迭代顺序，该迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序（只要插入key-value对时保持顺序即可）。同时又可避免使用TreeMap所增加的成本。

LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

2）、SortedMap接口和TreeMap实现类

Map接口派生了一个SortedMap子接口，TreeMap为其实现类。类似TreeSet排序，TreeMap也是基于红黑树对TreeMap中所有key进行排序，从而保证TreeMap中所有key-value对处于有序状态。

TreeMap两种排序方法：

自然排序：TreeMap的所有key必须实现Comparable接口，而且所有key应该是同一个类的对象，否则将会抛出ClassCastExcepiton异常。

定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeＭap中所有key进行排序。采用定制排序时不要求Map的key实现Comparable接口。

TreeMap中判断两个key相等的标准也是两个key通过equals比较返回true，而通过compareTo方法返回0，TreeMap即认为这两个key是相等的。

八、小结

List：保证以某种特定插入顺序来维护元素顺序，即保持插入的顺序，另外元素可以重复。

ArrayList：是用数组实现的，读取速度快，插入与删除速度慢（因为插入与删除时要移动后面的元素），适合于随机访问。

Vector：功能与ArrayList几乎相同，也是以数组实现，添加，删除，读取，设置都是基于线程同步的。

LinkedList：双向链表来实现，删除与插入速度快，读取速度较慢，因为它读取时是从头向尾（如果节点在链的前半部分），或尾向头（如果节点在链的后半部分）查找元素。因此适合于元素的插入与删除操作。

Set：维持它自己的内部排序，随机访问不具有意义。另外元素不可重复，内部是以Map实现的。

HashSet：是最常用的，查询速度最快，因为 内部以HashMap来实现，所以插入元素不能保持插入次序。

LinkedHashSet：继承了HashSet，保持元素的插入次序，因为内部使用LinkedHashMap实现，所以能保持元素插入次序。

TreeSet：基于TreeMap，生成一个总是处于排序状态的set，它实现了SortedSet接口，内部以 TreeMap来实现。

Map：用于保存具有映射关系的数据（key-vlaue），Key不允许重复。

TreeMap：键以某种排序规则排序，内部以red-black（红-黑）树数据结构实现，实现了SortedMap接口。

HashMap:以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来。

Hashtable:也是以哈希表数据结构实现的，解决冲突时与HashMap也一样也是采用了散列链表的形式，不过性能比HashMap要低。

九、比较

1、ArrayList和Vector

同步性:Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的。

数据增长:当需要增长时,Vector默认增长为原来一培，而ArrayList却是原来的一半

2、Collection和Collections

Collection，java.unit下的接口，是一系列单值集合类的父接口，主要有List和Set，提供了基本的一些方法。而Collections是java.unit下的类，是针对集合的一些帮助类，是一系列算法的集合。里面的属性和方法基本都是static的，来实现对各种集合的搜索、排序、线程安全化等操作。

3、 Iterator与ListIterator有什么区别？

Iterator:只能正向遍历集合，适用于获取移除元素。ListIerator：继承Iterator,可以双向列表的遍历，同样支持元素的修改。

4、heap和stack有什么区别。

栈（stack）是一种线形集合，其添加和删除元素的操作应在同一段完成。栈按照后进先出的方式进行处理。

堆（heap）是栈的一个组成元素。

十、总结

关于集合框架的只是很杂，很乱。我也只是根据咱们的学习总结了一些咱们经常需要用到和面试会经常考到的知识点。我希望每一个同学都能抽出那么几分钟看一看这个，来让我们的大脑再加深一下关于集合的印象。本文我没有使用代码进行演示，望大家谅解， 谢谢您的参考！