有书共读】java核心技术卷1--第9章

======================java核心技术卷1第9章-集合==================

主要内容：

1、Java集合框架

       （1）将集合的接口与实现分离

       与现代的数据结构类库的常见情况一样，Java集合类库也将接口（interface）与实现（implementation）分离

       （2）Collection接口

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

public interface Collection<E>{

       Boolean add(Eelement);

       Iterator<E>iterator();

       …

}

add方法用于向集合中添加元素。若添加元素确实改变了集合就返回true，否则返回false；

iterator方法用于返回一个实现Iterator接口的对象。可以使用这个迭代对象依次访问集合中的元素。

（3）迭代器

Iterator接口中包含四个方法：

public interface Iterator<E>{

       E next();

       Boolean hasNext();

       void remove();

       default void forEachRemaining(Consumer<? suoer E> action);

}

反复调用next方法，可以逐个访问集合中的每个元素。为了防止达到集合末尾时抛出NoSuchElementException，在使用next之前调用hasNext方法，hasNext方法返回true则可继续调用next方法。

（4）泛型实用方法

由于Collecttion与Iterator都是泛型接口，可以编写操作任何集合类型的实用方法。

集合有两个基本接口：Collection和Map。

List是一个有序集合。元素会增加到容器中的特定位置。可以采用两种方式访问元素：使用迭代器访问，或者使用一个整数索引来访问。

Set接口等同于Collection接口，不过其方法的行为有更严谨的定义。集（set）的add方法不允许增加重复元素。

2、具体的集合

       （1）链表，链表将每个对象存放在独立的结点中。每个结点还存放着序列中下一个结点的引用。在Java中，所有链表都是双向链接的，即每个节点还存放着指向前驱结点的引用。链表是个有序集合。

       （3）散列表。散列表为每个对象计算一个整数，称为散列码。散列码是由对象的实例域产生的一个整数，即具有不同数据域的对象将产生不同的散列码。

       （4）树集。TreeSet集与散列集十分相似。树集是一个有序集合，可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动地按照排序后的顺序呈现。

       （5）队列与双端队列。有两个端头，可以在头部和尾部同时添加或删除元素，不支持在队列中间添加元素。

       （6）优先级队列。元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。即，调用remove方法时，总会获得当前优先级队列中最小的元素。优先级队列使用了堆（heap），堆是一个可以自我调整的二叉树，可以对树执行添加和删除操作，可以让最小的元素移动到根，不必花时间对元素进行排序。

       使用优先级队列的典型示例是任务调度。每个任务有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，都将优先级最高的任务从队列中删除。

3、映射

       映射用来存放键值对。

       （1）基本映射操作，两个通用的实现：HashMap和TreeMap。这两个类都实现了Map接口。散列映射对键进行散列，树映射用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或比较函数只能作用于键。与键关键的值不能进行散列或比较。

       （3）映射视图。三种视图：键值、值集合以及键值对集合。键和键值对可以构成一个集，映射中一个键只能有一个副本。

       （5）链接散列集与映射。LinkedHashSet 和LinkedHashMap用来记住插入元素项的顺序。链接散列映射将用访问顺序，而不是插入顺序，对映射条目进行迭代。

       （6）枚举集与映射。EnumSet是一个美剧类型元素集的高校实现。EnumMap是一个键类型为枚举类型的映射。它可以直接且高效地用一个值数组实现。

       （7）标识散列映射。在类IdentityHashMap中，键的散列值不是用hashCode函数计算的，而是用System.indentityHashCode方式计算的。

4、算法

       泛型集合接口有一个很大的有点，即算法只需要实现一次。

       （1）排序与混排

       （2）二分查找。

              Collections类的binarySearch方法实现了这个算法。注：集合必须是排好序的。如：

                     i = Collection.binarySearch(c,element)

返回的i为大于等于零的话则是匹配到对象的索引，i为负数则表示没有匹配到元素。

       （4）批操作。批量删除、批量复制等。

       如批量删除操作：coll1.removeAll(coll2),将从coll1中删除coll2中出现的元素。

       （5）集合与数组的转换。

       如需数组转集合：

              String[] V = …;

              HashSet<String> staff = new HashSet<>(Array.asList(V));