java集合

• 1. collection接口
  • 1.1. 迭代器
  • 1.2. 实现foreach循环
  • 1.3. 泛型实用方法
• 2. 集合框架中的接口
  • 2.1. List接口
  • 2.2. 散列集
  • 2.3. 树集
  • 2.4. 队列与双端队列
  • 2.5. 优先队列
• 3. 映射
  • 3.1. 基本映射操作
  • 3.2. 更新映射条目
  • 3.3. 映射视图
  • 3.4. 弱散列映射
  • 3.5. 连接散列集和映射
  • 3.6. 标识散列映射
• 4. 视图与包装器
  • 4.1. 小集合
  • 4.2. 子范围
  • 4.3. 不可修改的视图
  • 4.4. 检查型视图
• 5. 算法
  • 5.1. 排序与混排
  • 5.2. 二分查找
  • 5.3. 批操作
  • 5.4. 集合与数组的转换

1. collection接口

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

public interface Collection<E>{
	boolean add(E element);//用于添加对象
	Iterator<E> iterator();//返回一个实现了Iterator接口的对象，迭代器。
	...//还有其他方法
}

1.1. 迭代器

Iterator接口包含4个方法

public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);

        while(this.hasNext()) {
            action.accept(this.next());
        }

    }
}

• 调用next方法可以访问集合的下一个元素，但在此之前需要调用hasNext方法确定是否还有下一个元素，否则会抛出一个异常。
• java的迭代器和c++不同，c++是根据数组索引建模的；而java迭代器可以看成位于两个元素中间，当调用next方法，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。
• Iterator的remove方法会删除上一次调用next方法时返回的元素，如果在调用next方法之前没有调用next，会抛出异常，即remove对next有依赖性。

1.2. 实现foreach循环

要想使用foreach循环，需要实现Iterable接口

public interface Iterable<T> {
    Iterator<T> iterator();//实现该方法
    ...
}

接口中的方法返回一个实现类的迭代器，因此还必须先实现这个迭代器，下面以自己实现的LIFO栈为例

public class stack<T> implements Iterable<T> {
    private T st[];//栈数组
    private int top;//栈顶
    private int N;//栈的容量

    public stack(int cap){
        this.N = cap;
        st = (T[]) new Object[cap];
        this.top = -1;
    }
    
    ...
    
    @Override
    public Iterator<T> iterator() {//返回迭代器,实现Iterable接口中的方法
        return new ReverseIterator();
    }

    public class ReverseIterator implements Iterator<T>{//实现一个迭代器，能够使用foreach循环遍历栈（后进先出遍历）
        private int i = top;//内部类可以访问私有字段

        @Override
        public boolean hasNext() {
            return i>-1;
        }

        @Override
        public T next() {
            return st[i--];
        }
    }
}

在该类中，我编写了实现了Iterator接口的内部类，其能够按照后进先出的顺序遍历堆栈。Iterable中的方法返回该类的引用，因此foreach循环能够调用此迭代器来遍历堆栈。

Collection接口扩展了Iterable接口，因此对于标准库中的任何集合都能够使用foreach循环。

总之，对于自己实现的类，要想使用foreach循环，要经历以下步骤：

1. 实现一个适用于该类的迭代器。
2. 实现Iterable接口并重写其方法，返回你所写的迭代器。

1.3. 泛型实用方法

Colllection接口中还有其他实用的方法

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object var1);//检查是否包含某个元素

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] var1);//转换为数组

    default <T> T[] toArray(IntFunction<T[]> generator) {
        return this.toArray((Object[])generator.apply(0));
    }

    boolean add(E var1);

    boolean remove(Object var1);

    boolean containsAll(Collection<?> var1);

    boolean addAll(Collection<? extends E> var1);

    boolean removeAll(Collection<?> var1);

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        Iterator each = this.iterator();

        while(each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }

        return removed;
    }

    boolean retainAll(Collection<?> var1);

    void clear();

    boolean equals(Object var1);

    int hashCode();

    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    default Stream<E> stream() {
        return StreamSupport.stream(this.spliterator(), false);
    }

    default Stream<E> parallelStream() {
        return StreamSupport.stream(this.spliterator(), true);
    }
}

所有的实现类都必须要提供这些方法，这会非常麻烦，因此java类库中有一个AbstractCollection类，其实现Collection接口中大部分的方法。但是仍保持size和iterator仍为抽象方法。

因此具体集合类能够扩展AbstractCollection类，只需提供size方法和iterator方法即可。

2. 集合框架中的接口

集合有两个基本接口：Collection和Map。第二个为映射。

图片转载自网络

因为映射包含键值对，因此在映射中插入对象要用put方法：

V put(K key,V value)

要从集合中读取元素，可以使用迭代器访问元素。不过，从映射中读取值则需要使用get方法：

V get(K key)

2.1. List接口

List是个有序集合，继承自Collection。元素会增加到容器中的特定位置。可以采用两种方式访问元素：

• 使用迭代器访问。
• 使用一个整数索引来访问，该方式为随机访问。

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

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

它也有个抽象类AbstractList,其实现了List接口中的大部分方法。

实现类中最常用的是数组列表(ArrayList)和链表(LinkList)，第一个是以数组为基准实现的，而第二个是基于双向链表实现的。

链表的插入和删除效率高于数组，但是查找元素的效率却很低。链表中的get和set方法的效率是非常低的，并不推荐使用，因此有一个专门用于链表的迭代器——listIterator,可以使用listIterator()方法返回

LinkedList linkedList = new LinkedList();
ListIterator listIterator = linkedList.listIterator();

ListIterator接口中提供了许多有用的方法：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();//反向遍历链表

    int nextIndex();//返回下一次调用next方法时返回元素的索引

    int previousIndex();

    void remove();

    void set(E var1);

    void add(E var1);//添加到迭代器当前位置之前
}

注意：集合中的remove方法不能连续调用，需要调用一次next或previous在进行remove操作。如果上一次操作是previous，remove会删除右侧的元素。

如果一个迭代器发现它的集合被另一个迭代器修改了，或是被该集合自身的某个方法修改了，就会抛出一个异常。
因此，为了避免并发修改异常，请遵循这样一个原则：

• 可以根据需要为一个集合关联多个迭代器，前提是这些迭代器只能读取集合，或者可以在关联一个能同时读写的迭代器。

2.2. 散列集

先看一下散列表的概念：

• 有一种数据结构可以用于快速的查找对象，这就是散列表。

• 散列表为每个对象计算一个整数，称为散列码，散列码是由对象的实例字段得出的一个整数，有不同数据的对象将产生不同的散列码。

• Object类中有一个hashCode方法来产生一个散列码，如果定义自己的类，需要重写hashCode，使之与equals方法相容(即两个相同的对象产生的散列码也要相同)

• 在java中，散列表用链表数组实现，每个列表称为桶。要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。

java集合类库中提供了一个HashSet类，它实现了基于散列表的集（set）。

而对于Set接口，其等同于Collection接口，但是它的add方法不允许增加重复的元素，并且不在意元素之间的顺序，只要两个集具有相同的元素，就可以认为他们是相等的。

HashSet只是不保证有序，并不是保证无序！！！

      HashSet<String> strings = new HashSet<>();
      strings.add("shit");
      strings.add("fuck");
      strings.add("dog");
      for(String s:strings){
          System.out.println(s);
      }
      //shit
//fuck
//dog   这是有序的！

2.3. 树集

TreeSet类与散列集十分类似，不过树集是一个有序集合。

可以将任意顺序的元素插入到集合中。在对集合进行遍历时，值将自动地按照排序后的顺序呈现。

TreeSet<String> strings = new TreeSet<>();
strings.add("b");
strings.add("a");
strings.add("c");
for(String st:strings){
    System.out.println(st);
}//a b c

排序是用红黑树完成的，因此将一个数据元素添加到树中要比添加到散列表中慢。

2.4. 队列与双端队列

双端队列不同于队列，其允许在头部和尾部都高效地添加或删除元素，不支持在队列中间添加元素。如果要使用双端队列，需要实现Deque接口。

ArrayDeque和LinkedList类都实现了这个接口，因此能在队头和队尾进行操作。

Deque中的方法

public interface Deque<E> extends Queue<E> {
    void addFirst(E var1);//添加到队头

    void addLast(E var1);//添加到队尾

    boolean offerFirst(E var1);//同上

    boolean offerLast(E var1);

    E removeFirst();//移除队头

    E removeLast();//移除队尾

    E pollFirst();

    E pollLast();

    E getFirst();

    E getLast();

    E peekFirst();

    E peekLast();

    boolean removeFirstOccurrence(Object var1);

    boolean removeLastOccurrence(Object var1);

    boolean add(E var1);

    boolean offer(E var1);

    E remove();//删除队头

    E poll();//同上

    E element();//返回队头的元素

    E peek();

    boolean addAll(Collection<? extends E> var1);

    void push(E var1);

    E pop();

    boolean remove(Object var1);

    boolean contains(Object var1);

    int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();
}

2.5. 优先队列

优先队列(PriorityQueue)中的元素可以按照任意的顺序插入，但会按照有序的顺序进行检索。无论何时调用remove方法，总会获得当前优先队列中最小的元素。

但是：优先队列并没有对所有的元素进行排序！ 其只是使用了堆这个数据结构来找出最小的元素。

3. 映射

映射用来存放键值对。如果提供了键，就能找到值。

3.1. 基本映射操作

java类库为映射提供了两个通用的实现：HashMap和TreeMap，这两个类都实现了Map接口。

每当往映射中添加一个对象时，必须同时提供一个键。在这里键是String对象，对应的值为Integer对象。

HashMap<Integer, String> hash = new HashMap<>();
hash.put(1,"小明");
hash.put(2,"小张");

要想检索一个对象，必须使用键！

System.out.println(hash.get(1));//输出  小明

如果映射中没有存储与给定键对应的信息，get将返回null。可以使用默认值来代替null。

System.out.println(hash.getOrDefault(3,"空缺"));//第二个参数为默认值
//输出  空缺

键必须是唯一的！ 不能对同一个键存放两个值，如果对同一个键调用两次put方法，第二个值就会取代第一个值。但是put会返回第一个值。

System.out.println(hash.put(1,"小王"));//输出  小明
//小王取代了小明

3.2. 更新映射条目

如果要统计一个单词在文件中的出现数目，看到一个单词时计数器加1

counts.put(word,counts.get(word)+1);//counts是一个映射，键为单词，值为出现数

但是在第一次看见这个单词时，其数目为null，对null操作会产生一个异常。

有三种方法来更新这个值：

1. 使用默认值

counts.put(word,counts.getOrDefault(word,0)+1);

2. putIfAbsent方法

counts.putIfAbsent(word,0);//如果word不存在或与null关联，则将其与0关联
counts.put(word,counts.get(word)+1);

3. merge方法

counts.merge(word,1,Integer::sum);
//如果键原先不存在，该方法会将word和1相关联，否则使用Integer::sum函数
//组合原值和1

3.3. 映射视图

集合框架不认为映射本身是一个集合。不过，可以得到映射的视图(view)——这是实现了Collection接口或某个子接口的对象。

有三种视图：

• 键集
• 值集合（不是一个集）
• 键/值对集

下面的方法会返回上面所列的视图

Set<K> KeySet()//键集
Collection<V> values()//值集合
Set<Map.Entry<K,V>> entrySet()//键值对集

其中KeySet不是HashSet或TreeSet，而是实现了Set接口的另外类的对象。

由于都扩展了Collection接口，所以他们都可以用foreach循环来遍历

      HashMap<Integer, String> hash = new HashMap<>();
      hash.put(1,"小明");
      hash.put(2,"小张");
      Set<Map.Entry<Integer, String>> entries = hash.entrySet();
      for (Map.Entry<Integer,String> en:entries) {
          System.out.println(en);
      }
      /*
      1=小明
2=小张
      */

注意：

• 如果在视图上删除某个值或者键，映射中的键值对都会被删除！

• 不能向视图中添加元素！

3.4. 弱散列映射

如果有一个值，其对应的键已经不再在程序中的任何地方使用，因为没有任何途径可以引用这个值的对象，所以无法从映射中删除这个这个键值对。而垃圾回收器也不会回收它(其中所有的桶是活动的)。因此，需要程序负责从长期存活的映射表中删除那些无用的值。

或者使用WeakHashMap。

WeakHashMap使用弱引用保存键，对于这种类型的对象，垃圾回收器会回收。

3.5. 连接散列集和映射

LinkedHashSet 和 LinkedHashMap 类会记住插入元素项的顺序。这样就可以避免散列表中的项看起来顺序是随机的。

3.6. 标识散列映射

类IdentityHashMap 有特殊的用途。在这个类中，键的散列值不是用hashCode计算的，而是用System.IdentityHashCode方法计算的。这是根据对象的内存地址计算散列码时所使用的方法。而且，在对两个对象进行比较时，其使用”==”而不是equals。

4. 视图与包装器

4.1. 小集合

java9中引入了一些静态方法，可以生成给定的元素的集或列表，以及给定键值对的映射。

List<String> names = List.of("a","b","c");
Set<Integer> numbers = Set.of(2,3,5);
Map<String,Integer> scores = Map.of("a",2,"b",3,"c",5);

会分别生成包含3个元素的一个列表、一个集和一个映射。

Map接口有一个静态方法ofEntries，能接受任意多个Map.Entry<K,V>对象。

Map<String, Integer> s = Map.ofEntries(
        Map.entry("a", 1)
        Map.entry("b", 2)
);

这些集合对象都是不可修改的！ 如果需要一个可更改的集合，可以把这个不可修改的集合传递到构造器：

List<String> hello = List.of("hello", "java");
ArrayList<String> strings = new ArrayList<>(hello);
//或者ArrayList<String> strings = new ArrayList<>(List.of("hello", "java"));
strings.add("!");
for(String st:strings){
    System.out.println(st);
}

4.2. 子范围

可以为很多集合建立子范围视图。

ArrayList<Integer> integers = new ArrayList<>();
integers.add(1);
integers.add(2);
integers.add(3);
List<Integer> in = integers.subList(0, 2);
for(int a:in){
    System.out.println(a);
}//1 2

第一个索引包含在内，第二个则不包含。这与String类的substring操作中的参数情况相同。

可以对子范围应用任何操作，而且操作会自动反映到整个列表！

对于有序集合映射，可以使用排序顺序而不是元素位置建立子范围。具体在SortedSet接口中。

4.3. 不可修改的视图

Collections类（不是Collection接口）有几个可以生成不可修改视图的方法

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
    return new Collections.UnmodifiableCollection(c);
}

public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
    return new Collections.UnmodifiableSet(s);
}

public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
    return new Collections.UnmodifiableSortedSet(s);
}

public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s) {
    return new Collections.UnmodifiableNavigableSet(s);
}

public static <T> List<T> unmodifiableList(List<? extends T> list) {
    return (List)(list instanceof RandomAccess ? new Collections.UnmodifiableRandomAccessList(list) : new Collections.UnmodifiableList(list));
}

public static <K, V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m) {
    return new Collections.UnmodifiableMap(m);
}

public static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
    return new Collections.UnmodifiableSortedMap(m);
}

public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m) {
    return new Collections.UnmodifiableNavigableMap(m);
}

每个方法都定义处理一个接口。例如，Collections.unmodifiableList处理ArrayList、LinkedList或者实现了List接口的其他类。这个方法会返回一个实现了List接口的类对象，他们是不可更改的。

4.4. 检查型视图

将错误的类型混入泛型集合中的情况极有可能发生

ArrayList<String> strings = new ArrayList<>();
ArrayList a = strings;
a.add(new Date());//no error

这个错误的命令在运行时检查不出来，这时候可以用检查型视图，如果插入的对象不属于指定的类，就会抛出一个ClassCastException异常

ArrayList<String> strings = new ArrayList<>();
List<String> safeStrings = Collections.checkedList(strings, String.class);
ArrayList a = (ArrayList) safeStrings;
a.add(new Date());//抛出异常ClassCastException

5. 算法

在java集合框架中还有一些有用的算法。

5.1. 排序与混排

Collections类的sort方法实现了对List接口的集合进行排序，这个方法假定列表元素实现了Comparable接口。

var staff = new LinkedList<String>();
....
Collections.sort(staff);

或者可以使用List接口的sort方法，不过这个方法需要传进一个Comparator对象。

staff.sort(Comparator a);

如果想按降序对列表进行排序，可以使用静态的遍历方法Collections.reverseOrder()。这个方法将返回一个比较器

staff.sort(Comparator.reverseOeder());

注意：集合类库中的排序不是快速排序！

Collections类中还有一个算法shuffle，其会打乱集合中的顺序，作用与排序相反。

5.2. 二分查找

Collections类中还有个二分查找的方法，不过只适用于随机访问的集合，而对于链表，它会自动地退化为线性查找

Collections类中还有许多简单算法，例如求最大值，最小值，拷贝，交换位置等等。

5.3. 批操作

很多操作会“成批”复制或删除元素。

• a.removeAll(b); 会从a中删除b中出现的所有元素
• a.retainAll(b); 会从a中删除所有未在b中出现的元素

上面的方法是定义在Collection接口中的，Map中没有此方法，不过可以对Map的视图进行操作。

5.4. 集合与数组的转换

如果需要把一个数组转换为一个集合，可以使用List.of

String[] values = ...;
var staff = new HashSet<>(List.of(values));

将一个集合转换为数组会麻烦一些，需要使用toArray方法

staff.toArray(new String[0]);

赏

谢谢你请我吃糖果

支付宝

微信