Java集合

‍

Iterator

集合中的顶级接口，源代码如下

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 (hasNext())
            action.accept(next());
    }
}

包含2个动态方法

循环的时候要先调用hasNext进行判断，然后再调用next

实例1：Iterator遍历

通过操作迭代器来进行集合的遍历

集合中的任何数据结构，都可以使用foreach代替iterator循环。

原因是Collection接口扩展了Iterable接口

public static void main(String[] args) {

    // 模拟Iterator
    var list = Stream.of("Ashe", "Zed", "Yasuo")
            .collect(Collectors.toList());

    // 任何实现了 Iterator<E> 接口的方法，都会有迭代器
    // 获取list的迭代器
    var iterator = list.iterator();

    // 使用迭代器循环
    // 循环输出list，每次调用next方法，都要先判断hasNext
    // 如果没有判断，会抛出NoSuchElementException
    System.out.println("迭代器循环：");
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    // for循环与迭代器循环等价
    System.out.println("foreach循环：");
    for (var element : list) {
        System.out.println(element);
    }
}

‍

实例2：Iterator删除

Iterator 类似于一个指针，或者是SQL中的一个游标：在执行查找操作的同时，迭代器的位置会随之向前移动。可以通过next方法移动到下一个元素

public static void main(String[] args) {

    var list = Stream.of(1, 2, 3, 4, 5, 6, 7).collect(Collectors.toList());
    var iterator = list.iterator();

    // 删除第二个元素，需要移动两次迭代器
    // 这里从第0位移动到了第2位
    iterator.next();
    iterator.next();
    iterator.remove();

    for (var element : list) {
        System.out.println(element);
    }

}

‍

实例3：随机序列产生器

/**
 * 实现随机序列产生器
 */
public class RandomStringGenerator<T> implements Iterable<T> {

    private List<T> list;

    // 构造器
    public RandomStringGenerator(List<T> list) {
        this.list = list;
    }


    @Override
    public Iterator<T> iterator() {

        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {

                return list.get((int) (list.size() * Math.random()));
            }
        };
    }

    public static void main(String[] args) {

        var list = Arrays.asList("List", "Tree", "Array");
        var gen = new RandomStringGenerator<String>(list);

        // 操作迭代器
        var it = gen.iterator();
        for (int i = 0; i < 10; i++) {
            System.out.println(it.next());
        }

//        ArrayList转换成数组
//        ArrayList<String> arr = new ArrayList<String>();
//        arr.add("3");
//        var strArr = arr.toArray(new String[0]);
//        System.out.println(strArr.toString());

        // ArrayList通过构造器转换为数组
//        ArrayList<String> arr = new ArrayList<String>();
//        arr.add("3");
//        // Method Reference ::
//        // 通过这种方式可以访问到数组的构造方法
//        var strArr = arr.toArray(String[]::new);
    }
  
}

‍

总结

1. 从上述实例中可以看出，Iterator接口只具有遍历和删除元素的功能

2. Collection接口继承了Iterable接口，并且提供了查询、判断等等的扩展功能

3. AbstractCollection实现了Collection方法，相当于提供了默认的方法，如果子集合中有更高效的实现可以交给子类提供。

   1. 但是java8以后接口引入了default，这种方式应该交给default方法，充当动态方法，允许子类重写
   2. Abstract方法必须先被继承后，才能够实例化；主要用于当一个类/接口不足以描述一个对象的时候的补充手段，相当于提供默认的实现
   3. Abstract方法，一般用于模板方法设计模式，提供通用的总体算法骨架 以及 具体的业务抽象方法（该方法由子类来实现）

‍

‍

容器框架图

容器：用于容纳一组对象，不能容纳非对象类型，要能够增删改与遍历

容器 Collection 关系图

‍

链表

LinkedList

• 优点：插入、删除元素的开销小
• 缺点：无法随机读取元素
• 场景：适用于查询少、操作多的场景

Java中的链表都是双向链表

public static void main(String[] args) {

   var list = new LinkedList<String>();

   list.add("Ashe");
   list.add("Yasuo");
   list.add("Zed");

   // 获取迭代器
   var iterator = list.iterator();
   String first = iterator.next();
   String second = iterator.next();

    System.out.println("第一个元素: " + first);
    System.out.println("第二个元素: " + second);

    list.remove();
    System.out.println(list);

    // add方法，元素表尾添加
    list.add("NuNu");
    System.out.println(list);

    // 移动指针后，读取前驱
    // ListIterator 扩展了Iterator方法，使其具有add和反向遍历的能力
    var listIterator = list.listIterator();
    listIterator.next();
    System.out.println(listIterator.previous());
}

‍

散列集

适用于快速查找对象，并且不关心集合中元素顺序的场景

public static void main(String[] args) {
    var words = new HashSet<String>();
    long totalTime = 0;

    try (var in = new Scanner(System.in)) {
        while (in.hasNext()) {
            String word = in.next();

            if(word.equals("exit"))
            {
                break;
            }

            long callTime = System.currentTimeMillis();
            words.add(word);
            callTime = System.currentTimeMillis() - callTime;
            totalTime += callTime;
        }
    }

    var iterator = words.iterator();
    for (int i = 1; i < 20 && iterator.hasNext(); i++) {
        System.out.println(iterator.next());
    }

    System.out.println("words size: " + words.size() + " totalTime: " + totalTime);
}

‍

树集

是一个有序集合，输入一个任意顺序的元素，在遍历时会自动按照排序后的顺序呈现

public static void main(String[] args) {

    var treeSet = new TreeSet<Integer>();
    treeSet.add(1);
    treeSet.add(8);
    treeSet.add(3);
    treeSet.add(5);

    System.out.println(treeSet);
}

‍

映射

key-value存储的数据结构，指两组数据的映射关系

通过get()方法获取值，通过put方法设置值，通过remove方法删除值

‍

TreeMap通过一定的顺序来组织元素，而HashMap里的元素则是无序的

TreeMap实例

public static void main(String[] args) {

    var treeMap = new TreeMap<String, String>();

    treeMap.put("1", "Yasuo");
    treeMap.put("8", "Ashe");
    treeMap.put("5","NuNu");
    treeMap.put("2","Zed");

    System.out.println(treeMap);

    // 获取键集合
    var keys = treeMap.keySet();
    System.out.println("All keys: " + keys.toString());

    // 获取值集合
    var values = treeMap.values();
    System.out.println("All values: " + values.toString());

    // 获取键&值集合
    System.out.println("All Key & Value: ");
    var entrySet = treeMap.entrySet();
    treeMap.forEach((k,v) -> {
        System.out.println("key: " + k + " value: " + v);
    });
}

‍

链接散列集与映射

#TODO# LinkedHashSet & LinkedHashMap

‍

实现LRU缓存

LRU(Least Recently Used)缓存：最近最少使用，页面被置换

为什么选择LinkedHashMap

• 链表能够实现队列，完成先进先出的逻辑
• <K,V>的映射能够通过Key来索引数据

/**
 * 使用 LinkedHashMap 实现LRU缓存
 */
public class LRUCache<K, V> implements Iterable<K> {

    int MAX = 3;

    LinkedHashMap<K, V> cache = new LinkedHashMap<>();

    public void cache(K key, V value) {
        // 根据LRU，如果key已经存在，则先删除，然后从最右边入队
        if (cache.containsKey(key)) {
            cache.remove(key);
        }
        // 当cache已满，移除最左边的元素
        else if (cache.size() >= MAX) {
            // 获取迭代器
            var it = cache.keySet().iterator();
            // 通过迭代器获取第一位元素（即最左边元素），并移除
            var first = it.next();
            cache.remove(first);
        }
        cache.put(key, value);
    }

    @Override
    public Iterator<K> iterator() {

        var it = cache.entrySet().iterator();

        return new Iterator<K>() {
            @Override
            public boolean hasNext() {
                return it.hasNext();
            }

            @Override
            public K next() {
                return it.next().getKey();
            }
        };
    }

    // main function
    public static void main(String[] args) {

        var lru = new LRUCache<String, Integer>();
        lru.cache("A", 1);
        lru.cache("B", 2);
        lru.cache("C", 3);

        lru.cache("D", 4);
        lru.cache("C", 10);

        System.out.println(
                "leave <-" +
                StreamSupport.stream(lru.spliterator(), false)
                        .map(x -> x.toString())
                        .collect(Collectors.joining("<-")));
    }
}

‍

HashMap & HashTable

#TODO# HashMap & HashTable

‍

容器的工厂方法

Java9 新特性：of与ofEntries

public static void main(String[] args) {

    // List
    // 该List是可变的
    var list = new ArrayList<>(List.of(1,2,3,4,5));

    // Set
    var  set = Set.of(1,2,3,4);

    // Map
    Map<String,Integer> map = ofEntries(
            entry("Ashe",1),
            entry("Zed",2),
            entry("Yasuo",3)
    );

}

注意：工厂方法创建出来的集合对象都是不可变的，但是以下方式可以构造一个可变的集合

var list = new ArrayList<>(List.of(1,2,3,4,5));

‍

Arrays.asList

Arrays.asList 被称为不可变集合，该集合中元素可以更改，但是大小不可变

1.通过 Arrays.asList() 方法构造出来的list，不能执行add()和remove()。

这里的list，并非 java.util.ArrayList，它没有重写父类AbstractList的方法。

2.如果使用Arrays.asList()生成新的数组，那么修改的内容也会同步影响到旧数组上。

总结：尽量用于测试，不要用于开发业务上。

‍