java容器类—概述

大家好，又见面了，我是全栈君。

1、容器类关系图

java容器类---概述

虚线框表示接口。

实线框表示实体类。

粗线框表示最经常使用的实体类。
点线的箭头表示实现了这个接口。
实线箭头表示类能够制造箭头所指的那个类的对象。

Java集合工具包位于Java.util包下。包括了非常多经常使用的数据结构，如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致能够分为例如以下五个部分：List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具类（Arrays、Collections）。

从上图中能够看出，集合类主要分为两大类：Collection和Map。

Collection是List、Set等集合高度抽象出来的接口，它包括了这些集合的基本操作，它主要又分为两大部分：List和Set。

List接口通常表示一个列表（数组、队列、链表、栈等），当中的元素能够反复。经常使用实现类为ArrayList和LinkedList，另外还有不经常使用的Vector。另外。LinkedList还是实现了Queue接口，因此也能够作为队列使用。

Set接口通常表示一个集合，当中的元素不同意反复（通过hashcode和equals函数保证），经常使用实现类有HashSet和TreeSet。HashSet是通过Map中的HashMap实现的，而TreeSet是通过Map中的TreeMap实现的。另外，TreeSet还实现了SortedSet接口，因此是有序的集合（集合中的元素要实现Comparable接口，并覆写Compartor函数才行）。

我们看到。抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口，这就是在Java集合框架中用的非常多的适配器设计模式，用这些抽象类去实现接口，在抽象类中实现接口中的若干或所有方法，这样以下的一些类仅仅需直接继承该抽象类，并实现自己须要的方法就可以，而不用实现接口中的所有抽象方法。

Map是一个映射接口，当中的每一个元素都是一个key-value键值对。相同抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数，TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现。另外，不经常使用的HashTable直接实现了Map接口。它和Vector都是JDK1.0就引入的集合类。

Iterator是遍历集合的迭代器（不能遍历Map，仅仅用来遍历Collection）。Collection的实现类都实现了iterator()函数。它返回一个Iterator对象。用来遍历集合，ListIterator则专门用来遍历List。而Enumeration则是JDK1.0时引入的，作用与Iterator同样。但它的功能比Iterator要少。它仅仅能再Hashtable、Vector和Stack中使用。

Arrays和Collections是用来操作数组、集合的两个工具类。比如在ArrayList和Vector中大量调用了Arrays.Copyof()方法。而Collections中有非常多静态方法能够返回各集合类的synchronized版本号，即线程安全的版本号。当然了。假设要用线程安全的结合类，首选Concurrent并发包下的相应的集合类。

2、容器类持有对象方式

1 Collection：仅仅同意每一个位置上放一个对象。它包含“以一定顺序持有一组对象”的List。以及“仅仅能同意加入不反复对象”的Set。

你能够用add()方法向Collection对象中加元素。

2 Map：一组以“键－值”（key－value）的形式出现的pair，Map也不接受反复的key值。

你能够用put()方法往Map里面加元素。

Collection 和 Collections的差别：
Collections是个java.util下的类，它包括有各种有关集合操作的静态方法，实现对各种集合的搜索、排序、线程安全化等操作。
Collection是个java.util下的接口。它是各种集合结构的父接口。继承自它的接口主要有Set 和List.

3、Iterator接口

发现一个特点，上述全部的集合类。都实现了Iterator接口，

这是一个用于遍历集合中元素的接口，主要包括hashNext(),next(),remove()三种方法。它的一个子接口ListIterator在它的基础上又加入了三种方法，各自是add(),previous(),hasPrevious()。也就是说假设实现Iterator接口，那么在遍历集合中元素的时候，仅仅能往后遍历，被遍历后的元素不会在遍历到，通常无序集合实现的都是这个接口。比方HashSet。HashMap；

而那些元素有序的集合，实现的一般都是ListIterator接口，实现这个接口的集合能够双向遍历，既能够通过next()訪问下一个元素，又能够通过previous()訪问前一个元素，比方ArrayList。

抽象类：
另一个特点就是抽象类的使用。

假设要自己实现一个集合类。去实现那些抽象的接口会非常麻烦，工作量非常大。

这个时候就能够使用抽象类，这些抽象类中给我们提供了很多现成的实现。我们仅仅须要依据自己的需求重写一些方法或者加入一些方法就能够实现自己须要的集合类。工作流昂大大减少。

4、Set接口

Set是一种不包括反复的元素的Collection，即随意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
非常明显，Set的构造函数有一个约束条件，传入的Collection參数不能包括反复的元素。
请注意：必须小心操作可变对象（Mutable Object）。假设一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Set推断两个对象同样不是使用==运算符，而是依据equals方法。也就是说。仅仅要两个对象用equals方法比較返回true，Set就不会接受这两个对象。

4.1 HashSet

HashSet：是Set接口的一个子类。基本的特点是：里面不能存放反复元素，并且採用散列的存储方法，所以没有顺序。

这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致。

HashSet有下面特点：
不能保证元素的排列顺序，顺序有可能发生变化
不是同步的
集合元素能够是null,但仅仅能放入一个null

当向HashSet结合中存入一个元素时。HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后依据 hashCode值来决定该对象在HashSet中存储位置。

简单的说，HashSet集合推断两个元素相等的标准是两个对象通过equals方法比較相等。而且两个对象的hashCode()方法返回值相等
注意，假设要把一个对象放入HashSet中，重写该对象相应类的equals方法，也应该重写其hashCode()方法。

其规则是假设两个对象通过equals方法比較返回true时，其hashCode也应该同样。另外，对象中用作equals比較标准的属性，都应该用来计算 hashCode的值。

4.2 LinkedHashSet
LinkedHashSet集合相同是依据元素的hashCode值来决定元素的存储位置。可是它同一时候使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的加入顺序訪问集合的元素。

LinkedHashSet在迭代訪问Set中的所有元素时。性能比HashSet好，可是插入时性能略微逊色于HashSet。

4.3 TreeSet类
TreeSet是SortedSet接口的唯一实现类。TreeSet能够确保集合元素处于排序状态。

TreeSet支持两种排序方式，自然排序和定制排序，当中自然排序为默认的排序方式。

向TreeSet中增加的应该是同一个类的对象。
TreeSet推断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比較没有返回0

自然排序:
自然排序使用要排序元素的CompareTo（Object obj）方法来比較元素之间大小关系，然后将元素依照升序排列。
Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就能够比較大小。
obj1.compareTo(obj2)方法假设返回0，则说明被比較的两个对象相等，假设返回一个正数。则表明obj1大于obj2，假设是负数，则表明obj1小于obj2。
假设我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0

定制排序
自然排序是依据集合元素的大小。以升序排列。假设要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法

5、List接口

List是有序的Collection。使用此接口可以精确的控制每一个元素插入的位置。用户可以使用索引（元素在List中的位置，类似于数组下标）来訪问List中的元素。这类似于Java的数组。List同意有同样的元素。

除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个 ListIterator接口。和标准的Iterator接口相比。ListIterator多了一些add()之类的方法，同意加入。删除，设定元素。还能向前或向后遍历。

实现List接口的经常使用类有LinkedList，ArrayList，Vector和Stack。

5.1 LinkedList类
LinkedList实现了List接口。同意null元素。

此外LinkedList提供额外的get，remove。insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意：LinkedList没有同步方法。假设多个线程同一时候訪问一个List，则必须自己实现訪问同步。

一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(…));

5.2 ArrayList类
ArrayList实现了可变大小的数组。它同意全部元素。包含null。

ArrayList没有同步。
size，isEmpty，get，set方法执行时间为常数。可是add方法开销为分摊的常数。加入n个元素须要O(n)的时间。

其它的方法执行时间为线性。
每一个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。

这个容量可随着不断加入新元素而自己主动添加。可是增长算法并未定义。当须要插入大量元素时，在插入前能够调用ensureCapacity方法来添加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

5.3 Vector类
Vector很类似ArrayList，可是Vector是同步的。

由Vector创建的Iterator，尽管和ArrayList创建的Iterator是同一接口。可是，由于Vector是同步的。当一个Iterator被创建并且正在被使用，还有一个线程改变了Vector的状态（比如，加入或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException。因此必须捕获该异常。

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

ArrayList和Vector的差别：
一.同步性:Vector是线程安全的。也就是说是同步的。而ArrayList是线程序不安全的，不是同步的。由Vector创建的Iterator，尽管和ArrayList创建的Iterator是同一接口。可是，由于Vector是同步的，当一个Iterator被创建并且正在被使用，还有一个线程改变了Vector的状态（比如，加入或删除了一些元素）。这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

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

Array与Arrays:
Array就是数组。也就是长度固定的容器。一但创建了这个对象就不能改变其大小(capacity)。
Arrays是Array的工具类，其静态方法定义了对Array的各种操作:

5、Map接口
　　请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包括同样的key。每一个key仅仅能映射一个 value。Map接口提供3种集合的视图。Map的内容能够被当作一组key集合，一组value集合，或者一组key-value映射。

5.1 Hashtable类
Hashtable继承Map接口，实现一个key-value映射的哈希表。不论什么非空（non-null）的对象都可作为key或者value。Hashtable是同步的。
加入数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。

使用Hashtable的简单示比例如以下，将1，2，3放到Hashtable中，他们的key各自是”one”，”two”，”three”：　　

 Hashtable numbers = new Hashtable();
　　　　numbers.put(“one”, new Integer(1));
　　　　numbers.put(“two”, new Integer(2));
　　　　numbers.put(“three”, new Integer(3));</span>

要取出一个数，比方2，用对应的key：

　　　　Integer n = (Integer)numbers.get(“two”);
　　　　System.out.println(“two = ” + n);

因为作为key的对象将通过计算其散列函数来确定与之相应的value的位置，因此不论什么作为key的对象都必须实现hashCode和equals方法。

hashCode和equals方法继承自根类Object，假设你用自己定义的类当作key的话。要相当小心，依照散列函数的定义，假设两个对象同样，即obj1.equals(obj2)=true，则它们的hashCode必须同样。但假设两个对象不同。则它们的hashCode不一定不同，假设两个不同对象的hashCode同样，这样的现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。

　　假设同样的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这样的问题，仅仅须要牢记一条：要同一时候复写equals方法和hashCode方法，而不要仅仅写当中一个。

5、2 HashMap类
　　HashMap和Hashtable类似，不同之处在于HashMap是非同步的。而且同意null。即null value和null key。可是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，假设迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高。或者load factor过低。

5.3 WeakHashMap类
　　WeakHashMap是一种改进的HashMap。它对key实行“弱引用”，假设一个key不再被外部所引用，那么该key能够被GC回收。

HashMap和Hashtable的差别:
HashTable的应用很广泛。HashMap是Hashtable的轻量级实现（非线程安全的实现）。HashMap是新框架中用来取代HashTable的类。也就是说建议使用HashMap。不要使用HashTable。
1.HashTable的方法是同步的。HashMap未经同步，所以在多线程场合要手动同步HashMap这个差别就像Vector和ArrayList一样。

2.HashTable不同意null值(key和value都不能够),HashMap同意null值(key和value都能够)。

3.HashMap把Hashtable的contains方法去掉了。改成containsvalue和containsKey。由于contains方法easy让人引起误解。
4.HashTable使用Enumeration，HashMap使用Iterator。

总结
假设涉及到堆栈，队列等操作。应该考虑用List，对于须要高速插入，删除元素，应该使用LinkedList，假设须要高速随机訪问元素。应该使用ArrayList。
假设程序在单线程环境中，或者訪问只在一个线程中进行，考虑非同步的类，其效率较高。假设多个线程可能同一时候操作一个类，应该使用同步的类。

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
尽量返回接口而非实际的类型。如返回List而非ArrayList，这样假设以后须要将ArrayList换成LinkedList时。client代码不用改变。

这就是针对抽象编程。