JavaCoreOne-C09Collection

2023-07-08 2930 words 6 minutes

Contents

1. Java集合框架

Java设计者们想设计一组轻量的完善的数据结构, 它不可以有C++STL那样的复杂, 但同时具备泛型算法的优点。在Java类库中, 集合类的接口(interface)和实现(implementation)分离, 例如对于一个队列Queue来说, 它可以在队尾插入元素, 从队头剔除元素, 以及获取队列元素个数, 可以设计一个接口:

public Interface Queue<E>{
    void add(E e);
    E remove();
    int size();
}

然而其实现可以有不同的方式, 例如使用循环数组(模数)或者链表. 需要注意的是, 循环数组的实现是一个有界集合, 当集合手机的对象数量无上限时最好使用链表的实现方式. 在Java中, 这两种实现分别对应 ArrayDeque 和 LinkedList, 当然它们还有其他的特性.

1.1 Collection 接口

Java所有的集合都实现了Collection接口, 包含两个核心方法:

public Interface Collection<E>{
    void add(E e);
    Iterator<E> iterator();
    ...
}

add()用于向集合中添加元素, 而 Iterator 接口包含以下方法:

public Interface Iterator<E>{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action);
}

可以通过next()访问到集合的每一个元素, 而hasNext()判断是否达到边界, 也可以使用for-each语法遍历:

// iterator
Collection<String> astr = ...;
Iterator<String> it = astr.iterator();
while(it.hasNext()){
    String ele = it.next();
    ...
}
// for-each
for(String s: astr){
    ...
}

next()方法返回当前元素引用, 并把指针移动到下一个元素(如果有) remove()删除next()方法返回的元素, 例如调用next()方法返回第一个元素, 指针移到第二个元素, 接着调用remove()方法就删除了第一个元素, 不能连续的调用remove方法, 实际上, 必须先调用next()越过将要删除的元素.

1.2 Collection 基本方法

Java所有的集合都实现了 Collection接口, 该接口有一些必须实现的方法:

int size();
boolean isEmpty();
boolean contains(Object obj)
boolean containsAll(Collection<?> c)
boolean equals(Object other)
boolean addAll(Collection<? extends E> c)
boolean remove(Object obj);
boolean removeAll(Collection<?> c);
boolean clear();
boolean reatinAll(Collection<?> c);
Object[] toArray();
<T> T[] toArray(T[] arrayToFill);

这些方法在所有集合中均适用, 另一方面也意味着实现 Collection接口就要实现这些方法, 为了简化实现, Java提供了 AbstractCollection, 他保持了基础方法 size 和 iterator 为抽象方法, 但其他方法已经被实现, Collection增添了许多其他默认方法, 大多与流处理相关.

2 集合

2.1 Sequence

LinkedList: 插入和删除高效的顺序表 ArrayList: 可以动态增长的随机访问顺序表 ArrayDeque: 使用循环数组作为底层实现的双端队列 PriorityQueue: 使用小顶堆的优先队列, 无论何时调用remove方法, 总会获得当前队列中最小的元素

ListIterator() 包含add方法, 以及previous()和hasPrevious()方法可用于反向遍历

堆是一个自组织的二叉树, add 和 remove 方法总是保持队列的最小元素作为堆顶, 其典型用法包括任务调度如下展示了 PriorityQueue 的使用方法:

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<LocalDate> dates = new PriorityQueue<>();
        dates.add(LocalDate.now());
        dates.add(LocalDate.of(2023, 5, 20));
        dates.add(LocalDate.of(2022, 12, 25));
        dates.add(LocalDate.of(2018, 6, 7));
        dates.add(LocalDate.of(2021, 8, 13));
        // 1. use iterator to traverse (for-each)
        for (LocalDate date : dates) {
            System.out.println(date);
        }
        System.out.println("----------------");
        // 2. use remove
        while (!dates.isEmpty()){
            System.out.println(dates.remove());     // remove the top of the heap
        }
    }
}
/*
2018-06-07
2021-08-13
2023-05-20
2023-07-12
2022-12-25
----------------
2018-06-07
2021-08-13
2022-12-25
2023-05-20
2023-07-12
*/

2.2 Set

HashSet: 无重复元素的集合 TreeSet: 有序集, 红黑树实现 LinkedHashSet: 通过添加链接以记住插入顺序

散列表可以用于快速的查找对象, 这就是散列表, 它通过元素内容本身生成元素的存储地址, 因此可以以常数时间查找到元素.

Java使用链表数组实现, 首先他是一个数组, 其次数组的每个元素是一个链表, 假设一个元素的散列码为108, 则访问第108个桶(链表), 并把该元素附到链表尾部.

标准类库散列表的桶数量为2的幂, 衡量散列表的空满程度使用装填因子a, 也即非空桶的占比, 当散列表太满(例如a>=0.75)时就需要再散列. 此时自动将桶数扩展为两倍, 并重新整理元素.

例: 无重复地统计txt文件的单词总数并计时

public class SetTest {
    public static void main(String[] args) {
        // 读取一个txt文件并计算其中单词出现的数量
        // 同时计算 add 操作的耗时(ms)
        HashSet<String> wordTable = new HashSet<>();
        long totalTime = 0;
        try(var in = new Scanner(System.in)){
            while (in.hasNext()){
                String word = in.next();
                long callTime = System.currentTimeMillis();
                wordTable.add(word);
                long interval = System.currentTimeMillis()-callTime;
                totalTime += interval;
            }
        }
        Iterator<String> it = wordTable.iterator();
        for(int i=0; i<12&&it.hasNext(); i++){
            System.out.println(it.next());
        }
        System.out.println("... ...");
        System.out.println("Total words: " + wordTable.size());
        System.out.println("Total time(ms): " + totalTime);
    }
}

运行方法: java SetTest.java < abc.txt code\collection\set>java SetTest.java < ..\..\..\txt\TheEnchantedApril.txt

比较使用HashSet和TreeSet Total words: 11976 HashSet: Total time(ms): 14 TreeSet: Total time(ms): 22

通常, 给出对象的散列构造比给出其比较方法更简单, 除非一些必要的情况, 应优先考虑 HashSet

例: 将 Item 对象按照不同的法则添加到 TreeSet:

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Item> itemTreeSet = new TreeSet<>();
        // 1. 添加几个 Item 对象
        itemTreeSet.add(new Item("Flower", 192));
        itemTreeSet.add(new Item("Dance", 179));
        itemTreeSet.add(new Item("Ally", 237));
        itemTreeSet.add(new Item("Weird", 184));
        itemTreeSet.add(new Item("Bundle", 192));
        System.out.println(itemTreeSet);

        // 2. 按照 description 重排
        TreeSet<Item> sortByDes = new TreeSet<>(Comparator.comparing(Item::getDescription));
        sortByDes.addAll(itemTreeSet);
        System.out.println(sortByDes);
    }
}

Item

public class Item implements Comparable<Item>{
    private String description;
    private Integer partNumber;

    public Item(String description, Integer partNumber) {
        this.description = description;
        this.partNumber = partNumber;
    }

    @Override
    public String toString() {
        return "Item{" +
                "description='" + description + '\'' +
                ", partNumber=" + partNumber +
                '}';
    }

    @Override
    public int compareTo(Item o) {
        // 优先比较 partNumber, 然后是 description
        int diff = partNumber - o.partNumber;
        return diff != 0 ? diff:description.compareTo(o.description);
    }

    public String getDescription() {
        return description;
    }
}

3. 映射(Map)

HashMap: 无重复元素的集合 TreeMap: 有序集 LinkedHashMap: 通过添加链接以记住插入顺序

Map是存放键值对的集合, 但注意它不是集合, 也就是Map与Collection相互独立。使用 put 将键值对(kv)放入集合, 使用get(k)获取键值对, 如果不存在k则返回null, 另一个方法是 getorDefault(k, default) , 如果不存在k则返回default。Map中各键值对的键必须唯一, 如果对同一个键使用两次put方法, 后一次的值会覆盖前者, 实际上put返回键参数上一次关联的键值. 示例 put, remove, foreach test,

public class MapTest {
    public static void main(String[] args) {
        // 1. 创建一个 Map
        Map<Integer, Item> itemMap = new HashMap<>();
        // 2. put new kv pair
        itemMap.put(1238, new Item("qoehfo", 1290));
        itemMap.put(3984, new Item("woiedd", 2923));
        itemMap.put(2190, new Item("qwefqw", 9203));
        itemMap.put(9823, new Item("wiheed", 1345));
        itemMap.put(2098, new Item("hwerfw", 5433));
        itemMap.put(9382, new Item("ag4tge", 1343));
        // 3. print it
        System.out.println(itemMap);
        System.out.println("---------------");
        // 4. look up
        System.out.println(itemMap.get(1209));
        System.out.println(itemMap.getOrDefault(1209, new Item("0", 0)));
        System.out.println(itemMap.get(2190));
        System.out.println("---------------");
        // 5. update
        Item orig = itemMap.put(2190, new Item("wodonw", 1203));
        System.out.println(itemMap);
        System.out.println(orig);
        System.out.println("---------------");
        // 5. remove, foreach
        itemMap.remove(2098);
        itemMap.forEach((k, v)->{
            System.out.println("key: "+k+", value: "+v);
        });
    }
}

考虑这个问题: 统计txt文件的每个单词的出现次数并计时关键语句是: count.put(word, count.get(word)+1) 然而如果单词首次出现呢, 此时get返回null值, 程序报错, 一种办法是利用 getOrDefault. 不过这里介绍一个新办法: counts.merge(word, 1, Integer::sum); 意思是把word和1关联, 否则使用sum将二者结合(求和)

public class WordFreq {
    public static void main(String[] args) {
        Map<String, Integer> wordTable = new TreeMap<>();
        long totalTime = 0;
        try(Scanner scanner = new Scanner(System.in)){
            while (scanner.hasNext()){
                String word = scanner.next();
                long ct = System.currentTimeMillis();
                wordTable.merge(word, 1, Integer::sum);
                long interval = System.currentTimeMillis()-ct;
                totalTime += interval;
            }
        }
        // 可以获取 Map.Entry, 从而实现仅访问前几个元素
        Set<Map.Entry<String, Integer>> wordEntries = wordTable.entrySet();
        Iterator<Map.Entry<String, Integer>> it = wordEntries.iterator();
        for(int i=0; i<12&&it.hasNext(); i++){
            System.out.println(it.next());
        }
        System.out.println("... ...");
        System.out.println("Total words: " + wordTable.size());
        System.out.println("Total time(ms): " + totalTime);
    }
}
// JavaCoreOne\code\collection\map>java WordFreq.java < ..\..\..\txt\test.txt

Map有三个视图(实现了Collection接口或者子接口) Set<K> keySet() Collection<V> values() Set<Map.Entry<K, V>> entrySet

缓存

LinkedHashMap, 它引入额外的指针以记住插入顺序, 另一方面, 它也可以按照访问顺序来迭代映射条目: 每次调用get或者put时, 影响到的条目会被删除并放到链表尾部(仍处于原来的桶)。这样访问最少的元素将留在链表前端, 可以把访问频率高的放在内存而低的放在数据库, 还可以规定映射条目最大数量, 使得访问频率低的自动移除:

var cache = new LinkedHashMap<K, V>(128, 0.75, true){
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest){
        return size() > 100;
    }
}

视图与包装器

keySet()返回值并非HashSet或者TreeSet，而是一个实现了Set接口的类对象, 通过这个类的方法操作原映射, 这被称为视图(view)

生成给定元素的集合:

List<String> aList = List.of("Peter", "Paul", "Mary");
System.out.println(aList);

它们都是不可变的, 不可增删元素也不可修改内容. 可以传入构造器以得到可修改的集合.

注意在IDEA运行时, 请确保项目设置以及编译器设置的JDK版本高于8, 例如JDK17 子视图 subList(start, end): 获取原集合范围是[start, end)的子视图, 对子视图的修改会影响原始图, 例如clear()

集合算法(Collections)

泛型算法: 一次编写, 多处使用

java的排序算法使用归并排序, 慢一些但稳定. 一些概念: 可修改的(modifiable), 支持set方法可改变大小的(resizable), 支持add和remove方法

List<Item> itemList = new ArrayList<>();
itemList.add(new Item("Flower", 192));
itemList.add(new Item("Dance", 179));
itemList.add(new Item("Ally", 237));
itemList.add(new Item("Weird", 184));
itemList.add(new Item("Bundle", 192));

// 1. sort, 排序, 若为链表实现, 则先复制到数组
Collections.sort(itemList);
itemList.sort(Comparator.comparing(Item::getDescription));   // 依据某一字段排序
itemList.sort(Comparator.reverseOrder()); // 倒排
itemList.sort(Comparator.comparing(Item::getDescription).reverseOrder());   // 依据某一字段倒排

// 2. shuffle
Collections.shuffle(itemList);  // 打乱集合

// 3. 在有序列表中二分查找
// Collections.binarySearch(itemList, xxx, Comparator) -> index(if exists)
// 如果没有匹配的元素, (-i-1) 将指明新元素的插入位置

// 4. Collections还有许多方法, 可以翻阅书籍