1 概述
Java Collections 框架中包含了大量的接口及其实现类和操作它们的算法，主要包括列表（List）、集合（Set）、映射（Map），如下：
| 接口 | 实现类 | 数据结构 | 初始容量 | 加载因子 | 扩容 | 线程安全 | 允许 key = null |
| List | ArrayList | 数组 | 10 | 1.5倍+1 | 否 | ||
| LinkedList | 双向链表 | 否 | |||||
| Vector | 数组 | 10 | 2倍 | 是 | |||
| Set | HashSet | hash 表 | 16 | 0.75 | 2倍 | 否 | |
| TreeSet | 红黑树 | 否 | |||||
| Map | HashMap | 数组+链表+红黑树 | 16 | 0.75 | 2倍 | 否 | 是 |
| Hashtable | 数组+链表+红黑树 | 11 | 2倍+1 | 是 | 否 | ||
| ConcurrentHashMap | Node数组+链表+红黑树 | 是 | |||||
| TreeMap | 红黑树 | 否 |
- List
（按插入顺序保存对象，允许元素重复）
（1）ArrayList：数组实现，默认大小为10，扩充1.5倍（向下取整）+1，不够时采用需求值（如需初始为10，需求容量为17，扩容1.5倍+1为16，仍不够，此时将容量设置为17）
（2）LinkedList：双向链表实现
（3）Vector：数组实现，默认大小为10，扩充2倍，线程安全的
- Set
（不允许元素重复）
（1）HashSet: hash表实现，默认大小为16，2倍扩充。
（2）TreeSet: 红黑树实现。
- Map
（存储“键—值”对，键具有唯一性）
（1）HashMap：数组+链表+红黑树实现，hash数组默认大小16，若给定初值，会自动扩充至最近的2的幂次方大小（如指定初值为20，则自动扩充至32），扩充：2倍，允许一条记录key=null
（2）Hashtable：数组+链表+红黑树实现，hash数组默认大小11，若指定初值，会直接使用这个值，扩充：2*old+1，线程安全的，继承自Dictionary类
（3）ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后CAS锁）
（4）TreeMap：红黑树实现
注：HashMap中，当链表长度大于阈值（默认为8）时，才将链表转换为红黑树；HashTable中没有这个限制。
Collection框架
注意：上图是一个简图，部分抽象类和继承关系省略了。
Map框架
注意：上图是一个简图，部分抽象类和继承关系省略了。
2 容器常用方法
java容器存在于 java.util.* 中。
2.1 List
java
代码解读
复制代码
//增删改查方法
public void add(Object element) //增添元素
public void add(int index,Object element) //在指定位置增添元素
public boolean remove(Object o) //删除指定对象
public Object remove(int index) //删除指定位置的元素
public Object set(int index,Object element) //修改指定位置元素的值
public Object get(int index) //获取指定位置元素
public int indexOf(Object o) //获取指定元素的位置
public boolean contains(Object o) //判断指定元素是否存在
//其他常用方法
public int size() //获取容器中元素个数
public Iterator<E> iterator() //获取迭代器
public void clear() //清空元素
ArrayList适合快速查找元素，LinkedList适合频繁地对列表进行增加或删除元素操作，因此LinkedList类可用于实现堆栈和队列，对此LinkedList类中定义了特定的方法，如下：
java
代码解读
复制代码
//模拟栈和队列操作
public void addFirst(Object o) //在链表头增添元素
public void addLast(Object o) //在链表尾增添元素
public Object removeFirst() //删除链表头元素，并返回该元素
public Object removeLast() //删除链表尾元素，并返回该元素
public boolean isEmpty() //判断链表是否为空
public void push(E e) //等价于addFirst()
public E pop() //等价于removeFirst()
public E getFirst() //获取链表首元素
public E getLast() //获取链表尾元素
2.2 Set
java
代码解读
复制代码
//增删查方法
public void add(Object element) //增添元素
public boolean remove(object element) //删除元素
public boolean contains(Object o) //判断元素是否存在
//其他常用方法
public int size() //获取容器中元素个数
public boolean isEmpty() //判断集合是否为空
public Iterator<E> iterator() //获取迭代器
public void clear() //清空元素
2.3 Map
java
代码解读
复制代码
//增删查
public Object put(Object key,Object value) //增添元素
public Object remove(Object key) //删除元素,并返回键对应的值
public Object get(Object key) //获取键对应的值
public boolean containsKey(Object key) //判断指定键是否存在
public boolean containsValue(Object value) //判断指定值是否存在
//获取键、值、元素集合
public Collection values() //获取值集合
public Set KeySet() //获取键集合
public Set entrySet() //获取元素集合
//其他方法
public int size() //获取容器中元素个数
public boolean isEmpty() //判断容器是否为空
public void clear() //清空元素
Map 接口没有提供 iterator() 方法，其子接口 Entry 提供了 iterator() 方法，并且提供了获取键、值的方法，如下：
java
代码解读
复制代码
//Map.Entry接口主要方法
public Iterator<E> iterator() //获取迭代器
public Object getKey() //获取键
public Object getValue() //获取值
//调用案例
Iterator(Entry) iter=map.entrySet().iterator();
while(iter.hasNext()){
Entry entry=iter.next();
int key=(Integer)entry.getKey();
int val=(Integer)entry.getValue();
}
3 其他容器常用方法
3.1 Arrays
java
代码解读
复制代码
public static int binarySearch(Object[] a, Object key) //二分查找（a已排序）
public static boolean equals(Object[] a, Object[] a2) //判断两数组是否完全一致
public static void fill(Object[] a, Object val) //在a中所有位置填充val
public static void fill(Object[] a, int fromIndex, int toIndex, Object val) //在[fromIndex,toIndex)中填充元素val
public static String toString(Object[] a) //将数组a转换为字符串，如"[1, 2, 3]"
public static void sort(Object[] a) //改进的快速排序（升序）
public static void sort(Object[] a, int fromIndex, int toIndex) //对[fromIndex,toIndex)中的元素排序（升序）
public static <T> void sort(T[] a, Comparator<? super T> c) //自定义比较器排序
排序案例：升序排序直接调用 sort() ，降序排序需要实现**比较器（Comparator ）**接口
java
代码解读
复制代码
import java.util.Arrays;
import java.util.Comparator;
public class Sort{
static Integer[] a= {5,8,4,2,9,3,1,6,7};
static String[] s= {"Tom","John","Marry","Katty","Jerry"};
public static void main(String[] args) {
Arrays.sort(a); //1 2 3 4 5 6 7 8 9
Arrays.sort(s); //Jerry John Katty Marry Tom
Arrays.sort(a,new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}); //9 8 7 6 5 4 3 2 1
Arrays.sort(s,new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
}); //Tom Marry Katty John Jerry
}
}
3.2 Collections
3.2.1 Collections 类对 Collection 对象提供的方法
java
代码解读
复制代码
public static Object max(Collection coll) //获取最大值
public static Object min(Collection coll) //获取最小值
3.2.2 Collections 类对List对象提供的方法
java
代码解读
复制代码
public static int binarySearch(List list, Object key) //查找元素
public static void copy(List dest, List src) //将src复制给dest
public static void fill(List list, Object obj) //在list中填充obj
public static void reverse(List list) //列表元素倒置
public static void sort(List list) //升序排序
public static <T> void sort(List<T> list, Comparator<? super T> c) //自定义比较器排序
排序案例：升序排序直接调用 sort() ，降序排序需要实现**比较器（Comparator ）**接口
java
代码解读
复制代码
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Sort{
static int[] a= {5,8,4,2,9,3,1,6,7};
static String[] s= {"Tom","John","Marry","Katty","Jerry"};
static List list1=new ArrayList<Integer>();
static List list2=new ArrayList<String>();
public static void main(String[] args) {
for(int i=0;i<a.length;i++) {
list1.add(a[i]);
}
for(int i=0;i<s.length;i++) {
list2.add(s[i]);
}
Collections.sort(list1); //[1, 2, 3, 4, 5, 6, 7, 8, 9]
Collections.sort(list2); //[Jerry, John, Katty, Marry, Tom]
Collections.sort(list1,new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}); //[9, 8, 7, 6, 5, 4, 3, 2, 1]
Collections.sort(list2,new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
}); //[Tom, Marry, Katty, John, Jerry]
}
}
3.2.3 Collections 类提供的集合同步处理方法
java
代码解读
复制代码
public static Collection synchronizedCollection(Collection c) //Collection对象同步
public static List synchronizedList(List list) //List对象同步
public static Set synchronizedSet(Set s) //Set对象同步
public static Map synchronizedMap(Map m) //Map对象同步
案例：
java
代码解读
复制代码
List list=Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator<E> iter=list.iterator();
while(iter.hasNext()) {
foo(iter.next());
}
}
