Java的数据结构

线性表、链表、哈希表是常用数据结构。做 Java 开发时，JDK 已经在 java.util 里准备好了一套类。下面按接口把各自的职责和使用方式理清。

记住两棵树：Collection（单列）和 Map（键值）。SDK 不提供直接实现 Collection 的类，实现都落在 List、Set 这些子接口上。

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set

Map
├Hashtable
├HashMap
└WeakHashMap

一、Collection 接口

Collection 是最基本的集合接口，代表一组 Object，也就是元素。有的允许重复，有的不允许；有的能排序，有的不能。

所有实现类都要提供两个标准构造：无参构造创建空集合；带一个 Collection 参数的构造，复制出一份相同元素的新集合。

不论实际类型是什么，都支持 iterator()，返回迭代子，逐一访问元素：

Iterator it = collection.iterator(); // 获得一个迭代子

while(it.hasNext()) {

Object obj = it.next(); // 得到下一个元素

}

由 Collection 派生的两个接口是 List 和 Set。主要方法：

boolean add(Object o)添加对象到集合

boolean remove(Object o)删除指定的对象

int size()返回当前集合中元素的数量

boolean contains(Object o)查找集合中是否有指定的对象

boolean isEmpty()判断集合是否为空

Iterator iterator()返回一个迭代器

boolean containsAll(Collection c)查找集合中是否有集合c中的元素

boolean addAll(Collection c)将集合c中所有的元素添加给该集合

void clear()删除集合中所有元素

void removeAll(Collection c)从集合中删除c集合中也有的元素

void retainAll(Collection c)从集合中删除集合c中不包含的元素

二、List 接口

List 是有序 Collection，能精确控制每个元素的插入位置，可用索引（类似数组下标）访问，并允许重复元素。

除了 iterator()，List 还提供 listIterator()。ListIterator 比标准 Iterator 多了 add、删除、设定，以及向前/向后遍历。

常用实现：LinkedList、ArrayList、Vector、Stack。主要方法：

void add(int index,Object element)在指定位置上添加一个对象

boolean addAll(int index,Collection c)将集合c的元素添加到指定的位置

Object get(int index)返回List中指定位置的元素

int indexOf(Object o)返回第一个出现元素o的位置.

Object removeint(int index)删除指定位置的元素

Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素

LinkedList

允许 null。额外提供在首尾 get、remove、insert 的方法，因此可当堆栈、队列或双端队列。没有同步方法。多线程同时访问必须自己同步，例如：

List list = Collections.synchronizedList(new LinkedList(...));

ArrayList

可变大小数组，允许所有元素（含 null），不同步。size、isEmpty、get、set 是常数时间；add 是摊还常数，加 n 个元素要 O(n)；其余多为线性。

每个实例有容量（底层数组大小），加元素时自动增长，增长算法未规定。插入大量元素前可调 ensureCapacity 提前扩容。和 LinkedList 一样非同步。主要方法：

Boolean add(Object o)将指定元素添加到列表的末尾

Boolean add(int index,Object element)在列表中指定位置加入指定元素

Boolean addAll(Collection c)将指定集合添加到列表末尾

Boolean addAll(int index,Collection c)在列表中指定位置加入指定集合

Boolean clear()删除列表中所有元素

Boolean clone()返回该列表实例的一个拷贝

Boolean contains(Object o)判断列表中是否包含元素

Boolean ensureCapacity(int m)增加列表的容量,如果必须,该列表能够容纳m个元素

Object get(int index)返回列表中指定位置的元素

Int indexOf(Object elem)在列表中查找指定元素的下标

Int size()返回当前列表的元素个数

Vector 与 Stack

Vector 很像 ArrayList，但是同步的。Iterator 接口相同，但 Vector 被另一线程改过状态后，再调 Iterator 会抛 ConcurrentModificationException，必须捕获。

Stack 继承 Vector，后进先出。额外五个方法：push / pop，peek 看栈顶，empty 测空，search 查位置。刚创建时是空栈。

三、Set 接口

Set 不含重复元素：任意 e1、e2 都有 e1.equals(e2)==false，最多一个 null。构造时传入的 Collection 也不能带重复元素。

可变对象要小心：若 Set 里某个元素改了自身状态，导致 equals 变成 true，集合契约就会被破坏。

四、Map 接口

Map 没有继承 Collection。它提供 key 到 value 的映射：不能有相同 key，每个 key 只映射一个 value。三种视图：一组 key、一组 value、一组 key-value 映射。主要方法：

boolean equals(Object o)比较对象

boolean remove(Object o)删除一个对象

put(Object key,Object value)添加key和value

Hashtable

实现 key-value 哈希表，key、value 都不能是 null。put / get 基本是常数时间。用 initial capacity 和 load factor 调性能，默认负载因子 0.75 较均衡；增大可省空间但查找变慢。

把 1、2、3 放进去，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));

按 key 取出 2：

Integer n = (Integer)numbers.get(“two”);

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

作为 key 的对象必须实现 hashCode 和 equals。两对象 equals 为 true 则 hashCode 必须相同；不同对象 hashCode 可以相同（冲突），冲突会加大开销。若相同对象却有不同 hashCode，get 会拿到 null。只记一条：equals 和 hashCode 要一起覆写。Hashtable 是同步的。

HashMap 与 WeakHashMap

HashMap 类似 Hashtable，但非同步，且允许 null key 和 null value。当把它当 Collection 看（values()）时，迭代开销和容量成正比：迭代很重要时，别把初始容量设太高，也别把 load factor 设太低。

WeakHashMap 是改进的 HashMap，对 key 使用弱引用：外部不再引用该 key 时，GC 可以回收它。

五、怎么选

尽量返回接口而不是实现类，例如返回 List 而不是 ArrayList，以后换成 LinkedList 时调用方不用改——这就是针对抽象编程。

一句话总结：单列走 Collection（List 有序可重复，Set 去重），键值走 Map；按访问模式选实现，对外只暴露接口。