corejava基础知识(5)-集合

本文是对 java 集合的总结。书的思路是将接口与实现分开讲；然后从父讲起，再讲子对父的提升。我觉得这种方式很好理解加记忆，所以本文也是这样整理的。

集合框架

主要思路是让接口与实现分离

集合框架的接口：两个基本接口 Collection 和 Map

集合框架的类：

接口

两个基本接口：Collection 和 Map

Collection

以下是Collection接口内的一些方法

public abstract interface class java.util.Collection
{

  public abstract boolean add(java.lang.Object);
  public abstract boolean remove(java.lang.Object);
  public abstract boolean equals(java.lang.Object);
  public abstract void clear();
  public abstract boolean isEmpty();
  public abstract boolean contains(java.lang.Object);
  public abstract int size();
  public abstract java.util.Iterator iterator();
  public abstract boolean addAll(java.util.Collection);
  public abstract boolean containsAll(java.util.Collection);
  public abstract boolean removeAll(java.util.Collection);
  public abstract boolean retainAll(java.util.Collection);
  public boolean removeIf(java.util.function.Predicate);
  ...
  
}

可以看出来就是 大小，加，删，是否含某个元素，是否空 等等，这些集合最基础的功能

Collection中有Iterator接口

public abstract interface class java.util.Iterator
{

  public void remove();
  public abstract boolean hasNext();
  public abstract java.lang.Object next();
  public void forEachRemaining(java.util.function.Consumer);

}

Map

以下是Map接口内的一些方法

public abstract interface class java.util.Map
{

  public boolean remove(java.lang.Object, java.lang.Object);
  public abstract java.lang.Object get(java.lang.Object);
  public abstract java.lang.Object put(java.lang.Object, java.lang.Object);
  public abstract boolean equals(java.lang.Object);
  public abstract void clear();
  public abstract boolean isEmpty();
  public boolean replace(java.lang.Object, java.lang.Object, java.lang.Object);
  public void replaceAll(java.util.function.BiFunction);
  public abstract int size();
  public abstract void putAll(java.util.Map);
  public java.lang.Object putIfAbsent(java.lang.Object, java.lang.Object);
  public abstract java.util.Set keySet();
  public abstract boolean containsValue(java.lang.Object);
  public abstract boolean containsKey(java.lang.Object);
  public java.lang.Object getOrDefault(java.lang.Object, java.lang.Object);
  public void forEach(java.util.function.BiConsumer);
  ...

}

可以看出来就是 大小，加映射，删映射，用键查值，是否空 等等，这些映射最基础的功能。还有些视图的部分，下篇文章具体讲

Collection的子接口

List

有序集合，新加支持随机访问功能：

• add(n, 元素)
• remove(n)
• get(n)
• set(n, 元素)

Set

1. 元素不重复，所以要适当的定义equals方法；
2. 子接口SortedSet，故名思义是排好序的，所以要适当的定义比较器
3. SortedSet的子接口NavigableSet中设计了一些搜素，遍历的方法

Queue

1. 入队尾，出对头
2. 子接口Qeque双端队列，两头都可以出入

Map的子接口

其实和Set差不多

1. 子接口SortedMap，故名思义是排好序的，所以要适当的定义比较器
2. SortedMap的子接口NavigableMap中设计了一些搜素，遍历的方法

对接口的实现

List

LinkedList(链表)

java中的链表都是双向的（有前驱后驱）。重点讲下它的迭代器ListIterator

• 初始位置： |ABCD
• iter.next: A|BCD
• iter.previous: |ABCD
• iter.add : 把元素加到光标|之前，注意是之前
• iter.remove必须在it.next或it.previous使用之后使用，把光标经过的元素删除

链表使用注意：

• 使用链表是可以减少在列表中间插入删除元素所付出的代价。
• 避免使用以整数索引链表中的位置，这样效率很低

ArrayList(数组列表)

ArrayList： 动态泛型数组列表，可以自动调节数组容量。当需要随机访问时使用它效率更高，不用链表。
讲下capacity和size的区别：

• new ArrayList<>(100) 100 是capacity，是初始容量，如果实际size超过它，容量会自动增加
• array.size()返回的是数组列表内元素实际的个数。

p.s. 这和c++的 vector 很像

Set

HashSet(散列集)

• HashSet: 基于散列表的Set，内部用链表数组实现。初始化时可以指定容量和装填因子。
• 由于HashSet访问是随机的，所以当不需要关心集合中的顺序时才使用它。
• 子类LinkedHashSet，里面的元素之间是双向链表，迭代器是按插入顺序进行访问的。

TreeSet(树集)

-TreeSet: 实现SortedSet接口，内部基于红黑树。由于是有顺序的，所以用户一般要自定义比较器。迭代器是按排序顺序进行访问的。

• 当不需要顺序时，用HashSet，因为它更快。
• 可以实现升级版NavigableSet接口，higher(v),lower(v),pollFirst(),pollLast(),反向迭代 等等。

Queue

一般用它的升级版Deque，而Deque可以由ArrayDeque和LinkedList实现。下面主要介绍PriorityQueue

PriorityQueue(优先级队列)

• PriorityQueue：优先级队列，内部基于堆（heap）。
• 按任意顺序插入，却总是按排序顺序输出最小值。
• PriorityQueue<Type> pq = new PriorityQueue();，从左边可以看出这货是类。

Map

HashMap

• 顾名思义和HashSet差不多，只不过是对建进行散列。
• 子类LinkedHashMap，注意链表散射映射，迭代器是按访问顺序进行访问的。每次调用 get 或 put, 受到影响的条目将从当前的位置删除，并放到条目链表的尾部。

TreeMap

• 顾名思义和HashMap差不多，只不过是对建进行红黑树排序。
• 同样 当不需要顺序时，用HashMap，因为它更快.

一些技巧：

• 遍历Map：

scores.forEach((k, v) -> // 访问 k, v 的最快方法
        System.out.println("key=" + k + ", value" + v));

• 用 Map 计数：

scores.put("Jack", scores.getOrDefault("Jack", 0) + 1); // 方法1
scores.merge("Jack", 1, Integer::sum); // 方法2

WeekHashMap

弱散列映射：当对键的唯一引用来自散列条目时，这一数据结构将与垃圾回收器协同工作一起删除键 / 值对。也就是当某个值没用了它会被自动回收。

IdentityHashMap

• IdentityHashMap 中 键的散列值 不是用 hashCode 函数计算的，而是用 System.identityHashCode 方法计算的（Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式）。
• 所以，在对两个对象进行比较时，IdentityHashMap 使用 == , 而不使用equal。也就是不同的键对象，即使内容相同，也被视为是不同的对象。
• 在实现对象遍历算法 (如对象串行化)时，可以它用来跟踪每个对象的遍历状况。

遗留的集合

看看就好，遇到时再查书

本文示例代码：github