java容器资料

原文在此 收入blog中以备参考

Java容器类学习心得

由于我对C++比较熟悉，所以学习Java应该重点体会Java带来的新概念。本文基本上是Java标准库中集合框架的基本概念，没有例子。写本文的目的在于方便我很长时间后若是忘了这些东西可以通过这片文章迅速回忆起来。

1. 接口
整个Java容器类的基础是容器接口（例如Collection，Map等接口），而不是类。使用接口的最大好处在于将容器的实现与容器的接口分开，这就意味着你可以使用相同的方法访问容器而不用关心容器是由什么样的数据结构实现的。同样，Iterator接口也使得用户可以使用相同的方法访问不同的容器类。以上这些是通用算法的基础。

1.1 Collection接口
Collection接口有如下基本方法：
boolean add(Object obj)：如果添加对象后，集合确实发生了变化，则返回true；否则返回false
Iterator iterator()：返回一个实现了Iterator接口的对象
此外，还有
int size(),boolean isEmpty()，boolean contains(Object obj)，void clear()等许多有用的方法

1.2 Map接口
Map用于存放关键字/值对。有如下基本方法：
Object get(Object key)
Object put(Object key,Object balue)
Set keySet()
Set entrySet()
此外，还有其他有用的方法。
需要注意的是，从表面看它似乎就是一种由键值对构成的集合，但实际上并不是这样。不过另一方面假如将Map的某一部分看作集合，有时候也还是显得非常方便的。换言之你可以创建一个集合用它来表达Map的那一部分。综上所述，一个Map可以返回的东西包括它的键值构成的一个Set、由它的值构成的一个集合或者由它的键值对构成的一个Set。

1.3 Iterator接口
Iterator接口有下面3个基本方法：
Object next()：返回迭代器刚越过的元素的引用
boolean hasNext()：判断容器内是否还有可供访问的元素
void remove()：删除迭代器刚越过的元素
注意：Java中的迭代器与STL中的迭代器在概念上有很重要的区别。在STL中，迭代器类似于数组的索引，使用这种迭代器可以查看存放在该位置上的元素（类似于通过数组索引i来访问c[i]一样）。Java中的迭代器并不这样运行。查看与位置的变化紧密的结合在一起。每次通过next()访问一个元素的同时，迭代器的位置会自动向前走一步。
这个问题可以这样理解：Java中的迭代器指向的位置并不是元素，而是元素之间。这样，每次调用next()时，迭代器便越过下一个元素，同时返回它刚越过的那个元素的引用。
根据上面的说明，很容易得出下面的代码是错误的：

java 代码

it.remove();
it.remove();

而下面的代码是正确的：

java 代码

it.remove();
it.next();
it.remove();

迭代器的典型应用

java 代码

Iterator it=c.iterator();
while(it.hasNext())
{
 Object obj=it.next();
 //do something with obj
}

1.4 子接口
1.4.1 List接口
List从Collection接口中分立出来是因为List的特点——有序的集合。这里指的有序并不是按照大小排好序的（Sorted），而是指集合是可以以确定的顺序访问的序列。针对List的这个特点，它比Collection接口增加了通过索引进行操作的方法。例如，add、remove、get、set等方法的参数表中都可以加入索引的数值，从而操作处在索引位置处的元素。

1.4.2 Set接口
Set与List的不同，它里面的元素是无序的；所以，不能通过任何索引的方法来操作Set对象

1.4.3 ListIterator接口
使用与List的迭代器，比Iterator接口增加了一些方法（例如add()等）。此外，由于List是双向表，所以还增加了Object previous()和boolean hasPrevious()方法，用法与next()和hasNext()一样。

1.4.4 SortedMap接口
包含如下基本方法：
Comparator comparator()
Object firstKey()
Object lastKey()

2. 抽象容器类
2.1 抽象容器类包括AbstractCollection，AbstractList，AbstractSet等等

2.2 为什么要有抽象结合类？
例如Collection接口中定义了许多有用的方法，如果实现Collection接口的每个类都自行实现这么多的方法，那将是非常麻烦的。为了使实现Collection接口的类的实现更容易，AbstractCollection类让一些基本方法（比如add()和iterator()）变成了抽象的方法，而利用这些基本方法的其他方法（例如addAll()等等）则具体实现了。

3. 具体的容器
3.1 ArrayList与LinkedList
都是实现了List接口的类，是有序集。List接口支持通过索引的方法来访问元素，对于这一点，ArrayList没有任何问题；但是对于LinkedList则有很大的问题，链表本身不应该支持随机存储，但是作为List的一个实现，链表也提供了对随机访问的支持，但是效率很低。每次通过索引的方法都是进行一次遍历。我认为，其实就不应该让链表支持随机访问；而Java这样实现我想是因为整个集合框架的体系，使得链表与数组可以使用同样的方法使用。综上所述，对于LinkedList最好不使用随机访问，而使用迭代器。

3.2 TreeSet
3.2.1 TreeSet是SortedSet的一个实现。根据数据结构的知识可以知道，树的效率非常高，而且Java标准库中有TreeSet这样的类，以后应该尽量使用TreeSet来提高程序的效率。
3.2.2 需要注意的是：TreeSet作为有序集，它通过compareTo或者Comparator来将集合元素排序。任何具有相同比较值的元素（无论它们是否equals()），在TreeSet中都作为同一个元素，从而不能有重复。这样以来，即使是不同的对象也不能加入到集合中，这一点有时候很不方便。我在编写A*算法时，不同状态有时候对应着同一个启发函数值，那么这些不同的状态就无法加入到TreeSet中。

3.3 HashSet
3.3.1 HashSet是非常高效的数据结构，与TreeSet不同，HashSet是比较对象的equals()方法来区分不同的对象。这样只有真正不同的对象才能不被重复的加入到集合中。
3.3.2 需要注意的是：HashSet效率非常高，但是对象的hashCode函数不好确定。一般默认的对象的hashCode函数是根据对象的内存地址得到的。好的hashCode函数是HashSet成功运用的关键。

4. 视图
4.1 什么是视图？
对映象类使用keySet()方法，仿佛该方法建立了一个新的集合，并将影响的所有关键字都填入这个集合。实际情况并非如此，对这个集合的任何操作都将反映到原始的映象对象上。
实际上，keySet()返回的是一个实现Set接口的对象，对该对象的操作就是对映象的操作。这样的集合成为视图。
4.2 视图的应用
4.2.1 将现有的容器变为线程安全的容器：使用Collections.synchronizedCollection(Collection c)方法，在SDK文档中该方法的解释是“Returns a synchronized (thread-safe) collection backed by the specified collection”。
4.2.2 将现有的容器变为只读的容器：使用Collections.unmodifiableCollection(Collection c)方法，在SDK文档中该方法的解释是“Returns an unmodifiable view of the specified collection.”。
4.2.3 子范围
4.2.4 Arrays类中的asList()方法

5. 通用算法
通用的集合接口带来的一大好处就是可以编写通用算法。可以使用Collections中的静态通用方法，也可以编写自己的通用方法。
（具体的算法的内容在此略去）

总结：千万记住这句话——没有最好的容器（数据结构），要根据不同的问题选择不同的容器，以此来达到功能的要求和效率的最优。