Java编程原理——泛型和容器

1 泛型

1.1 基本概念

1. 泛型实际上就是将类型参数化，处理的数据类型不是固定的，而是可以作为参数传入；
2. Java的泛型实际上通过Java编译器对泛型字符做类型擦除实现的；
3. 泛型可以指定上限为某个具体类，例如：

public class NumberPair<U extends Number, V extends Number> extends Pair<U, V>{
    public NumberPair(U first, V second) {
        super(first, second);
    }
}

1. 除此之外，也可以指定上界为某个接口，例如Java中的max方法需要实现Comparable接口；
2. 总结：泛型是计算机中一种非常重要的思维方式，它将数据结构和算法与数据类型进行分离，使得同一套数据结构和算法能够应用于各种数据类型，而且可以保证类型安全，提高可读性。

1.2 通配符解析

1. 参数类型限定通配符写法。例如：public void addAll(DynamicArray<? extends E> c), <? exntends E>也称为有限定通配符；
2. 与之相对应的就为无限定通配符，具体为：Dynamic<?>，更简洁的写法就为
3. 但是通配符存在一个重要限制：只能读，不能写，由于类型安全无知，因此Java编译器一般是不允许写入，所以干脆禁止；
4. 通配符的形式都可以使用类型参数的形式来替代，通配符能做的，用类型参数都可以做；
5. 通配符的形式可以减少类型参数，形式上往往更为简单，可读性也更好；因此能使用通配符就使用通配符；
6. 如果类型参数之间有依赖关系，或者返回依赖类型参数，或者需要写操作，则只能使用类型参数；
7. 通配符形式和类型参数往往配合使用；

1.3 超类型通配符

1. 形式：<? super E>，用于表示E的某个父类类型；
2. 使用场景：对于有限通配符形式<? extends E>在无法满足工作需要时，可以使用<? super E>代替；
3. <? super E>用于灵活写入或比较，<?>或<? exntends E>用于灵活读取；

1.4 局限性

1. 基本类型不能用于实例化类型参数；
2. 运行时类型信息不适用泛型；
3. 类型擦除可能引起一些冲突，因此泛型中不能使用基本类型，要使用基本类型对应的包装类型；
4. 不能通过类型参数创建对象；
5. 泛型类类型参数不能用于创建静态变量和方法；
6. 不能创建泛型数组，因为一旦创建泛型数组既不会产生编译错误，也不会产生运行异常，但确是非常危险的；
7. 如果要存放泛型对象，可以使用原始类型的数组，或者是用泛型容器；
8. 泛型容器内部使用Object数组，如果要转换泛型容器为对应类型的数组，需要使用反射；

2 列表和队列

2.1 ArrayList

1. ArrayList为动态数组，其内部使用了一个Object类型的数组，默认容量为10，可以通过构造函数更改其初始容量；
2. ArrayList实现了Iterable接口，Iterable表示可迭代，凡是实现了Iterable接口的容器类均可以使用foreach语法，Java编译器会将其转换成调用Iterable接口中的Iterator方法；
3. 迭代陷阱：由于迭代器内部会维护一些索引位置相关的数据，要求在迭代过程中，容器不能发生结构性变化。否则索引位置就失效了，因此会出现ConcurrentModificationException异常。如果需要删除容器中间的元素，需使用iterator的remove方法。

/* 错误写法 */
public void remove(ArrayList<Integer> list) {
    for (Integer a : list) {
        if (a < 100) {
            list.remove(a); // 恐抛出ConcurrentModificationException
        }
    }
}

/* 正确写法 */
public void remove(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        if (it.next() < 100) {
            it.remove();
        }
    }
}

1. 使用迭代器的好处：迭代器表示的是一种关注点分离的思想，将数据和实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式。从封装思路上讲，迭代器封装了各种数据组织方式的迭代操作，提供了简单一致性的接口。
2. ArrayList的特点

• 随机访问：按照索引位置访问效率非常高，时间复杂度为O(1)；
• 除非数组已排序，否则按照内容查找元素效率比较低，具体为O(N)，也就是说性能与长度成正比；
• 添加数组元素的效率为O(N)；
• 插入和删除的效率较低，如果是在数组首部插入或者删除元素，需要对整个数组中的元素进行移动，具体为O(N)；
• 需要说明的是ArrayList不是线程安全的，在不需要线程安全的场景下推荐使用ArrayList；

2.2 LinkedList

1. LinkedList是使用数据结构中的单链表来实现的，因此插入和删除的性能很高，但是随机访问的效率就很低；
2. LinkedList除了实现Collection接口，还实现了Queue接口，因此对于队列可以这样使用：

Queue<String> queue = new LinkedList<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
while(queue.peek() != null) {
    System.out.println(queue.poll());
}

1. LinkedList也可以当作栈使用，示例如下：

Deque<String> stack = new LinkedList<>();
stack.push("a");
stack.push("b");
stack.push("c");
while(stack.peek() != null) {
    System.out.println(stack.pop());
}

1. LinkedList的用法和ArrayList类似，与ArrayList不同的是，LinkedList既可以用作队列也可以用作栈；
2. LinkedList的特点如下：

• 按需分配空间，不需要预先分配很多空间；
• 不可随机访问，按照索引位置访问效率较低；
• 无论列表是否有序，按内容查找都需要逐个查找；
• 在两端进行添加、删除操作效率很高；

2.3 ArrayDeque

1. ArrayDeque是基于数组实现的双端队列
2. ArrayDeque内部使用了一种叫做“循环数组”的结构，通过head和tail指针实现数据的插入和删除。循环数组的长度是2的幂次方。以及使用高效的位运算实现高效。
3. 由于是双端队列因此具备下列特点：

• 在两端添加和删除的效率很高；
• 根据元素的内容查找和删除的效率很低；
• 与ArrayList和LinkedList不同的是，没有索引位置的概念，不能根据索引位置进行操作。

3 Map和Set

3.1 HashMap

1. 创建的HashMap默认容量为16，默认因子为0.75，因此阈值为16 * 0.75 = 12
2. 创建Map保存数据的几个步骤分别为：

• (1) 计算键的哈希值；
• (2) 根据哈希值得到保存位置（取模）；
• (3) 插到对应位置的链表表头或者更新已有值；
• (4) 根据扩展table大小，注意这里的table是Entry类型；

1. 总结HashMap的实现原理

• HashMap内部有一个哈希表，每个元素指向一个单链表；
• 根据键值对操作实际上就是用键计算hash值，取模得到数组中的索引位置；然后操作哈希表中指向的单链表；
• 存取时依据键的hash值，只在对应的链表中操作，不会访问其他链表。对应链表操作时也是先计算hash值，当哈希值相同时再使用equals方法比较
• HashMap是无顺序的，所有的键值对都是随机排列的，如果希望Map中的数据有序排列，可以使用LinkedHashMap；
• HashMap不是线程安全的，因此在不需要高并发的场景下推荐使用HashMap，如果是在高并发场景，可以使用Java8中新增的ConcurrentHashMap对象；

3.2 HashSet

1. Set表示没有重复元素并且无序的容器接口，与数学中的集合概念吻合；
2. HashSet有下列应用场景

• 排重：如果对排重后的元素无顺序要求，可以使用HashSet进行排重；
• 保存特殊值：例如维护IP地址的黑名单和白名单，可以使用HashSet；
• 集合运算：方便进行数学中的交集以及并集的集合运算；

1. HashSet内部使用的是HashMap实现，内部都包含一个HashMap的实例变量；
2. 总结HashSet的特点有如下几个：

• 没有重复元素；
• 可以高效的添加、删除元素、判断元素是否存在；
• 没有顺序；

3.3 TreeMap或TreeSet

1. 与HashMap无序相对比，TreeMap是有序的。
2. TreeMap内部使用的是红黑树实现的；
3. TreeMap的特点如下

• 按键有序：可以很方便地根据键的顺序进行查找
• 为了使得按键有序，TreeMap要求键实现Comparable接口或者通过构造方法提供一个Comparator对象；
• 根据键值保存、查找、删除的效率比较高；

1. 总结TreeSet的特点有如下几个：

• 没有重复元素；
• 可以高效地添加、删除元素、判断元素是否存在；
• 有顺序，可以根据自己实现Comparator方法达到正序或者逆序排列；

3.4 LinkedHashMap

1. LinkedHashMap存在两种顺序，一种是插入顺序（先插入的元素在前面），一种是访问顺序（最近访问的元素会移动到末尾，最开始的是没被访问的）；
2. LinkedHashMap是有序的，例子如下(插入顺序)：

Map<String, Integer> seqMap = new LinkedHashMap<>();
seqMap.put("c", 100);
seqMap.put("d", 200);
seqMap.put("a", 500);
seqMap.put("d", 300);
for (Entry<String, Integer> entry : seqMap.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}
/*
Result is :
c 100
d 300
a 500
*/

1. LinkedHashMap的访问顺序：

Map<String, Integer> accessMap = new LinkedHashMap<>(16, 0.75, true);
accessMap.put("c", 100);
accessMap.put("d", 200);
accessMap.put("a", 500);
accessMap.get("c");
accessMap.put("d", 300);
for (Entry<String, Integer> entry : accessMap.getEntrySet()){
    System.out.println(entry.getKey() + " " + entry.getValue());
}
/*
Result is : 
a 500
c 100
d 300
*/

1. LinkedHashMap可以应用于缓存，例如LRU缓存，下面贴出一个LRU缓存的简单实现：

// 实现代码
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxEntries;
    public LRUCache(int maxEntries) {
        super(16, 0.75f, true);
        this.maxEntries = maxEntries;
    }
    
    @Override
    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}
// 使用示例
LRUCache<String, Object> cache = new LRUCache<>(3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.get("a");
cache.put("d", "call");
System.out.println(cache);

// 输出结果
{c=call, a=abstract, d=call}

3.5 EnumMap

1. 键类型为枚举类型，除了可以使用基本的HashMap，也可以使用EnumMap；
2. EnumMap的好处在于，Map的所有键都是预先定义的，其次是枚举能保证一定的顺序性。示例如下：

public enum Size {
    SMALL, MEDIUM, LARGE
}

public class Clothes {
    String id;
    Size size;
}

public static Map<Size, Integer> countBySize(List<Clothes> clothes) {
    Map<Size, Integer> map = new EnumMap<>(Size.class);
    for (Clothes c : clothes) {
        Size size = c.getSize();
        Integer count = map.get(size);
        if (count != null) {
            map.put(size, count + 1);
        } else {
            map.put(size, 1);
        }
    }
    return map;
}

1. EnumSet使用了极为精简和高效的位向量实现，位向量是计算机程序中解决问题的一种方式。
2. EnumSet不能通过new的方式创建，如果需要创建EnumSet对象，需要调用其内部的静态工厂方法；
3. 位向量是用一个位表示一个元素的状态，用一组位表示一个集合的状态，每个位对应一个元素，而状态只可能有两种。
4. 对于只有两种状态，且需要进行集合运算的数据、使用位向量进行表示、位运算进行处理。是计算机程序中常用的思维方式。

4 堆与优先级队列

4.1 完全二叉树

1. 完全二叉树的特点：给定任意一个节点，可以根据其编号直接快速计算出其父节点和孩子节点的编号。例如：如果节点编号为i，则父亲节点编号为i / 2，左孩子的节点编号为2 * i，右孩子节点编号为2 * i + 1;
2. 基于上述特点，完全二叉树可以很方便的存储到一个连续数组中；

4.2 PriorityQueue

1. PriorityQueue内部使用堆实现，可以实现很高的存取效率，逐个出队列可以得到有序，但内部不一定是有序的。基本例子如下，模拟一个任务队列，代码如下：

static class Task {
    int priority; // 数值越大，优先级越高
    String name; // 表示任务的名称
    
    private static Comparator<Task> taskComparator = new Comparator() {
        @Override
        public int compare(Task o1, Task o2) {
            if (o1.getPriority() > o2.getPriority()) {
                return -1;
            } else if (o1.getPriority() < o2.getPriority()){
                return 1;
            }
            return 0;
        }
    }
}

Queue<Task> tasks = new Priority<>(11, taskComparator);
tasks.offer(new Task(20, "写日记"));
tasks.offer(new Task(10, "看电视"));
tasks.offer(new Task(100, "写代码"));
Task task = tasks.poll();
while (task != null) {
    System.out.print("处理任务：" + task.getName() + ", 优先级：" + task.getPriority());
    task = tasks.poll();
}
// 结果如下：
处理任务：写代码，优先级：100
处理任务：写日记，优先级：20
处理任务：看电视，优先级：10

1. PriorityQueue有如下特点：

• 实现了优先级队列，最先出队的总是优先级最高的；
• 优先级相同时，内部元素不完全有序；
• 查询头部元素效率很高，入队、出队效率很高；
• 根据值查找和删除元素效率很低
• 具体两个应用场景：求前K个最大的元素，且数据源源不断进来或者是求数据的中间值，且数据源源不断来；

5 通用容器类

1. Collections提供了很多针对容器接口的通用算法和功能；
2. 容器接口有如下六种，分别是：Collection、List、Set、Queue、Deque和Map；
3. 容器类中运用了大量的适配器模式

• 空容器方法：类似于将null或者“空”转换成一个标准的容器接口对象；例如：emptyMap, emptyList或者是emptySet;（不可变对象）
• 单一对象方法：讲一个单独的对象转换为一个标准的容器接口对象；例如：singletonList, singletonMap或者singletonSet;（不可变对象）
• 其他适配方法，例如将Map转换为Set等。

1. 基本容器类都是线程不安全的，因此在不需要并发的场景下可以放心使用；