泛型

谈到集合，就离不开泛型，基本上现在使用集合都要指定元素的类型。

但是 Java 一开始是没有泛型的，而是将元素向上转型转成 Object 类型对象，保存在 Object[] 中，所以那个时候的集合可以保存所有类型的实例对象。

在 JDK5 的时候引入了泛型，为了兼容之前的 API，还是用 Object[] 保存元素。但是，在使用集合的时候，必须要指定元素的类型。

为什么要指定元素的类型呢？

就以下面的代码作为例子：

• 没有使用泛型：可以保存所有类型的对象，这些对象会被转成 Object 对象保存起来，通过 get 方法返回的也是 Object 对象。
• 使用泛型：只能保存指定的数据类型的对象（这里是 String 类型），但是 String 对象也是要转成 Object 对象保存起来。但是，因为知道了数据的类型，所以向上转型和向下转型可以丝滑切换，get 方法返回的就是经过向下转型的对象。

    public static void main(String[] args) {
        ArrayList l1 = new ArrayList();
        ArrayList<String> l2 = new ArrayList<>();
        
        // 没有泛型，可以保存所有类型的对象
        l1.add("100");
        l1.add(100);
        l1.add(true);
        // 返回的是Object对象
        Object o = l1.get(0);

        l2.add("100");
        l2.add("200");
        // 返回的是String对象
        String s = l2.get(0);
    }

泛型其实就是起到一个门禁的作用，只有符合条件的对象才能进入集合中。

这里还有一个概念叫做泛型擦除。因为泛型只是加了一个门禁，实际上还是保存 Object 对象。所以我们在 .java 文件中使用集合的时候需要声明集合元素的类型，但是编译之后，在 .class 文件中对于元素类型的声明会被擦除。

简单说就是我们在 .java 文件中写的是 ArrayList<String> list = new ArrayList<>()，在 .class 文件中变成了 ArrayList list = new ArrayList()，元素的类型被去掉了。

所以 Java 是在编译期对集合的元素进行类型判断的。

泛型类

泛型类的使用非常简单，就是在类名后面加一个 <{标识符}> 就可以了，然后这个标识符就成为了一个本类中全局通用的类型。

泛型接口跟泛型类是一样的，毕竟接口是特殊的类嘛。

如果一个类继承了泛型类或者实现了泛型接口，要么提供具体的类型，要么继续保持泛型。

public class Main {
    public static void main(String[] args) {
        Test1<String> test1 = new Test1<>();
        String str = test1.test("str");

        Test2<Integer> test2 = new Test2<>();
        Integer i = test2.test(100);

        Test3<Boolean> test3 = new Test3<>();
        Boolean b = test3.test(false);

        Test4<Main> test4 = new Test4<>();
        Main main = test4.test(new Main());
    }

    @Override
    public String toString() {
        return "Main{}";
    }
}

class Test1<T> {
    public T test(T t) {
        System.out.println(t);
        return t;
    }
}

class Test2<T100>{
    public T100 test(T100 t) {
        System.out.println(t);
        return t;
    }
}

class Test3<ABC>{
    public ABC test(ABC abc) {
        System.out.println(abc);
        return abc;
    }
}

class Test4<$$>{
    public $$ test($$ $$) {
        System.out.println($$);
        return $$;
    }
}

泛型方法

在泛型类中提供了一个全局的类型标识符，在方法中可以直接使用这个类型标识符表示具体的类型。

当然，即使不是泛型类，一样可以使用泛型方法：

• 参数列表中一定要出现泛型
• 在返回值前面加上泛型标识符，不然编译报错

    public static void main(String[] args) {
        test("1234");
    }

    // 泛型标识符 返回值 方法名(参数列表)
    // 参数列表一定要出现泛型
    public static <T> void test(T t) {
        System.out.println(t);
    }

泛型通配符

泛型通配符用来规定集合元素类型之间的继承关系，这么说确实很天书，还是看代码吧。

public class Main {
    public static void main(String[] args) {
        ArrayList<P2> p2 = new ArrayList<>();
        p2.add(new P2());
        p2.add(new P2());

        // 合法
        p2.add(new P3());
        
        // 非法
        test(p2);
    }

    public static void test(ArrayList<P1> list) {
        
    }
}

class P1 {

}

class P2 extends P1 {

}

class P3 extends P2 {

}

• p2.add(new P3())，因为 P3 是 P2 的子类，所以这里相当于向上转型，P2 p2 = new P3()，是合法的。
• test(p2)，test 方法需要的是 ArrayList<P1> 类型的对象，但是传入的是 ArrayList<P2> 类型的对象。虽然 P2 继承了 P1，它们之间有继承关系，但是 ArrayList<P1> != ArrayList<P2>，它们都是 ArrayList 类型，没有特殊关系，所以是非法的，编译不通过。

这个时候就需要用泛型通配符了：

• ? 通配所有类型
• ? extends A，A 和 A 的子类
• ? super A，A 和 A 的父类

依旧看代码：

因为 P1 > P2 > P3，所以 ? extends P1 的要求，P2 和 P3 都满足；? super P3 的要求，P2 和 P3 都满足。

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        // ?：对元素类型没有要求
        test1(list);

        ArrayList<P1> p1 = new ArrayList<>();
        ArrayList<P2> p2 = new ArrayList<>();
        ArrayList<P3> p3 = new ArrayList<>();
        
        // ? super P3：元素类型是P3的上级，也就是直接父类和间接父类都可以
        test2(p1);
        test2(p2);

        // ? extends P1：元素类型是P1的下级，也就是直接子类和间接子类都可以
        test3(p2);
        test3(p3);
    }

    public static void test1(ArrayList<?> list) {

    }

    public static void test2(ArrayList<? super P3> list) {

    }

    public static void test3(ArrayList<? extends P1> list){
        
    }
}

class P1 {

}

class P2 extends P1 {

}

class P3 extends P2 {

}

集合简介

简介就是简单介绍的意思。

集合的体系：

• Collection：单列集合，一个元素保存一个对象
  • List：有序、可重复、有索引或者说下标
    • ArrayList：基于数组实现
    • LinkedList：基于链表实现
  • Set：无序、不重复、无索引或者说下标
    • HashSet：基于 HashMap
    • TreeSet：基于 TreeMap
• Map：双列集合，一个元素就是一个键值对，可以保存键和值两个对象，键不能重复，值可以重复
  • HashMap：基于数组、链表、红黑树实现
  • TreeMap：基于红黑树实现

HashSet 和 TreeSet 其实就是 HashMap 和 TreeMap。

    public HashSet() {
        map = new HashMap<>();
    }

    public TreeSet() {
        this(new TreeMap<>());
    }

这是它们的 add 方法，用 key 来保存元素，它们的 value 都是一个静态常量 PRESENT。TreeSet 和 HashSet 各自有一个 PRESENT 静态常量。

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

下面是集合的遍历方式。

• 单列集合可以通过迭代器、for 循环、forEach 方法进行遍历。
  • 在使用迭代器的时候，不能用集合的 API 对集合进行增删改这些更新操作，会抛并发修改异常。但是可以用迭代器的 remove 方法移除元素。
  • 在 List 分支中添加了列表迭代器，虽然还是不能用集合的 API 进行更新操作，但是可以用迭代器的 set、remove、add 方法进行增删改。

双列集合需要先转成单列集合才能进行遍历。

ArrayList

ArrayList 是基于数组实现的，而且是动态数组，可以实现自动扩容。

这里是 ArrayList 的部分属性：

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData;
    private int size;

• EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是空数组，但是 EMPTY_ELEMENTDATA != DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
• 因为 ArrayList 是用 Object 来保存元素的，所以 elementData 是 Object 数组。
• size 表示集合中元素的个数。

ArrayList 有三个 public 的构造方法：

• public ArrayList()：默认初始长度是 10
• public ArrayList(int initialCapacity)：指定初始长度
• public ArrayList(Collection<? extends E> c)：传入一个单列集合对象，其实就是把这个集合中的元素 copy 到 ArrayList 里面

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList()：令 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，默认初始长度是 10。

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

public ArrayList(int initialCapacity)：如果传进来的 int < 0，抛非法参数异常；如果 int == 0，elementData = EMPTY_ELEMENTDATA；如果 int > 0，直接分配内存空间。

    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

public ArrayList(Collection<? extends E> c)：这个就更好理解了，如果传进来的集合对象有元素就拷贝元素，否则 elementData = EMPTY_ELEMENTDATA。（如果传进来的是 null 会抛空指针异常）

接下来是扩容逻辑，因为 ArrayList 有 add 方法和 addAll 方法，在添加元素的时候，会根据当前集合中的元素数量和要添加的元素数量，计算出一个最小容量。如果 ArrayList 对象的总长度小于最小容量，就要进行扩容。

也就是：ArrayList 对象中的元素个数 + 要添加进来的元素个数 = 最小容量。

如果 elementData.length < 最小容量，调用 grow 方法进行扩容。

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

ArraysSupport.newLength 方法用来确认新数组的长度，返回的是 oldLength + Math.max(minGrowth, prefGrowth)，minGrowth = minCapacity - oldCapacity，prefGrowth = oldCapacity >> 1。

简单理解就是，新数组的长度要么是旧数组长度的 1.5 倍，要么新数组长度 = 最小容量。

还没完，我们还要看 else 分支，还记得 ArrayList 的三个构造方法吗，elementData = EMPTY_ELEMENTDATA，还有 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

如果 oldCapacity = 0，elementData = EMPTY_ELEMENTDATA，走 if 分支。

如果 oldCapacity = 0，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，走 else 分支。所以只有空参构造才有默认长度 = 10 的说法。

    public static void main(String[] args) {
        ArrayList<String> l1 = new ArrayList<>(0);
        ArrayList<String> l2 = new ArrayList<>(new ArrayList<String>());
        ArrayList<String> l3 = new ArrayList<>();
        // 扩容后长度 = 1
        l1.add("100");
        l2.add("100");

        // 扩容后长度 = 10
        l3.add("100");
    }

LinkedList

LinkedList 是基于链表实现的，而且是双向链表，维护了头尾指针，通过头尾指针操作非常方便。

LinkedList 的属性如下：

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

为什么这里没有 Object[] 数组呢？泛型不都是保存 Object 对象的吗？

很简单，因为这个是链表，不是数组，可以通过 next 和 prev 指针获得上下的元素。

Node 是 LinkedList 中的一个内部类，表示 LinkedList 中的一个元素，也叫节点吧。

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

在 LinkedList 中添加节点、删除节点、在指定下标插入元素这些操作就很好理解了，无非就是移动指针的艺术。

LinkedList 操作头尾节点的时间复杂度都是 O(1)，而且为头尾节点设置了很多方法，有兴趣的可以了解下。

TreeMap

Map 的 key 是无序、不重复的，它是怎么实现去重的呢？

• HashMap 通过计算 key 的 hash 值进行去重。
• TreeMap 是基于红黑树的，但是红黑树可以有重复的元素啊，红黑树又不是一定要去重。所以，在 Java 中使用 TreeMap 的时候，需要同时提供去重的规则。

这个去重的规则在 TreeMap 同时用来排序和去重。

方案一：TreeMap 的元素类型需要实现 Comparable 接口，重写 compareTo 方法。

public class Main {
    public static void main(String[] args) {
        TreeMap<Test, Integer> map = new TreeMap<>();
        map.put(new Test(1, "1"), 1);
        map.put(new Test(2, "2"), 2);
        for (Map.Entry<Test, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey().toString());
        }
    }
}

class Test implements Comparable<Test> {
    private int id;
    private String unique_str;

    public Test(int id, String unique_str) {
        this.id = id;
        this.unique_str = unique_str;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Test{" +
                "id=" + id +
                ", unique_str='" + unique_str + '\'' +
                '}';
    }

    // 负数放在左边
    // 正数放在右边
    // 0表示重复，不是添加元素，是替换元素
    @Override
    public int compareTo(Test t) {
        // this：要添加的元素
        // t：集合中用来对比的元素
        return getId() - t.getId();
    }
}

方案二：在 new TreeMap 对象的时候传入一个比较器对象，比较器对象里面有一个 compare 方法。

public class Main {
    public static void main(String[] args) {
        TreeMap<Test, Integer> map = new TreeMap<>(new Comparator<Test>() {
            @Override
            public int compare(Test o1, Test o2) {
                // o1：要添加的元素
                // o2：集合中用来对比的元素
                return o1.getId() - o2.getId();
            }
        });
        map.put(new Test(1, "1"), 1);
        map.put(new Test(2, "2"), 2);
        for (Map.Entry<Test, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey().toString());
        }
    }
}

接下来是 TreeMap 中的 put 方法：

    private V put(K key, V value, boolean replaceOld) {
        Entry<K,V> t = root;
        if (t == null) {
            addEntryToEmptyMap(key, value);
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        } else {
            Objects.requireNonNull(key);
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        }
        addEntry(key, value, parent, cmp < 0);
        return null;
    }

K key, V value, boolean replaceOld：传入了 key 和 value，通过 replaceOld 判断是否需要替换重复的元素。

if else 这里就是遍历红黑树判断元素是否存在了，如果有比较器对象就用比较器来对比，否则用 Comparable 接口。所以比较器比 Comparable 接口更优先。

HashMap

HashMap 从 JDK8 起，使用了数组 + 链表 + 红黑树来实现。

HashMap 的各种属性如下：

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    int threshold;

• DEFAULT_INITIAL_CAPACITY：默认长度，2^4 = 16
• MAXIMUM_CAPACITY：最大长度，2^30
• DEFAULT_LOAD_FACTOR：加载因子
• TREEIFY_THRESHOLD：链表树化边界，当链表的长度 >= 8 就要转红黑树
• UNTREEIFY_THRESHOLD：红黑树链化边界，当红黑树的节点数 <= 6 转成链表
• MIN_TREEIFY_CAPACITY：数组树化边界，当数组长度 >= 64 并且链表长度 >= 8 时，链表转成红黑树
• threshold：HashMap 允许的最大元素个数，threshold = 加载因子 * 数组长度

先来看 put 方法：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

put 方法中调用了 putVal 方法，通过 hash(key) 得到 key 的哈希值。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hash 方法中，先通过 key 的 hashCode 方法获取 hash 值，hashCode 返回的是 int 类型的变量。

将 hashCode 返回的 int 变量赋值给 h，让 h 的低 16 位和 h 的高 16 位进行与操作，保留 h 的高 16 位。这个过程叫做扰动算法，目的是增强哈希值的随机性，减少哈希冲突。

接下来进入 putVal 方法，这里就不展示代码了，就大概讲一下流程，其实我也没怎么看懂(｡>︿<｡ )。

• if(table == null)，先给 table 分配内存，HashMap 是懒分配，new 出来对象之后只有第一次添加元素才会分配内存，跟 ArrayList 一样。
• HashMap 允许 key 和 value = null，允许一个 null key 和多个 null value。
• tab[i = (n - 1) & hash]，n = 数组长度，index = hash & (数组长度 - 1) = hash % 数组长度，但是位运算的效率比取模更高，不过如果要让位运算和取模是等效的，数组长度必须是 2 的 n 次方，n >= 0。
• 如果 table[i] == null，直接令 table[i] = e，否则出现哈希冲突。table[i] 下面可能挂着链表或者红黑树，遍历 table[i] 下面的所有元素，用 equals 方法进行对比，无则新增，有则替换。

还没完，因为数组长度是有限的，在 putVal 中还要判断是否需要扩容：

• 数组长度 < 64 但是链表长度已经 >= 8
• ++size > threshold，threshold = 加载因子 * 数组长度

扩容调用的是 resize 方法。

• 新数组长度 = 旧数组长度的两倍，数组长度必须是 2 的 n 次方，n >= 0
• 在 HashMap 中有三种元素：数组元素、链表元素、红黑树元素
  • 数组元素：根据哈希值，计算在新数组的位置，newTab[e.hash & (newCap - 1)] = e
  • 链表元素和红黑树元素：if ((e.hash & oldCap) == 0)，放在新数组的旧下标位置（下标不变）；else 放在新数组的旧下标 + 旧数组长度的位置（新下标 = 旧下标 + 旧数组长度）

注意：扩容后原来的结构可能变化。

其实 HashMap 还有一个构造方法，可以指定数组的初始长度。这就很有意思了，如果我传进去的长度不是 2 的 n 次方，是一个奇数，那 HashMap 不就炸了吗？

Java 的开发者早就考虑到了这个问题，所以这个构造方法是防呆设计。

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

new HashMap<>(9)，最终会通过 tableSizeFor(initialCapacity) 返回 initialCapacity 在 2 的 n 次方区间的向上取整的值。不过这句话对听不懂的人就是废话。

已知 2^3 = 8，2^4 = 16，因为 9 位于 [8, 16] 的区间内，然后向上取整，所以 this.threshold = tableSizeFor(9) = 16。

这里跟上面不是矛盾了吗？threshold 不是 = 加载因子 * 数组长度吗？怎么现在 threshold 直接等于数组长度了，难道是 public HashMap(int initialCapacity) 这个方法的特性？

别急，要知道这个时候的 HashMap 还没有初始化数组，所以这里的 threshold 是用来保存数组长度的，之后还可以改。

在第一次添加元素的时候，会触发 resize 方法，不过应该不算是扩容，只是分配数组内存罢了。

在 resize 方法中初始化数组时，会重新计算 threshold，令 threshold = 加载因子 * 数组长度，如果想要计算数组长度，直接用 threshold / 加载因子就可以了。