泛型谈到集合就离不开泛型基本上现在使用集合都要指定元素的类型。但是 Java 一开始是没有泛型的而是将元素向上转型转成 Object 类型对象保存在 Object[] 中所以那个时候的集合可以保存所有类型的实例对象。在 JDK5 的时候引入了泛型为了兼容之前的 API还是用 Object[] 保存元素。但是在使用集合的时候必须要指定元素的类型。为什么要指定元素的类型呢就以下面的代码作为例子没有使用泛型可以保存所有类型的对象这些对象会被转成 Object 对象保存起来通过 get 方法返回的也是 Object 对象。使用泛型只能保存指定的数据类型的对象这里是 String 类型但是 String 对象也是要转成 Object 对象保存起来。但是因为知道了数据的类型所以向上转型和向下转型可以丝滑切换get 方法返回的就是经过向下转型的对象。public static void main(String[] args) { ArrayList l1 new ArrayList(); ArrayListString 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 文件中写的是 ArrayListString list new ArrayList()在 .class 文件中变成了 ArrayList list new ArrayList()元素的类型被去掉了。所以 Java 是在编译期对集合的元素进行类型判断的。泛型类泛型类的使用非常简单就是在类名后面加一个 {标识符} 就可以了然后这个标识符就成为了一个本类中全局通用的类型。泛型接口跟泛型类是一样的毕竟接口是特殊的类嘛。如果一个类继承了泛型类或者实现了泛型接口要么提供具体的类型要么继续保持泛型。public class Main { public static void main(String[] args) { Test1String test1 new Test1(); String str test1.test(str); Test2Integer test2 new Test2(); Integer i test2.test(100); Test3Boolean test3 new Test3(); Boolean b test3.test(false); Test4Main test4 new Test4(); Main main test4.test(new Main()); } Override public String toString() { return Main{}; } } class Test1T { public T test(T t) { System.out.println(t); return t; } } class Test2T100{ public T100 test(T100 t) { System.out.println(t); return t; } } class Test3ABC{ 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) { ArrayListP2 p2 new ArrayList(); p2.add(new P2()); p2.add(new P2()); // 合法 p2.add(new P3()); // 非法 test(p2); } public static void test(ArrayListP1 list) { } } class P1 { } class P2 extends P1 { } class P3 extends P2 { }p2.add(new P3())因为 P3 是 P2 的子类所以这里相当于向上转型P2 p2 new P3()是合法的。test(p2)test 方法需要的是 ArrayListP1 类型的对象但是传入的是 ArrayListP2 类型的对象。虽然 P2 继承了 P1它们之间有继承关系但是 ArrayListP1 ! ArrayListP2它们都是 ArrayList 类型没有特殊关系所以是非法的编译不通过。这个时候就需要用泛型通配符了? 通配所有类型? extends AA 和 A 的子类? super AA 和 A 的父类依旧看代码因为 P1 P2 P3所以 ? extends P1 的要求P2 和 P3 都满足? super P3 的要求P2 和 P3 都满足。public class Main { public static void main(String[] args) { ArrayListString list new ArrayList(); // ?对元素类型没有要求 test1(list); ArrayListP1 p1 new ArrayList(); ArrayListP2 p2 new ArrayList(); ArrayListP3 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基于 HashMapTreeSet基于 TreeMapMap双列集合一个元素就是一个键值对可以保存键和值两个对象键不能重复值可以重复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 方法进行增删改。双列集合需要先转成单列集合才能进行遍历。ArrayListArrayList 是基于数组实现的而且是动态数组可以实现自动扩容。这里是 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()默认初始长度是 10public 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 0elementData 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 - oldCapacityprefGrowth oldCapacity 1。简单理解就是新数组的长度要么是旧数组长度的 1.5 倍要么新数组长度 最小容量。还没完我们还要看 else 分支还记得 ArrayList 的三个构造方法吗elementData EMPTY_ELEMENTDATA还有 elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA。如果 oldCapacity 0elementData EMPTY_ELEMENTDATA走 if 分支。如果 oldCapacity 0elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA走 else 分支。所以只有空参构造才有默认长度 10 的说法。public static void main(String[] args) { ArrayListString l1 new ArrayList(0); ArrayListString l2 new ArrayList(new ArrayListString()); ArrayListString l3 new ArrayList(); // 扩容后长度 1 l1.add(100); l2.add(100); // 扩容后长度 10 l3.add(100); }LinkedListLinkedList 是基于链表实现的而且是双向链表维护了头尾指针通过头尾指针操作非常方便。LinkedList 的属性如下transient int size 0; transient NodeE first; transient NodeE last;为什么这里没有 Object[] 数组呢泛型不都是保存 Object 对象的吗很简单因为这个是链表不是数组可以通过 next 和 prev 指针获得上下的元素。Node 是 LinkedList 中的一个内部类表示 LinkedList 中的一个元素也叫节点吧。private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }在 LinkedList 中添加节点、删除节点、在指定下标插入元素这些操作就很好理解了无非就是移动指针的艺术。LinkedList 操作头尾节点的时间复杂度都是 O(1)而且为头尾节点设置了很多方法有兴趣的可以了解下。TreeMapMap 的 key 是无序、不重复的它是怎么实现去重的呢HashMap 通过计算 key 的 hash 值进行去重。TreeMap 是基于红黑树的但是红黑树可以有重复的元素啊红黑树又不是一定要去重。所以在 Java 中使用 TreeMap 的时候需要同时提供去重的规则。这个去重的规则在 TreeMap 同时用来排序和去重。方案一TreeMap 的元素类型需要实现 Comparable 接口重写 compareTo 方法。public class Main { public static void main(String[] args) { TreeMapTest, Integer map new TreeMap(); map.put(new Test(1, 1), 1); map.put(new Test(2, 2), 2); for (Map.EntryTest, Integer entry : map.entrySet()) { System.out.println(entry.getKey().toString()); } } } class Test implements ComparableTest { 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) { TreeMapTest, Integer map new TreeMap(new ComparatorTest() { 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.EntryTest, Integer entry : map.entrySet()) { System.out.println(entry.getKey().toString()); } } }接下来是 TreeMap 中的 put 方法private V put(K key, V value, boolean replaceOld) { EntryK,V t root; if (t null) { addEntryToEmptyMap(key, value); return null; } int cmp; EntryK,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 接口更优先。HashMapHashMap 从 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 16MAXIMUM_CAPACITY最大长度2^30DEFAULT_LOAD_FACTOR加载因子TREEIFY_THRESHOLD链表树化边界当链表的长度 8 就要转红黑树UNTREEIFY_THRESHOLD红黑树链化边界当红黑树的节点数 6 转成链表MIN_TREEIFY_CAPACITY数组树化边界当数组长度 64 并且链表长度 8 时链表转成红黑树thresholdHashMap 允许的最大元素个数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 但是链表长度已经 8size thresholdthreshold 加载因子 * 数组长度扩容调用的是 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 82^4 16因为 9 位于 [8, 16] 的区间内然后向上取整所以 this.threshold tableSizeFor(9) 16。这里跟上面不是矛盾了吗threshold 不是 加载因子 * 数组长度吗怎么现在 threshold 直接等于数组长度了难道是 public HashMap(int initialCapacity) 这个方法的特性别急要知道这个时候的 HashMap 还没有初始化数组所以这里的 threshold 是用来保存数组长度的之后还可以改。在第一次添加元素的时候会触发 resize 方法不过应该不算是扩容只是分配数组内存罢了。在 resize 方法中初始化数组时会重新计算 threshold令 threshold 加载因子 * 数组长度如果想要计算数组长度直接用 threshold / 加载因子就可以了。