Java核心技术卷I 记录(3)

集合

Collection 接口

在Java 类库中，集合类的基本接口是Collection 接口。这个接口有两个基本方法

public interface Collection<E>
{
boolean add(E element);
Iterator<E> iteratorQ;
。。。
}

add() 方法用于向集合中添加元素。如果添加元素确实改变了集合就返回true, 如果集合没有发生变化就返回false。例如， 如果试图向集(如Set)中添加一个对象， 而这个对象在集中已经存在，这个添加请求就没有实效，因为集中不允许有重复的对象。
iterator() 方法用于返回一个实现了Iterator 接口的对象。可以使用这个迭代器对象依次访问集合中的元素。下一节讨论迭代器。

迭代器

Iterator 接口包含4 个方法：

public interface Iterator<E>
{
E next();
boolean hasNextO;
void remove0;
default void forEachRemaining(Consumer<? super E> action) ;
}

通过反复调用next 方法，可以逐个访问集合中的每个元素。但是， 如果到达了集合的末尾，next 方法将抛出一个NoSuchElementException。因此，需要在调用next 之前调用hasNext方法。如果迭代器对象还有多个供访问的元素， 这个方法就返回true。

元素被访问的顺序取决于集合类型。如果对ArrayList 进行迭代， 迭代器将从索引0 开始， 每迭代一次， 索引值加1。然而， 如果访问HashSet 中的元素， 每个元素将会按照某种随机的次序出现。虽然可以确定在迭代过程中能够遍历到集合中的所有元素，但却无法预知元素被访问的次序。所以set是无序的你无法通过get(i)来获取某个位置的值。

将Java 迭代器认为是位于两个元素之间。当调用next 时， 迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用

更重要的是，对next 方法和remove 方法的调用具有互相依赖性。如果调用remove 之前没有调用next 将是不合法的。如果这样做， 将会抛出一个IllegalStateException 异常。如果想删除两个相邻的元素， 不能直接地这样调用：

it.remove()；
it.remove0； // Error!

相反地， 必须先调用next 越过将要删除的元素。

it, remove() ;
it.next0；
it.remove() ; // OK

集合框架

Java 集合框架为不同类型的集合定义了大量接口。集合有两个基本接口：Collection 和Map

List 是一个有序集合（ordered collection）。元素会增加到容器中的特定位置。可以采用两种方式访问元素： 使用迭代器访问， 或者使用一个整数索引来访问。后一种方法称为随机访问（random access ), 因为这样可以按任意顺序访问元素。与之不同， 使用迭代器访问时，必须顺序地访问元素。

List 接口定义了多个用于随机访问的方法：

void add(int index, E element)
void remove(int index)
E get(int index)
E set(int index, E element)

Listlterator 接口是Iterator 的一个子接口。它定义了一个方法用于在迭代器位置前面增加一个元素：

void add(E element)

由数组支持的有序集合可以快速地随机访问，因此适合使用List 方法并提供一个整数索引来访问。与之不同， 链表尽管也是有序的， 但是随机访问很慢， 所以最好使用迭代器来遍历。

Set 接口等同于Collection 接口，不过其方法的行为有更严谨的定义。集（ set ) 的add 方法不允许增加重复的元素。要适当地定义集的equals 方法：只要两个集包含同样的元素就认为是相等的，而不要求这些元素有同样的顺序。hashCode 方法的定义要保证包含相同元素的两个集会得到相同的散列码。
既然方法签名是一样的， 为什么还要建立一个单独的接口呢？ 从概念上讲， 并不是所有集合都是集。建立一个Set 接口可以让程序员编写只接受集的方法。

SortedSet 和SortedMap 接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。Java SE 6 引人了接口NavigableSet 和NavigableMap, 其中包含一些用于搜索和遍历有序集和映射的方法。（理想情况下， 这些方法本应当直接包含在SortedSet 和SortedMap
接口中。）TreeSet 和TreeMap 类实现了这些接口。

链表

数组和数组列表都有一个重大的缺陷，就是从数组的中间位置删除一个元素要付出很大的代价，其原因是数组中处于被删除元素之后的所有元素都要向数组的前端移动，同样插入一个元素也是如此。

链表（ linked list ) 解决了这个问题。尽管数组在连续的存储位置上存放对象引用， 但链表却将每个对象存放在独立的结点中。每个结点还存放着序列中下一个结点的引用。在Java 程序设计语言中， 所有链表实际上都是双向链接的(doubly linked)—即每个结点还存放着指向前驱结点的引用。

从链表中间删除一个元素是一个很轻松的操作， 即需要更新被删除元素附近的链接

Java的集合类库提供了这样的一个类LinkedList，链表与泛型集合之间有一个重要的区别。链表是一个有序集合（ ordered collection ), 每个对象的位置十分重要。LinkedList.add 方法将对象添加到链表的尾部。但是因为迭代器是描述集合中的位置，所以这种依赖于位置的add 方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。因此， 在Iterator 接口中就没有add方法。相反地， 集合类库提供了子接口Listlterator, 其中包含add 方法。
与Collection.add 不同， 这个方法不返回boolean 类型的值， 它假定添加操作总会改变链表。另外， Listlterator 接口有两个方法， 可以用来反向遍历链表:

E previous();
int previousIndex();

与next 方法一样， previous 方法返回越过的对象。LinkedList 类的listlterator 方法返回一个实现了Listlterator 接口的迭代器对象。

add 方法只依赖于迭代器的位置， 而remove 方法依赖于迭代器的状态。

set 方法用一个新元素取代调用next 或previous方法返回的上一个元素。链表只负责跟踪对列表的结构性修改， 例如， 添加元素、删除元素。set 方法不被视为结构性修改

链表迭代器的设计使得它能够发现它的集合被另一个迭代器修改了， 或是被该集合自身的方法修改了， 就会抛出一个ConcurrentModificationException 异常。例如，一个迭代器指向另一个迭代器刚刚删除的元素前面， 现在这个迭代器就是无效的，并且不应该再使用。

为了避免发生并发修改的异常，请遵循下述简单规则：可以根据需要给容器附加许多的迭代器，但是这些迭代器只能读取列表。另外，再单独附加一个既能读又能写的迭代器。

链表不支持快速地随机访问。如果要查看链表中第n个元素，就必须从头开始， 越过n-1个元素,但是LinkedList 类还是提供了一个用来访问某个特定元素的get 方法，这个方法的效率不高，如果你使用了这个方法，那么你可能需要考虑换一个数据结构。

如果有一个整数索引n，list.listlterator(n) 将返回一个迭代器， 这个迭代器指向索引为n 的元素前面的位置。也就是说， 调用next 与调用list.get(n) 会产生同一个元素， 只是获得这个迭代器的效率比较低。

使用链表的唯一理由是尽可能地减少在列表中间插人或删除元素所付出的代价,如果列表只有少数几个元素， 就完全可以使用ArrayList。

如果需要对集合进行随机访问， 就使用数组或ArrayList , 而不要使用链表。

散列集

如果想要査看某个指定的元素， 却又忘记了它的位置， 就需要访问所有元素， 直到找到为止。如果集合中包含的元素很多， 将会消耗很多时间。如果不在意元素的顺序。那么可以用散列表。其缺点是无法控制元素出现的次序。它们将按照有利于其操作目的的原则组织数据。散列表为每个对象计算一个整数， 称为散列码（hashcode)。 散列码是由对象的实例域产生的一个整数。

在Java 中， 散列表用链表数组实现。每个列表被称为桶（ bucket) 。要想査找表中对象的位置， 就要先计算它的散列码， 然后与桶的总数取余， 所得到的结果就是保存这个元素的桶的索引。例如， 如果某个对象的散列码为76268, 并且有128 个桶， 对象应该保存在第108 号桶中（ 76268除以128 余108 )。当然， 有时候会遇到桶被占满的情况， 这也是不可避免的。这种现象被称为散列冲突（ hash
collision) 。 这时， 需要用新对象与桶中的所有对象进行比较， 査看这个对象是否已经存在。如果散列码是合理且随机分布的， 桶的数目也足够大， 需要比较的次数就会很少。

如果想更多地控制散列表的运行性能， 就要指定一个初始的桶数。桶数是指用于收集具有相同散列值的桶的数目。如果要插入到散列表中的元素太多， 就会增加冲突的可能性， 降低运行性能。

如果大致知道最终会有多少个元素要插人到散列表中， 就可以设置桶数。通常， 将桶数设置为预计元素个数的75% ~ 150%。

当然，并不是总能够知道需要存储多少个元素的， 也有可能最初的估计过低。如果散列表太满， 就需要再散列（rehashed)。如果要对散列表再散列， 就需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。装填因子（load factor ) 决定何时对散列表进行再散列。例如， 如果装填因子为0.75 (默认值)，而表中超过75%的位置已经填入元素， 这个表就会用双倍的桶数自动地进行再散列。

Java 集合类库提供了一个HashSet 类，它实现了基于散列表的集。它的具体实现是HashMap。可以用add 方法添加元素。contains 方法已经被重新定义， 用来快速地查看是否某个元素已经出现在集中。它只在某个桶中査找元素，而不必查看集合中的所有元素。散列集迭代器将依次访问所有的桶。由于散列将元素分散在表的各个位置上，所以访问它们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用HashSet。

equals 和hashCode的定义必须兼容，即如果x.equals(y) 为true, x.hashCode() 必须等于y.hashCode()。

树集

TreeSet 类与散列集十分类似， 不过， 它比散列集有所改进。树集是一个有序集合( sorted collection ) 。 可以以任意顺序将元素插入到集合中。在对集合进行遍历时， 每个值将自动地按照排序后的顺序呈现。将一个元素添加到树中要比添加到散列表中慢。

要使用树集， 必须能够比较元素。这些元素必须实现Comparable 接口或者构造集时必须提供一个Comparator。所以这也约束了不是什么情况下都能用树集。

映射

映射（map) 数据结构就是为此设计的。映射用来存放键/ 值对。如果提供了键， 就能够查找到值。

散列映射对键进行散列， 树映射用键的整体顺序对元素进行排序， 并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。散列稍微快一些， 如果不需要按照排列顺序访问键， 就最好选择散列。

从映射中删除一个键， 同时与之对应的值也被删除。

有3 种视图： 键集、值集合（不是一个集） 以及键/ 值对集。键和键/ 值对可以构成一个集， 因为映射中一个键只能有一个副本。下面的方法：

Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K, V>>entrySet()

会分别返回这3 个视图。

标识散列映射

类IdentityHashMap 有特殊的作用。在这个类中， 键的散列值不是用hashCode 函数计算
的， 而是用System.identityHashCode 方法计算的。在对两个对象进行比较时， IdentityHashMap 类使用==, 而不使用equals。

也就是说， 不同的键对象， 即使内容相同， 也被视为是不同的对象。在实现对象遍历算法（如对象串行化）时， 这个类非常有用， 可以用来跟踪每个对象的遍历状况。

链接散列集与映射

LinkedHashSet 和LinkedHashMap 类用来记住插人元素项的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并入到双向链表中。

链接散列映射将用访问顺序， 而不是插入顺序， 对映射条目进行迭代。每次调用get 或put, 受到影响的条目将从当前的位置删除， 并放到条目链表的尾部（只有条目在链表中的位置会受影响， 而散列表中的桶不会受影响)