CoreJava笔记 - 集合类

Java集合框架

1. 接口与实现分离
   ArrayDeque和ArrayList都实现了Queue<E>接口，在实际应用中只有创建的时候需要选择采用数组还是链表，之后都采用一样的接口来操作数据集。

2. Collection接口
   Collection是所有集合类的基本接口。接口中有两个方法最基本：

   • boolean add(E)：添加后如果集合变了，就返回true，否则返回false。
   • iterator()：返回Iterator()，用来遍历集合。

3. Iterator
Iterator有4个方法：

   • next()：iterator像一个指针。Java的iterator不指向节点，而是在节点之前。调用next()时，指针越过并返回当前节点。如果已经在尾部，则抛出NoSuchElementException。
   • hasNext()：监测是否有下一个节点，常常作为控制循环的条件。
   • remove()：不能直接调用这个函数，必须先调用next()，获取当前节点后，才能对当前节点进行操作。
   • forEachRemaining()：传入一个Lambda作为参数，可以完成for each循环的功能。

4. Collection接口中其它有用的方法

   • size(), isEmpty()
   • contains(), containsAll(),
   • equals()
   • addAll(), remove(), removeAll(), clear(), retainAll()
   • toArray(), <T> T[] toArray(T[] arrayToFill)
   • removeIf(Predicate<? super E> filter)

5. 集合类中的接口

   
   集合类中的接口
   • Collection接口：
   • Map接口：处理键值对。Map.put(K, V)、Map.get(K)。
   • List接口：提供随机访问。RandomAccess是一个tagging接口，用于判断集合是不是很好的支持随机访问（链表实现 vs. 数组实现）。
   • Set接口：与Collection相比更加严格。元素的值不能重复，equals()不要求顺序，hashCode()要保证元素相同code就相同。
   • SortedSet和SortedMap接口：用于排序的比较器对象，并支持得到集合的子集视图。
   • NavigableSet和NavigableMap接口：搜索和遍历。TreeSet和TreeMap实现了这些接口。

具体的集合

集合类

1. 链表
   在Java中，链表是双向链接的。在链表中，LinkedList.add()只将节点添加到末尾，如果想在链表中间添加节点，则需要使用Iterator.add()。迭代器的add()方法会在下一个节点之前插入新节点。

   注意：add()方法只依赖于迭代器的位置，而remove()方法还依赖于迭代器的状态（刚刚越过的节点）。
   注意：多个迭代器引用同一个容器时，若一个迭代器修改了容器结构，则另一个迭代器在访问容器时会得到ConcurrentModificationException。一般设计为：1个读写迭代器，多个只读迭代器。检测原理：容器喝迭代器都维护着一个修改次数，当迭代器发现自己的修改次数与容器的修改次数不符，则必有其他迭代器修改了容器结构。

2. 数组列表
   ArrayList与Vector：Vector是线程安全的，效率远逊ArrayList。

3. 散列集
   散列集的作用是放弃认为安排节点位置的权利。由算法自动安排节点的位置，目的在于快速查找。

   在Java中散列集是个链表数组，数组中的每一项是一个Hash桶。先计算节点的hashCode，与桶数取模，决定放入哪个桶。当某个桶被占满时，发生散列冲突，可能需要再散列。

   注意：一般认为桶数是元素个数的75%-150%，当元素达到装填因子（如75%），进行再散列。在标准库中桶数是2的幂，但是有些研究者认为桶数设为质数比较好。

   Java中的HashSet类是采用散列集实现的set类型。

4. 树集
   Java中的TreeSet的实现是红黑树。树集中的元素会自动进行排序。

   常用接口：

   • Comparator<? super E> SortedSet.comparator()
   • E SortedSet.first()
   • E SortedSet.last()
   • E NavigableSet.higher(E)
   • E NavigableSet.lower(E)
   • E NavigableSet.celling(E)
   • E NavigableSet.floor(E)
   • E NavigableSet.pollFirst()
   • E NavigableSet.pollLast()
   • Iterator<E> NavigableSet.descendingIterator()

5. 队列与双端队列
   Deque接口在Java中由ArrayDeque和LinkedList类实现。

   常用接口：

   • 接口Queue<E>，Deque<E>，ArrayDeque<E>
   • 方法add()和offer()，remove()和poll()，element()/get()和peek()

6. 优先级队列
   Java中PriorityQueue的实现方式是堆（Heap），Iterator遍历不是排序的，但是如果调用remove()方法，则总是移除最小的节点。节点必须可以比较。

映射-MAP

1. 基本操作
   Java为map提供了两个类：HashMap和TreeMap。HashMap对键进行散列，而TreeMap对键进行排序。HashMap高效，尽量使用HashMap。

   采用map.forEach(lambda)方法是最高效的访问方式。

2. 更新映射项

   • map.put(key, map.getOrDefault(key, 0)+1);
   • map.putIfAbsent(key, 0);
   • map.merge(key, 1, Integer.sum);

   和merge()类似的函数还有：

   • compute()
   • computerIfPresent()
   • computerIfAbsent()
   • replaceAll()

3. 映射视图

   • map.keySet()
   • map.values()
   • map.entrySet()

4. 弱散列映射
   WeakHashMap类：当map中的key值已经失去引用，这个(k, v)项就没有意义了，可以被垃圾回收。WeakHashMap中对象引用使用WeakReference类，如果某个对象只有WeakReference引用，那么GC就会回收该对象。

5. 链接散列集与映射
   LinkedHashSet类和LinkedHashMap类：HashSet、HashMap的节点同时是个双向链表，可以保持相互顺序。
   而且每次get或者set，都会让节点移动到链表尾部，这样链表开头都是就不需要频繁访问的节点，可以借此机制实现缓存或者释放有限资源。

6. 枚举集与映射
   EnumSet是枚举的高效实现，基于bit。EnumSet没有构造，只有厂方法：allOf，noneOf，range，of。
   EnumMap是将枚举值作为key的map：
   EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);

7. 标识散列映射
   IdentityHashMap的散列值是根据内存位置计算得出的，因此就算内容相同的两个对象也是不等的。该对象的比较用==，不用equals。

视图与包装器

容器类返回一个集合类的接口对象，通过这个集合类的接口对象，像操作某种集合一样来操作容器中的原有节点，这就是视图。

1. 轻量级集合包装器

   Card[] c = new Card[54];
   //返回视图对象，不能add/remove，会抛出UnsupportedOperationException
   List<Card> list = Arrays.asList(c);
   
   //生成100个元素的List，每个元素都是“Default”，存储代价极小
   List<String> list = Collections.nCopies(100, "Default");
   
   //返回一个不可修改的单元素集
   Collections.singleton(anObject);
   
   //Collections还可以生成空集、列表、映射，等。而且，编译器可以推测出集合的类型信息。
   Set<String> deepThoughts = Collections.emptySet();
   

2. 子范围
   可以为许多集合建立子范围视图(区间范围是前闭后开)：[start, end)
   List sl = aCollection.subList(start, end);

   对视图进行的操作会反应到原有集合：sl.clear();会删除视图涉及的所有元素。

   对于有序接口：SortedSet、SortedMap、NavigatableSet，可以使用排序建立视图：subSet/subMap、headSet/headMap、tailSet/tailMap。

3. 不可修改的视图

   • Collections.unmodifiableCollection
   • Collections.unmodifiableList
   • Collections.unmodifiableSet
   • Collections.unmodifiableSortedSet
   • Collections.unmodifiableNavigableSet
   • Collections.unmodifiableMap
   • Collections.unmodifiableSortedMap
   • Collections.unmodifiableNavigableMap

   注意：unmodifiableCollection、synchronizedCollection、checkedCollection返回的集合，其equals和hashCode是底层Object的方法。而unmodifiableList、unmodifiableSet调用的是原集合的equals和hashCode方法。

4. 同步视图
   synchronizedCollecton用于多线程同步。

5. 受查视图
   用于调试，及时检查插入时的类型错误。

6. 关于可选操作的说明
   视图有很多限制，而类支持更多方法。但是视图和类都用了一套接口，这就让视图中很多接口方法是Unsupported或者可选的。
   不应该把这种设计风格带到用户开发领域。

算法

通过接口和范型，主要算法只需要实现一次。

1. 排序与混排
   排序算法要求集合或者视图是可以修改的（支持set方法），但不必是可以改变大小的（支持）。
   Collections.sort()：稳定排序，复杂度NLogN。Java中的链表排序是将链表转为数组，进行排序后，再将数组转回链表。
   Collections.shuffle()：复杂度N。
   List.sort(Comparator)：可以对于非Comparable的对象进行排序
   Collections.reverseOrder()
Comparator.reversed()

2. 二分查找
   Collection.binarySearch()：返回大于或等于0，就是找到的索引。如果返回小于0的负数，则表示可以插入的位置：if (r < 0) list.add(-r - 1, element);。
   如果传入链表，会自动转为线性查找。

3. 简单算法

   • min和max
   • copy和fill
   • addAll和replaceAll
   • indexOfSubList和lastIndexOfSubList
   • swap，reverse，rotate
   • frequency，disjoint
   • removeIf

4. 批操作
   很多算法是对元素进行批量处理的。

   • removeAll()
   • retainAll()
   • addAll()
   • clear()

5. 集合与数组的转换
   因为Java的类库大都是支持范型前就创建的。所以提供了一些数组与容器类的转换。

   • list.toArray()：返回Object[]，不可转换为其他类型的数组。如：(String[]) list.toArray()是错误的。
   • list.toArray(new String[0])：生成一个指定类型的数组。
   • list.toArray(new String[list.size()])：填充指定数组，这种情况下不生成新数组。
   • Arrays.asList()：把数组包装成容器。

6. 编写自己的算法

   • 最好用集合类接口作为参数。
   • 如果要返回一个集合，最好也返回接口。

   // 参数是接口
   void fillMenu(JMenu menu, Collection<JMenuItem> items) {
       for (JMenuItem item : items) 
           menu.add(item);
   }
   
   // 返回值是接口的两个例子，但是只要返回是接口，上层就不需要修改：
   List<JMenuItem> getAllItems(JMenu menu) {
       List<JMenuItem> items = new ArrayList();
       for (int i = 0; i < menu.getItemCount(); i++) {
           items.add(menu.getItem(i));
       } 
       return items;
   }
   
   // 返回一个AbstractList类的不可修改的视图
   List<JMenuItem> getAllItems(final JMenu menu) {
       return new AbstractList<>() {
           public JMenuItem get(int i) {
               return menu.getItem(i);
           }
           public int size() {
               return menu.getItemCount();
           }
       }
   }
   

遗留的集合

1. Vector、Hashtable
   是ArrayList和HashMap的线程安全版本。并发访问的版本是ConcurrentHashMap。

2. Enumeration：遗留的Iterator
   Collections.enumeration：产生一个Enumeration用于遗留代码。

3. Properties：数据类型都是字符串的(K，V)对儿，可以自文件加载，也可以保存到文件。

4. 栈：Stack

5. 位集：BitSet
   例子：筛选素数。