基于Java回顾之集合的总结概述
java中的集合主要集中在2部分，一部分是java.util包中，一部分是java.util.concurrent中，后者是在前者的基础上，定义了一些实现了同步功能的集合。
这篇文章主要关注java.util下的各种集合对象。java中的集合对象可以粗略的分为3类：list、set和map。对应的uml图如下（包括了java.util下大部分的集合对象）：
collection概述
java集合中的list和set都从collection出来，它是一个学习集合很不错的入口，它包含了集合中通常需要有的操作：
添加元素：add/addall
清空集合：clear
删除元素：remove/removeall
判断集合中是否包含某元素：contains/containsall
判断集合是否为空：isempty
计算集合中元素的个数：size
将集合转换为数组：toarray
获取迭代器：iterator
我们来看一个简单的例子，下面的代码会返回一个集合，集合中的元素是随机生成的整数：
private static collection initcollection()
{
collection<integer> collection = new arraylist<integer>();
random r = new random();
for (int i = 0 ; i < 5; i++)
{
collection.add(new integer(r.nextint(100)));
}
return collection;
}
在对集合进行操作的过程中，遍历是一个经常使用的操作，我们可以使用两种方式对集合进行遍历：
1） 使用迭代器对集合进行遍历。正如上面描述collection接口时所说，所有集合都会有一个迭代器，我们可以用它来遍历集合。
private static void accesscollectionbyiterator(collection<integer> collection)
{
iterator<integer> iterator = collection.iterator();
system.out.println("the value in the list:");
while(iterator.hasnext())
{
system.out.println(iterator.next());
}
}
2）使用foreach遍历集合。
private static void accesscollectionbyfor(collection<integer> collection)
{
system.out.println("the value in the list:");
for(integer value : collection)
{
system.out.println(value);
}
}
list
java中的list是对数组的有效扩展，它是这样一种结构，如果不使用泛型，它可以容纳任何类型的元素，如果使用泛型，那么它只能容纳泛型指定的类型的元素。和数组相比，list的容量是可以动态扩展的。
list中的元素是可以重复的，里面的元素是“有序”的，这里的“有序”，并不是排序的意思，而是说我们可以对某个元素在集合中的位置进行指定。
list中常用的集合对象包括：arraylist、vector和linkedlist，其中前两者是基于数组来进行存储，后者是基于链表进行存储。其中vector是线程安全的，其余两个不是线程安全的。
list中是可以包括null的，即使是使用了泛型。
arraylist可能是我们平时用到的最多的集合对象了，在上述的示例代码中，我们也是使用它来实例化一个collection对象，在此不再赘述。
vector
vector的示例如下，首先我们看如何生成和输出vector：
private static void vectortest1()
{
list<integer> list = new vector<integer>();
for (int i = 0 ; i < 5; i++)
{
list.add(new integer(100));
}
list.add(null);
system.out.println("size of vector is " + list.size());
system.out.println(list);
}
它的元素中，既包括了重复元素，也包括了null，输出结果如下：
size of vector is 6
[100, 100, 100, 100, 100, null]
下面的示例，演示了vector中的一些常用方法：
private static void vectortest2()
{
vector<integer> list = new vector<integer>();
random r = new random();
for (int i = 0 ; i < 10; i++)
{
list.add(new integer(r.nextint(100)));
}
system.out.println("size of vector is " + list.size());
system.out.println(list);
system.out.println(list.firstelement());
system.out.println(list.lastelement());
system.out.println(list.sublist(3, 8));
list<integer> temp = new arraylist<integer>();
for(int i = 4; i < 7; i++)
{
temp.add(list.get(i));
}
list.retainall(temp);
system.out.println("size of vector is " + list.size());
system.out.println(list);
}
它的输出结果如下：
size of vector is 10
[39, 41, 20, 9, 29, 32, 54, 12, 94, 82]
[9, 29, 32, 54, 12]
size of vector is 3
[29, 32, 54]
linkedlist
linkedlist使用链表来存储数据，它的示例代码如下：
linkedlist示例
private static void linkedlisttest1()
{
linkedlist<integer> list = new linkedlist<integer>();
random r = new random();
for (int i = 0 ; i < 10; i++)
{
list.add(new integer(r.nextint(100)));
}
list.add(null);
system.out.println("size of linked list is " + list.size());
system.out.println(list);
system.out.println(list.element());
system.out.println(list.getfirst());
system.out.println(list.getlast());
system.out.println(list.peek());
system.out.println(list.peekfirst());
system.out.println(list.peeklast());
system.out.println(list.poll());
system.out.println(list.pollfirst());
system.out.println(list.polllast());
system.out.println(list.pop());
list.push(new integer(100));
system.out.println("size of linked list is " + list.size());
system.out.println(list);
}
这里列出了linkedlist常用的各个方法，从方法名可以看出，linkedlist也可以用来实现栈和队列。
输出结果如下：
size of linked list is 11
[17, 21, 5, 84, 19, 57, 68, 26, 27, 47, null]
null
null
null
size of linked list is 8
[100, 84, 19, 57, 68, 26, 27, 47]
set
set 和list类似，都是用来存储单个元素，单个元素的数量不确定。但set不能包含重复元素，如果向set中插入两个相同元素，那么后一个元素不会被插入。
set可以大致分为两类：不排序set和排序set，不排序set包括hashset和linkedhashset，排序set主要指treeset。其中hashset和linkedhashset可以包含null。
hashset
hashset是由hash表支持的一种集合，它不是线程安全的。
我们来看下面的示例，它和vector的第一个示例基本上是相同的：
private static void hashsettest1()
{
set<integer> set = new hashset<integer>();
for (int i = 0; i < 3; i++)
{
set.add(new integer(100));
}
set.add(null);
system.out.println("size of set is " + set.size());
system.out.println(set);
}
这里，hashset中既包含了重复元素，又包含了null，和vector不同，这里的输出结果如下：
size of set is 2
[null, 100]
对于hashset是如何判断两个元素是否是重复的，我们可以深入考察一下。object中也定义了equals方法，对于hashset中的元素，它是根据equals方法来判断元素是否相等的，为了证明这一点，我们可以定义个“不正常”的类型：
定义myinteger对象
class myinteger
{
private integer value;
public myinteger(integer value)
{
this.value = value;
}
public string tostring()
{
return string.valueof(value);
}
public int hashcode()
{
return 1;
}
public boolean equals(object obj)
{
return true;
}
}
可以看到，对于myinteger来说，对于任意两个实例，我们都认为它是不相等的。
下面是对应的测试方法：
private static void hashsettest2()
{
set<myinteger> set = new hashset<myinteger>();
for (int i = 0; i < 3; i++)
{
set.add(new myinteger(100));
}
system.out.println("size of set is " + set.size());
system.out.println(set);
}
它的输出结果如下：
size of set is 3
[100, 100, 100]
可以看到，现在hashset里有“重复”元素了，但对于myinteger来说，它们不是“相同”的。
treeset
treeset是支持排序的一种set，它的父接口是sortedset。
我们首先来看一下treeset都有哪些基本操作：
private static void treesettest1()
{
treeset<integer> set = new treeset<integer>();
random r = new random();
for (int i = 0 ; i < 5; i++)
{
set.add(new integer(r.nextint(100)));
}
system.out.println(set);
system.out.println(set.first());
system.out.println(set.last());
system.out.println(set.descendingset());
system.out.println(set.headset(new integer(50)));
system.out.println(set.tailset(new integer(50)));
system.out.println(set.subset(30, 60));
system.out.println(set.floor(50));
system.out.println(set.ceiling(50));
}
它的输出结果如下：
[8, 42, 48, 49, 53]
[53, 49, 48, 42, 8]
[8, 42, 48, 49]
[53]
[42, 48, 49, 53]
treeset中的元素，一般都实现了comparable接口，默认情况下，对于integer来说，sortedlist是采用升序来存储的，我们也可以自定义compare方式，例如以降序的方式来存储。
下面，我们首先重新定义integer：
定义myinteger2对象
class myinteger2 implements comparable
{
public int value;
public myinteger2(int value)
{
this.value = value;
}
public int compareto(object arg0)
{
myinteger2 temp = (myinteger2)arg0;
if (temp == null) return -1;
if (temp.value > this.value)
{
return 1;
}
else if (temp.value < this.value)
{
return -1;
}
return 0;
}
public boolean equals(object obj)
{
return compareto(obj) == 0;
}
public string tostring()
{
return string.valueof(value);
}
}
下面是测试代码：
private static void treesettest2()
{
treeset<integer> set1 = new treeset<integer>();
treeset<myinteger2> set2 = new treeset<myinteger2>();
random r = new random();
for (int i = 0 ; i < 5; i++)
{
int value = r.nextint(100);
set1.add(new integer(value));
set2.add(new myinteger2(value));
}
system.out.println("set1 as below:");
system.out.println(set1);
system.out.println("set2 as below:");
system.out.println(set2);
}
代码的运行结果如我们所预期的那样，如下所示：
set1 as below:
[13, 41, 42, 45, 61]
set2 as below:
[61, 45, 42, 41, 13]
map
map中存储的是“键值对”，和set类似，java中的map也有两种：排序的和不排序的，不排序的包括hashmap、hashtable和linkedhashmap，排序的包括treemap。
非排序map
hashmap和hashtable都是采取hash表的方式进行存储，hashmap不是线程安全的，hashtable是线程安全的，我们可以把hashmap看做是“简化”版的hashtable。
hashmap是可以存储null的，无论是对key还是对value。hashtable是不可以存储null的。
无论hashmap还是hashtable，我们观察它的构造函数，就会发现它可以有两个参数：initialcapacity和loadfactor，默认情况下，initialcapacity等于16，loadfactor等于0.75。这和hash表中可以存放的元素数目有关系，当元素数目超过initialcapacity*loadfactor时，会触发rehash方法，对hash表进行扩容。如果我们需要向其中插入过多元素，需要适当调整这两个参数。
我们首先来看hashmap的示例：
private static void hashmaptest1()
{
map<integer,string> map = new hashmap<integer, string>();
map.put(new integer(1), "a");
map.put(new integer(2), "b");
map.put(new integer(3), "c");
system.out.println(map);
system.out.println(map.entryset());
system.out.println(map.keyset());
system.out.println(map.values());
}
这会输出hashmap里的元素信息，如下所示。
{1=a, 2=b, 3=c}
[1=a, 2=b, 3=c]
[1, 2, 3]
[a, b, c]
下面的示例是对null的演示：
private static void hashmaptest2()
{
map<integer,string> map = new hashmap<integer, string>();
map.put(null, null);
map.put(null, null);
map.put(new integer(4), null);
map.put(new integer(5), null);
system.out.println(map);
system.out.println(map.entryset());
system.out.println(map.keyset());
system.out.println(map.values());
}
执行结果如下：
{null=null, 4=null, 5=null}
[null=null, 4=null, 5=null]
[null, 4, 5]
[null, null, null]
接下来我们演示hashtable，和上述两个示例基本上完全一样（代码不再展开）：
hashtable示例
private static void hashtabletest1()
{
map<integer,string> table = new hashtable<integer, string>();
table.put(new integer(1), "a");
table.put(new integer(2), "b");
table.put(new integer(3), "c");
system.out.println(table);
system.out.println(table.entryset());
system.out.println(table.keyset());
system.out.println(table.values());
}
private static void hashtabletest2()
{
map<integer,string> table = new hashtable<integer, string>();
table.put(null, null);
table.put(null, null);
table.put(new integer(4), null);
table.put(new integer(5), null);
system.out.println(table);
system.out.println(table.entryset());
system.out.println(table.keyset());
system.out.println(table.values());
}
执行结果如下：
{3=c, 2=b, 1=a}
[3=c, 2=b, 1=a]
[3, 2, 1]
[c, b, a]
exception in thread "main" java.lang.nullpointerexception
at java.util.hashtable.put(unknown source)
at sample.collections.mapsample.hashtabletest2(mapsample.java:61)
at sample.collections.mapsample.main(mapsample.java:11)
可以很清楚的看到，当我们试图将null插入到hashtable中时，报出了空指针异常。
排序map
排序map主要是指treemap，它对元素增、删、查操作时的时间复杂度都是o（log（n））。它不是线程安全的。
它的特点和treeset非常像，这里不再赘述。