Java 容器(list, set, map)

java容器类库的简化图：

(虚线框表示接口，实线框表示普通的类，

空心箭头表示特定的类实现了接口，实心箭头表示某个类可以生成箭头所指的类对象)

继承Collection的主要有Set 和 List.

List:

ArrayList 内部实现是用数组, 随机访问速度快，删除或插入元素速度慢。

LinkedList 内部实现是用链表, 随机访问速度慢，删除和插入元素相对较快。

平时最佳的做法可能是将ArrayList作为默认首选，只有你需要使用额外的功能，或者因为经常从表中插入或删除元素导致程序性能变差的时候，才去选择LinkedList。

Vector和Stack是过去遗留下来的类，目的只是为了支持老程序，应该在编写程序时尽量避免使用它们。

Set：

Hash

HashSet: 为快速查找而设计,可以认为是基于哈希表的实现。存入HashSet的元素必须定义hashCode().

LinkedHashSet: 具有HashSet的查询速度且内部使用链表维护元素的顺序（按插入的顺序或最近最少使用顺序）

Tree

TreeSet：保持次序的Set，底层为树结构（红黑树）。使用它可以从Set提取有序的序列。元素必须实现Comparable接口或者在构造TreeSet时传入Comparator参数。

 1 class Stone {
 2     private int volume;
 3 
 4     public Stone(int volume) {
 5         this.volume = volume;
 6     }
 7 
 8     public int getVolume() {
 9         return volume;
10     }
11 
12     //...........省略..........//
13 }
14 
15 class Stick implements Comparable{
16     private int length;
17 
18     public Stick(int length) {
19         this.length = length;
20     }
21 
22     public int getLength() {
23         return length;
24     }
25 
26     @Override
27     public int compareTo(Object o) {
28         Stick st = (Stick)o;
29         return this.getLength() - st.getLength();
30     }
31 
32     //...........省略..........//
33 }
34 
35 public class MyComparator implements Comparator<Stone>{
36 
37     @Override
38     public int compare(Stone st1, Stone st2) {
39         return st1.getVolume() - st2.getVolume();
40     }
41 
42     public static void main(String[] args) {
43         new TreeSet<Stone>(new MyComparator()); //传入Comparator
44 
45         new TreeSet<Stick>(); //Stick实现了Comparable
46     }
47 }

View Code

不管是散列存储还是树形存储，元素都必须实现equals()方法。虽然只有当时被放入HashSet或LinkedHashSet是hashCode()才是必须的，但是，对于良好的编程风格，应该在覆盖equals()方法的同时也覆盖hashCode()方法。

equals()方法必须满足5个条件:

1. 自反性。对任意x，    x.equals(x)一定为true

2. 对称性。对任意x、y，     如果y.equals(x)为true, x.equals(y)也为true

3. 传递性。对任意x、y、z，如果x.equals(y), y.equals(z)都为true, x.equals(z)也应该为true

4. 一致性。对任意x、y，   如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，其返回结果都应该一致。

5. 对于任何不是null的x,     x.equals(null)一定为false

hashCode()的编写建议(Effective Java）:

1. 给result(int型)一个非零的初始值

2. 为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c

域类型

计算

boolean c = ( f ? 0 : 1)

byte, char, short, 或 int
c = (int)f

long c = (int)(f ^ (f>>>32))

float c = Float.floatToIntBits(f);

double
long l = Double.doubleToLongBits(f);
c = (int)(1 ^ (l>>>32))

Object
c = f.hashCode( )

Array 对数组中的每个元素应用上述规则

3. 合并计算得到的散列码 result = 37 * result + c

4. 返回 result

5. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列码

SortedSet（接口）保证元素处于排序状态（按对象的比较函数对元素排序）,主要方法有：

Comparator comparator() 返回当前Set使用的Comparator,如果返回空，表示以自然排序（即按元素实现的Comparable中

compareTo()方法排序）。

Object first() 返回容器的第一个元素

Object last() 返回容器的最后一个元素

SortedSet subSet(fromElement, toElement) 生成此Set的子集，范围从fromElement(包含)到toElement(不包含)

SortedSet headSet(toElement) 生成此Set的子集，由小于toElement的元素组成

SortedSet tailSet(fromElement) 生成此Set的子集，有大于等于fromElement的元素组成

TreeSet实现SortedSet，包括SortedSet的方法。

可选操作

在Collection接口中执行各种添加和移除的方法都是可选的。也就是说实现Collection接口的类并不需要为这些方法提供有意义的功能实现。这违反了面向对象设计中的规则（无论你选择如何实现接口，应该保证能够向该接口发送这些消息）。

可选操作声明调用某些方法将不会执行有意义的行为，相反，它们会抛出异常。

可选操作是逻辑上的，在实现接口时，还是需要覆盖接口所谓的可选方法，只不过你不一定要提供有意义的实现，如果不支持该可选方法，可以在该方法出抛出UnsupportedOperationException。

那么为什么需要将方法定义为可选呢？

这样可以防止设计中出现接口过多的情况。

比如现在有下面三种需求（当然可以有更多不同的需求）

不能修改集合内容的容器，

只能添加元素的容器，

只能删除元素的容器。

那么现在就需要为上面三种需求各定义一种接口，显然这样比起现在的Collection，需要定义更多的接口。这样会导致接口过多，使整个容器类库更加复杂。

注意：UnsupportedOperationException必须是一个罕见的异常。即对大多数类来说，所有操作都应该可以工作，只有在特列中才会有未获得支持的操作。

快速报错（fail-fast）

java容器有一种保护机制，能够防止多个进程同时修改同一容器的内容。

如果在迭代遍历某个容器的过程中，另一个进程介入其中，并且插入、删除或修改此容器内的某个对象，那么就容易出现问题。

java容器类类库采用fail-fast机制。他会探查容器上除了当前线程所进行的操作之外的所有变化，一旦发现其它进程修改了容器，就会立刻抛出ConcurrentModificationException异常。

示例：

 1 import java.util.*;
 2 public class FailFast {
 3     public static void main(String[] args) {
 4         Collection<String> c = new ArrayList<String>();
 5         Iterator<String> it = c.iterator();
 6         c.add("An object");
 7         try {
 8             String s = it.next();
 9         } catch(ConcurrentModificationException e) {
10             System.out.println(e);
11         }
12     }
13 } 
14 /* Output:
15 java.util.ConcurrentModificationException
16 *///:~

View Code

Map

HashMap 基于散列表的实现（它取代了HashTable, HashTable是过时的类）。

LinkedHashMap 类似与HashMap，但是迭代遍历时，取得“键值对”的顺序是其插入的顺序

或最近最少使用的顺序(如果在构造LiskedHashMap传入参数accessOrder=true)。

比HashMap慢一点，但是在迭代访问时更快，因为它使用链表维护内部的次序。

TreeMap 基于红黑树的实现。查看key 或 key-value是，它们会被排序（次序由Comparator或Comparable决定）

博客园(FOREVER_ENJOY)：http://www.cnblogs.com/zyx1314/p/5331282.html

本文版权归作者所有；欢迎转载！请注明文章作者和原文连接

域类型	计算
boolean	c = ( f ? 0 : 1)
byte, char, short, 或 int	c = (int)f
long	c = (int)(f ^ (f>>>32))
float	c = Float.floatToIntBits(f);
double	long l = Double.doubleToLongBits(f); c = (int)(1 ^ (l>>>32))
Object	c = f.hashCode( )
Array	对数组中的每个元素应用上述规则