java 集合系列、算法

目录1. 接口与实现分离2. 迭代器2. Collection接口3. 集合框架中的接口4. 详细的集合4.1 链表4.2 数组列表4.3 散列集4.4 树集4.5 队列、双端队列、优先级队列5. 映射5.1 映射的基本API5.2 映射视图5.3 弱散列映射5.4 链接散列集与映射5.5 标识散列映射6. 算法6.1 排序...

讲不出再见

533人浏览 · 2020-02-05 16:40:30

讲不出再见 · 2020-02-05 16:40:30 发布

1. 接口与实现分离

java集合类库分为集合接口和实现，一个集合接口可能对应多种实现，但是功能是同一个意义。

为什么会有多种实现呢？每种实现都各有优势和独到之处，因此，按照需要选择合适的实现方法。

比如：Map<Stirng, String> a = new HashMap<>(); 选择了HashMap实现；

Map<String, String> a = new ConcurrentHashMap<>()；选择了ConcurrentHashMap实现。

2. 迭代器

遍历集合的元素，访问顺序取决于集合类型，ArrayList就是从下标0开始顺序，HashSet就按照某种随机次序出现。

public interface Iterator<E> {
    /**是否到末尾了，还有下一个元素吗？有的话，返回true，没有就返回false  */
    boolean hasNext();

    /**
     * 获取下一个元素，如果超出范围，就报错 NoSuchElementException
     */
    E next();

    /**
     * 删除迭代器当前所指的元素
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * 遍历集合的每个元素，用这个方法就行，配合lambda表达式，一般还是用循环来遍历要清晰一些
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

2. Collection接口

集合类的基本接口是Collection接口。接口中定义的方法如下：

3. 集合框架中的接口

4. 详细的集合

4.1 链表

数组和数组列表都不够灵活，添加和删除元素，都会导致大量元素向后移动和向前移动。而此时就显示出链表的优势了。

LinkedList 链表实现类，一个顺序链表。

Iterator 是迭代器，功能比较单一，能够遍历集合的每个元素。

ListIterator 是链表迭代器，继承于Iterator，有一个add()方法，用于在迭代器当前所指位置添加元素。还可以反向遍历链表，

E previous() 方法是从链表尾开始遍历，相当于next()， hasPrevious() 方法判断是否还有下一个元素，相当于hasNext()方法。

下面的代码将"wwww"添加到了第一个位置，要执行一次next()方法，以便让迭代器指向第一个位置。

LinkedList<String> list = new LinkedList<>();
list.add("aaaa");
list.add("bbbb");
ListIteratot iterator = list.listIterator();
iterator.next();
iterator.add("wwww");

需要添加元素到表头时，需要迭代器指向表头，当需要添加元素到链表尾的时候，需要迭代器越过最后一个元素（即hasNext返回false）。

如果一个迭代器发现它的集合被另一个迭代器修改了，或者被该集合自身的方法修改了，就会抛出一个ConcurrentModificationException异常。

List的方法：即使可以直接在指定位置添加元素，但是底层也是一个位置一个位置的移动，直到处于指定位置。

ListIterator的方法：

LinkedList的方法：

4.2 数组列表

之前已经介绍过了，请查看https://blog.csdn.net/dgh112233/article/details/104146032

4.3 散列集

链表和数组都是有次序的结构，数组可以按照下标任意访问元素，但是插入元素和删除元素时，开销大；链表非常适合插入、删除元素频繁的场景，但是访问元素需要从头到尾一个一个移动，直到找到，不能直接访问；散列集是一种没有次序的集合，但是可以快速的查找元素。

散列表为每个对象计算一个整数（散列码），散列码是由对象的实例域产生的一个值。

HashMap的工作原理：https://blog.csdn.net/dancer_one/article/details/82845092

4.4 树集

树集是一种以二叉树方式存储元素的集合，优点：不用我们特地排序，每当我们改变树集后，它都会自动调整好顺序，因此迭代器总能顺序地访问元素；缺点：元素之间的比较开销，因为要排序。

树集的使用，需要注意元素之间一定要能够比较，否则，无法比较，无法排序，就是失去了树集的意义了。

TreeSet 和 TreeMap类是树集。

4.5 队列、双端队列、优先级队列

队列是只允许在尾部添加元素，在开头删除元素。

双端队列允许在开头和尾部删除、添加元素。Deque接口的实现类有ArrayDeque和LinkedList，都提供了双端队列。

下面给出接口的方法，以了解双端队列都有哪些操作 Deque接口的方法：

ArrayDeque类都实现了上面的方法，另外，队列默认长度是16，可以在构造的时候，设置初始化大小。

优先级队列 PriorityQueue 类：优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索，也就是说，无论何时调用remove方法，总会获得当前优先级队列中最小的元素。优先级队列并没有对所有的元素进行排序，如果进行迭代，并不需要排序。优先级队列采用的数据结构是“堆”。

这个类有很多操作方法，大致都差不多。

5. 映射

5.1 映射的基本API

Map接口的方法，通过这些方法，基本可以知道映射有哪些操作：

HashMap和TreeMap类的构造方法：

5.2 映射视图

映射有3中视图：键集、值集、键/值对集。

5.3 弱散列映射

首先说一说几种引用：

1. 强引用。我们一般情况下，默认用的就是强引用，当垃圾回收器是永远不会回收强引用对应的对象，即便内存溢出。

2. 软引用。当垃圾回收器要进行回收垃圾时，会将软引用对应的对象列入下次回收的清单中，下次才会去清除它（除非该对象又被激活了）。

3. 弱引用。当垃圾回收器要进行垃圾回收时，如果对象只被弱引用所引用，那么就回收它。

4. 虚引用。一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来获取一个对象的实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。虚引用和弱引用对关联对象的回收都不会产生影响，如果只有虚引用活着弱引用关联着对象，那么这个对象就会被回收。

弱散列映射 WeakHashMap：和弱引用类似，为了更好的管理内存空间，只不过不是将整个映射都清除掉，而是将映射中那些已经没法使用的键值对（在垃圾回收时）清除掉，比如有一个值，对应的键已经不再被使用（即找不到该键的引用，没法使用）。

5.4 链接散列集与映射

LinkedHashSet 和 LinkedHashMap 类用于记住插入元素的顺序，可以通过键迅速找到值，同时链接散列集中存储的元素是有顺序的。这种结构对于实现高速缓存的“最近最少使用”原则很有用。

5.5 标识散列映射

类IdentityHashMap和HashMap的功能一样，不过，IdentityHashMap的键的散列值不是用hashCode函数计算的，而是用System.identityHashCode 方法计算的，是根据对象的存储地址来计算的，即使两个对象内容一样，但是存储地址不同，计算出的hashCode也不同。

6. 算法

6.1 排序

Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。此接口只有一个方法compareTo，比较此对象与指定对象的顺序，如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

Collection类中的sort方法可以对实现了List接口的集合进行排序，排序的规则就是按照compareTo方法来的。

List<Integer> aaa = new ArrayList<>(); Collection.sort(aaa); 按照比较规则的升序进行排序。

还可以使用List接口的sort()方法。Comparator类有一些方法可用于比较一些字段。Comparator类的排序功能内容是参考的别人的文章：https://www.jianshu.com/p/3f621e51f306

对整数列表排序（升序）

List<Integer> list = Arrays.asList(1, 4, 2, 6, 2, 8);
list.sort(Comparator.naturalOrder());

对整数列表排序（降序）

List<Integer> list = Arrays.asList(1, 4, 2, 6, 2, 8); 
list.sort(Comparator.reverseOrder());

根据对象属性（年龄）进行排序

        List<Person> personList = new ArrayList<>();
        personList.add(new Person("a", 2));
        personList.add(new Person("b", 4));
        personList.add(new Person("c", 7));
        // 升序
        personList.sort(Comparator.comparingInt(Person::getAge));
        // 降序
        personList.sort(Comparator.comparingInt(Person::getAge).reversed());

根据对象属性（价格、速度）进行排序，需要注意的是，排序有先后之分，不同的顺序会导致不同的结果

        List<Computer> list = new ArrayList<>();
        list.add(new Computer("xiaomi",4000,6));
        list.add(new Computer("sony",5000,4));
        list.add(new Computer("dell",4000,5));
        list.add(new Computer("mac",6000,8));
        list.add(new Computer("micro",5000,6));
        // 先以价格（升序）、后再速度（升序）
   list.sort(Comparator.comparingInt(Computer::getPrice).thenComparingInt(Computer::getSpeed));
        // 先以速度（降序）、后再价格（升序）
     list.sort(Comparator.comparingInt(Computer::getSpeed).reversed().thenComparingInt(Computer::getPrice));
        // 先以价格（降序）、后再速度（降序）
        list.sort(Comparator.comparingInt(Computer::getPrice).thenComparingInt(Computer::getSpeed).reversed());
        System.out.println(list);

6.2 二分查找

如果序列是有序的，二分查找方法才有效。

Collections 类的binarySearch静态方法能够实现二分查找。如果一个集合是可以随机访问的，那么二分查找才有意义，如果必须要挨个挨个遍历地去访问集合中的元素的话，那么二分查找就没有意义了，binarySearch方法会自动将它变成线性查找（一个一个找，直到找到为止）。

binarySearch方法返回的是int值，表示匹配对象的索引（位置），大于等于0，即找到了，小于0，即没有找到。

static <T extends Comparable<? super T>> int binarySearch(List<T> elements, T element); 如果集合实现了Comparable接口的compareTo方法，即元素有比较的规则，就可以比较；第一个参数是实现了List接口的集合，第二个参数是要查找的内容。

static <T> int binarySearch(List<T> elements, T element, Comparator<? super T> c); 如果集合没有实现了Comparable接口的compareTo方法，即元素没有比较的规则，就没法正确比较，就用这个方法；第一个参数是实现了List接口的集合，第二个参数是要查找的内容，第三个参数是比较器对象（规定比较的规则）。

如果返回的负数n，表示集合中没有要找的元素，如果此时将此元素插入 -n-1 位置处，集合的顺序仍不会变。

6.3 关于集合的常用算法

Collections类中的常用算法：

Collection接口的算法方法：

List接口的算法方法：

6.4 集合与数组的转换

数组转换成集合，比如：String[] aaa = {"hello", "how"}; HashSet<String> ss = new HashSet<>(Arrays.asList(aaa));

集合转换成数组，比如：2种方法都行。

       List<BB> list = new ArrayList<>();
       list.add(new BB("aa", 23));
       list.add(new BB("bb", 12));
       list.add(new BB("cc", 56));
//       BB[] aa = list.toArray(new BB[0]);
       BB[] aa = list.toArray(new BB[list.size()]);