一 集合有哪些

1. Collection
   • List
     • 概述
       • 序列 索引
       • 四種訪問列表元素方法：get iterator ListIterator foreach
       • 排序：
         • java.lang.Comparable：很多數(shù)據(jù)類均已實(shí)現(xiàn)，如String/Integer
         • java.util.Comparator：擴(kuò)展使用
         • Collections.sort(List<T> list) <T extends Comparable>
         • Collections.sort(List<T> list, Comparator<? super T> c)
     • ArrayList
       • 基于數(shù)組的list實(shí)現(xiàn)，默認(rèn)容量為10，add復(fù)雜度O(n)；
       • 相當(dāng)于Vector，但不同步，Collections.synchronizedList(new ArrayList(...))，基于synchronized代碼塊；
       • 擴(kuò)容：最大為Integer.MAX_VALUE，每次add時(shí)候計(jì)算容量，如果超過，則擴(kuò)容，每次擴(kuò)容為oldCapacity的一半，若擴(kuò)容后還小于所需，則使用minCapacity；
       • 場景：隨機(jī)查找O(1)，更適合查找，不太適合增刪比較多的場景；
       • tips clone 淺拷貝
         • 賦值：基本數(shù)據(jù)類型和引用數(shù)據(jù)類型都是同一份，即均改變；
         • 淺拷貝：基本數(shù)據(jù)類型拷貝，引用數(shù)據(jù)類型只拷貝指針，即引用數(shù)據(jù)類型是同一份，若改變則受影響；
         • 深拷貝：全拷貝，基本數(shù)據(jù)和引用數(shù)據(jù)類型都是個(gè)一份，互不影響；
     • LinkedList
       • 結(jié)構(gòu)：屬性(Node<E> first & Node<E> last)
         內(nèi)嵌private 靜態(tài)內(nèi)部類node，
         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;
         }
         }
       • 雙鏈表，實(shí)現(xiàn)了List和Deque接口，具有雙向隊(duì)列的特性；
       • 不同步，Collections.synchronizedList(new LinkedList(...))；
       • 相反的順序返回此deque元素的迭代器，descendingIterator()；
       • 場景：增刪O(1)，更適合頻繁增刪，雖支持隨機(jī)查找，但需要遍歷鏈表，使用的是折半查找；
     • Vector
       • 概述
         • 基于數(shù)組實(shí)現(xiàn)，默認(rèn)容量為10，等同于ArrayList；
         • 同步，所有public method均是synchronized 方法；
         • 擴(kuò)容：跟ArrayList的區(qū)別是，在new Vector可以指定擴(kuò)容時(shí)增長多少，若未設(shè)置，則是oldCapacity，默認(rèn)擴(kuò)容1倍；
       • Stack
         • 結(jié)構(gòu)：LIFO，更常用的是
           Deque<Integer> stack = new ArrayDeque<Integer>();
         • method：peek()/push()/pop();
   • Set
     • 概述
       • 元素唯一，只有一個(gè)空元素；
     • HashSet
       • 概述
         • 內(nèi)嵌HashMap，初始容量16，負(fù)載因子為0.75；
         • HashMap默認(rèn)的value是new Object()，如何保證不重復(fù)，HashMap的key是避免重復(fù)的；
         • 不同步，Collections.synchronizedSet(new HashSet(...))；
       • LinkedHashSet
         • 跟HashSet并無什么不同，只不過底層依賴的是LinkedHashMap；
         • 迭代順序跟add放入的順序一致，so當(dāng)你想以放入的順序返回；
     • TreeSet
       • 內(nèi)嵌NavigableMap(導(dǎo)航map)，默認(rèn)是依賴TreeMap，底層是紅黑樹，根據(jù)Comparator比較放入；
       • 默認(rèn)是自然順序，另可在new TreeSet時(shí)指定Comparator；
       • add/remove/contains的時(shí)間復(fù)雜度是log(n)；
     • EnumSet
       • 專門用于操作枚舉集，對(duì)枚舉的操作效率高，內(nèi)嵌Enum<?>[]；
       • iterator返回的迭代器以自然順序 （枚舉常量的聲明順序）遍歷元素；
       • 不允許null元素，內(nèi)嵌靜態(tài)內(nèi)部類SerializationProxy進(jìn)行序列化；
   • Queue
     • 概述
       • 隊(duì)列，通常但不一定是以FIFO（先進(jìn)先出）方式排序元素，尾部插入，頭部刪除；
       • 插入/提取/檢查操作，這些方法中的每一種都有兩種形式：如果操作失敗，則拋出一個(gè)異常，另一種返回一個(gè)特殊值（ null或false ，具體取決于操作）；
       • remove()和[`poll()方法刪除并返回隊(duì)列的頭；
       • element()和peek()方法返回，但不要?jiǎng)h除，頭的隊(duì)列；
       • Queue實(shí)現(xiàn)通常不允許插入null元素，但LinkedList是個(gè)例外；
     • Deque
       • 雙端隊(duì)列，支持兩端元素插入和移除的線性集合；
       • 作為隊(duì)列時(shí)，具有FIFO的行為，尾部插入，頭部刪除；
       • 作為堆棧時(shí)，具有LIFO的行為，應(yīng)優(yōu)先于傳統(tǒng)的Stack，元素從頭部彈出；
       • 與List接口不同，Deque不支持索引訪問元素；
       • Deque同樣不允許插入null元素；
       • 插入：add=addLast/addFirst/offer=offerLast/offerFirst
       • 檢索：element/peek=peekFirst/peekLast
       • 刪除：poll=pollFirst/pollLast/remove=removeFirst/removeLast
       • 堆棧操作：push/pop；
2. Map
   • 概述
     • 鍵值對(duì)，替代原有抽象類Dictionary；
     • 內(nèi)嵌子接口：Entry<K,V>；
   • HashMap
     • 概述
       • 基于hash表實(shí)現(xiàn)，允許null key & value，與Hashtable相當(dāng)，但不同步；
       • capacity為16，必須是2的倍數(shù)，load factor指table的填充比例，默認(rèn)0.75，當(dāng)對(duì)迭代性能要求比較高時(shí)，不能把capacity設(shè)置的太大，同時(shí)load factor不要超過0.75，否則會(huì)明顯增加沖突幾率；
       • put原理：當(dāng)在第一次put時(shí)，先對(duì)table初始化，通過hash計(jì)算得到存放位置table[i]，存放；當(dāng)再次put時(shí)，同樣經(jīng)過hash計(jì)算得到位置，則采用鏈表法解決沖突，存放在相同位置的next區(qū)域；在JDK8中設(shè)置了鏈表的默認(rèn)閾值為8，如果超過這個(gè)值，則進(jìn)行紅黑樹化；如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)；如果bucket滿了(超過load factor*current capacity)，就要resize，變?yōu)樵瓉?倍；
     • LinkedHashMap
       • 基于hash表和雙向鏈表，與HashMap的區(qū)別在于迭代順序；
       • 迭代順序：內(nèi)置標(biāo)識(shí)位boolean accessOrder，默認(rèn)為false，則是插入順序，設(shè)置為true，則是訪問順序；
   • Hashtable
     • 基于hash表的實(shí)現(xiàn)，繼承于Dictionary，現(xiàn)已廢棄，主要了解與HashMap的區(qū)別；
     • 區(qū)別是：同步（所有方法被synchronized修飾），不允許null key & value，key的hash方式也不同；
     • tips：hash沖突處理
       • 拉鏈法：構(gòu)建一個(gè)同義詞的鏈表，hashmap就是基于此；
       • 開放定址法：當(dāng)p沖突時(shí)，基于p再hash處理，直到不沖突為止，主要有三種實(shí)現(xiàn)方式，即線性探測/二次探測/偽隨機(jī)探測；
   • TreeMap
     • 基于紅黑樹實(shí)現(xiàn)，containsKey/get/put/remove的時(shí)間復(fù)雜度log(n);
     • 排序是根據(jù)key的Comparable natural ordering，或者在構(gòu)造map的時(shí)候傳遞Comparator；
   • EnumMap
     • 類似于EnumSet，但key是Enum對(duì)象
3. Iterator
   • 概述
     • 只有remove方法；
     • list迭代順序均是放入的順序，set的迭代是按add后排序后，hashset根據(jù)hashcode處理（但不保證），treeset則是自然順序；
   • ListIterator
     • 只有l(wèi)ist接口才有，增加了add和set方法，并可指定索引迭代；
     • add是在迭代之后的地方add，set是對(duì)正迭代的進(jìn)行修改；