Java知识点总结，面试必备，java基础、java集合、JVM、Java并发、数据结构与算法、LeetCode

<!-- GFM-TOC --> * [一、概览](#一概览) * [Collection](#collection) * [Map](#map) * [二、容器中的设计模式](#二容器中的设计模式) * [迭代器模式](#迭代器模式) * [适配器模式](#适配器模式) * [三、源码分析](#三源码分析) * [ArrayList](#arraylist) * [Vector](#vector) * [CopyOnWriteArrayList](#copyonwritearraylist) * [LinkedList](#linkedlist) * [HashMap](#hashmap) * [ConcurrentHashMap](#concurrenthashmap) * [LinkedHashMap](#linkedhashmap) * [WeakHashMap](#weakhashmap) * [参考资料](#参考资料) <!-- GFM-TOC --> # 一、概览 | Collection | | 是否有序 | 是否允许元素重复 | 是否允许null值 | 实现 | 优点 | 缺点 | 默认容量 | 扩容因子 | 扩容 | | ---------- | ------------- | ---------------------- | --------------------------------------------------------- | ----------------------------- | ----------------------------------------------------------- | ------------------------------------ | ------------------------------------- | -------- | -------- | ----- | | List | ArrayList | 是 | 是 | 是 | 数组实现 | 无容量限制，查询快，轻量级 | 增删慢，线程不安全 | 10 | 1 | 1.5倍 | | | LinkedList | 是 | 是 | 是 | 链表实现 | 增删快 | 查询慢，双向链表，线程不安全 | 10 | 1 | 1.5倍 | | | Vector | 是 | 是 | 否 | 数组实现 | 线程安全，查询快 | 重量级，存在性能问题，增删慢 | 10 | 1 | 2倍 | | Set | HashSet | 否 | 否 | 是 | 基于HashMap实现 | 效率高 | 非线程安全 | 16 | 0.75 | 2倍 | | | TreeSet | 是（用二叉树实现排序） | 否 | 否 | 基于TreeMap实现 | 可以指定比较方法进行排序 | 非线程安全 | | | | | | LinkedHashSet | 是（用二叉树实现排序） | 否 | 是 | 继承HashSet，底层使用LinkedHashMap | 链表保证元素有序，hash表保证元素唯一 | 双重链接列表 | 16 | 0.75 | 2倍 | | Map | HashMap | 否 | 使用key-value来映射和存储数据，key必须唯一，value可以重复 | 最多只允许一条记录的key为null | 根据key的hashCode值存储数据 | 使用hash算法去重效率高 | 非线程安全 | 16 | 0.75 | 2倍 | | | TreeMap | 是（用二叉树排序） | 同上 | 否 | 基于红黑树实现，继承AbstractMap，并且实现了NavigableMap接口 | 可以用指定比较方法进行排序 | 非线程安全 | | | | | | LinkedHashMap | 是 | 同上 | 是 | 在HashMap基础上采用了双向链表 | 元素迭代顺序和插入顺序一致 | 双重链接链表，非同步，遍历比HashMap慢 | 16 | 0.75 | 2倍 | | | WeakHashMap | 否 | 同上 | 是 | KV对存储，“弱键”自动GC回收删除，继承AbstractMap | | | | | | | | HashTable | 否 | 同上 | 否 | 在HashMap基础上加synchronized | 线程安全 | 效率低 | 11 | 0.75 | 2倍+1 | 容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。 <div align="center"> <img src="https://github.com/wind0926/JAVA2019/blob/master/image/Java%E5%9F%BA%E7%A1%80/GitHub%E5%9B%BE%E7%89%87/java%E5%AE%B9%E5%99%A8%E4%BD%93%E7%B3%BB%E5%9B%BE.png"/> </div><br> ## Collection <div align="center"> <img src="https://github.com/wind0926/JAVA2019/blob/master/image/Java%E5%9F%BA%E7%A1%80/GitHub%E5%9B%BE%E7%89%87/Collection.png"/> </div><br> ### 1. Set - TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。 - HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。 - LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。 ### 2. List - ArrayList：基于动态数组实现，支持随机访问。 - Vector：和 ArrayList 类似，但它是线程安全的。 - LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。 ### 3. Queue - LinkedList：可以用它来实现双向队列。 - PriorityQueue：基于堆结构实现，可以用它来实现优先队列。 ## Map <div align="center"> <img src="https://github.com/wind0926/JAVA2019/blob/master/image/Java%E5%9F%BA%E7%A1%80/GitHub%E5%9B%BE%E7%89%87/map.png"/> </div><br> - TreeMap：基于红黑树实现。 - HashMap：基于哈希表实现。 - HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。 - LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。 # 二、容器中的设计模式 ## 迭代器模式 <div align="center"> <img src="https://github.com/wind0926/JAVA2019/blob/master/image/Java%E5%9F%BA%E7%A1%80/GitHub%E5%9B%BE%E7%89%87/%E8%BF%AD%E4%BB%A3%E5%99%A8.png"/> </div><br> Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。 从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。 ```java List<String> list = new ArrayList<>(); list.