java中的集合

在java的iterator中，如果想删除一个元素，比如删除第一个元素，则应该先调用next()方法，再remove()。否则会抛出异常IliegalStateException。

java类提供的AbstractCollection类把基础方法size和iterator抽象化了，但是在它们的基础上实现了例行方法contains()等。一个具体的集合可以从abastractCollection超类实现了，而且一些方法已经实现。具体的集合提供iterator方法就可以了。这对于类框架来说是一种很好的设计方案。实际数据结构的实现者饼没有要实现所有例行方法

的负担。

除类名以map结尾的类以外，其它类都实现了Collection接口，而以map结尾的类实现了Map接口。

ArrayList 可以动态增长和缩减的索引序列

LinkedList 可以在任何位置进行高效插入和移除操作的有序序列

HashSet 没有重复元素的无序集合

TreeSet 有序集

EnumSet 包含枚举类型元素

LinkedHashSet 可以记住元素被插入顺序的集合

PriorityQueue 可以高效地移除最小元素的集合

HashMap 一种存储键/值关联的数据结构

TreeMap 键有序的map集合

EnumMap 键属于枚举类型的map集合

LinkedHashMap 可以记住键/值项被添加顺序的map集合

WeakHashMap 该map集合中的值如果没有在其它地方被使用，则可以被垃圾回收器回收

IdentityHashMap 该map集合中的键是用==，而不是用equals来进行比较的

多个迭代器同时对一个列表进行操作，可能发生异常。可以遵循如下规则：附加多个只读的迭代器，加一个读写迭代器。

散列表

是个链表的数组，每个列表称为一个散列表元。这种数据结构用于快速查找对象。散列表为每个对象计算一个整数，称为散列码。若要查找表中某个对象的位置，只要计算出它的散列码，再将它减去以散列表元的总数为模数的值，得出的数就是包含该元素的散列表元的索引。

HashSet

set接口继承Collection接口，而且不允许集合中存在重复项。set是一个Collction，只不过其行为不同。

HashSet允许NULL值，不允许重复。

HashSet<String>hstring = new HashSet<String>(); hstring.add("a"); hstring.add("b"); hstring.add("a"); hstring.add(null); for(String s : hstring) System.out.println(s);

输出：null b a

TreeSet树集

比散列集有所改进，是一个有序集合(同样不会有相同的元素存在)。不论你以何种顺序将节点加入到该set，当循环输出时候，它总是以排序好的顺序进行输出打印。

TreeSet<String>treeSet = new TreeSet<String>(); treeSet.add("AA"); treeSet.add("zzz"); treeSet.add("bb"); treeSet.add("bb"); for(String string : treeSet) { System.out.println(string); }

默认条件下，树集假设你插入的元素实现了Comparable接口。该接口定义了一个方法：

public interface Comparable<T> { int comparaTo(T other); }

String类实现了Comparable接口，它的comparaTo方法是按照字典顺序来对字符串进行比较的。

如果要插入自己的对象，则必须通过实现Comparable接口来自定义一个排列的顺序。Object类中的comparaTo方法没有提供任何默认的实现。

使用Comparable接口来定义排列的顺序有明显的局限性。对于一个给定的类，该接口只能实现一次。如果不想实现这个接口，或者想根据某个字段进行排序呢？

在这种情况下，可以让树集使用不同的比较方法，将一个Comparator对象传递给TreeSet类的构造器。Comparator接口声明一个compare方法，它带有两个显示的参数：

public interfaceComparator<T> { int compare(T a, T b); }

与compareTo方法一样，如果a位于b的前面，那么compare方法返回一个负整数；拂过a与b相同，则返回0；如果a位于b的后面，则返回一个正整数。

如果按照描述项进行排序，只需要定义下面实现了Comparator接口的类：

classItemComparator implements Comparator<Item> { public int compare(Item a, Item b) { String descrA = a.getDiscription(); String descrB = b.getDiscription(); return descrA.compareTo(descrB); } }

然后你可以将该类的一个对象传递给树集的构造器。

ItemComparatorcomp = new ItemComparator(); SortedSet<Item>sortByDescription = new TreeSet<Item>(comp);

优先级队列Priority Queue

是一种能够在以任意顺序插入元素后，再按照顺序读取这些元素的数据结构。当你调用remove方法时候返回当前优先级队列中的最小元素。

它利用堆来实现。使用优先级队列的典型例子是任务调度。每个任务有一个优先级，任务以随机顺序添加到队列中，每当可以启动一个新任务时候，总是以最高优先级的

任务从队列中被移除出来执行。传统意义上优先级1是最高的优先级。

散列集

是个集合，它使你能够迅速找到某个现有的元素。一般你需要拥有要查找元素的精确副本。不过映射表数据结构就是来解决这个问题。映射表用于存储

许多键/值对，你提供了键，就能够找到它对应的值。

JAVA类库为映射表提供了两个通用实现：散列映射表HashMap和树状映射表TreeMap。这两者都实现了Map接口。

HashMap对键进行散列，而TreeMap则用键的全局顺序进行排列，并将其组织成搜索树。散列函数或比较函数只能作用于键，与键相关联的值不能进行散列或则比较。

Map<String,Employee>staff = new HashMap<String,Employee>(); Employee harry =new Employee("harry hacker"); staff.put("22-99",harry);

每当将一个对象添加到映射表中时，必须提供一个键。

若要读取该一个对象，必须使用键。

String s ="22-99"; e =staff.get(s); //get harry

如果映射表里没有存储任何关于指定键的信息，那么get返回NULL。

键必须是唯一的。你不能为同一个键存储两个值。如果你使用同一个键调用两次put方法，那么第二个值将取代第一个值。

//专用的集和散列表类

弱散列映射表 WeakHashMap

使用弱引用来持有键，WeakReference对象用于持有另一个对象的引用，这里是散列表键，如果一个对象只能有WeakReference对象获得，那么垃圾回收器仍然会将其回收，它把可以应用该对象的弱引用纳入一个队列，WeakHashMap定期检查该队列，当一个弱引用被添加到该队列时，就表示键不再被任何人使用，WeakHashMap便移除相关的项。

标识散列映射表IdentityHashMap

键的散列码不是由hashCode方法计算的，而是由System.identityHashCode方法计算出来的。这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方法。IdentityHashMap类使用==来对各个对象进行比较。

集合框架

遗留下来的集合

Hashtable

该类的作用与HashMap类是相同的，实际上它们拥有相同的接口。如果不需要与遗留代码兼容，建议使用HashMap类。

位集BitSet

BitSet类用于存放一个位序列，比Boolean对象的ArrayList更高效。