java arraylist排序_最全Java集合筆記

集合概述

什么是集合

集合框架：用于存儲數據的容器。

集合框架是為表示和操作集合而規定的一種統一的標準的體系結構。任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。

接口：表示集合的抽象數據類型。接口允許我們操作集合時不必關注具體實現，從而達到“多態”。在面向對象編程語言中，接口通常用來形成規范。

實現：集合接口的具體實現，是重用性很高的數據結構。

算法：在一個實現了某個集合框架中的接口的對象身上完成某種有用的計算的方法，例如查找、排序等。這些算法通常是多態的，因為相同的方法可以在同一個接口被多個類實現時有不同的表現。事實上，算法是可復用的函數。它減少了程序設計的辛勞。

集合框架通過提供有用的數據結構和算法使你能集中注意力于你的程序的重要部分上，而不是為了讓程序能正常運轉而將注意力于底層設計上。通過這些在無關API之間的簡易的互用性，使你免除了為改編對象或轉換代碼以便聯合這些API而去寫大量的代碼。它提高了程序速度和質量。

集合的特點

集合的特點主要有如下兩點：

對象封裝數據，對象多了也需要存儲。集合用于存儲對象。
對象的個數確定可以使用數組，對象的個數不確定的可以用集合。因為集合是可變長度的。

集合和數組的區別

數組是固定長度的；集合可變長度的。
數組可以存儲基本數據類型，也可以存儲引用數據類型；集合智能存儲引用數據類型。
數組存儲的元素必須是同一個數據類型；集合存儲的對象可以是不同數據類型。

使用集合框架的好處

容量自增長；
提供了高性能的數據結構和算法，使編碼更輕松，提高了程序速度和質量；
允許不同 API 之間的互操作，API之間可以來回傳遞集合；
可以方便地擴展或改寫集合，提高代碼復用性和可操作性。
通過使用JDK自帶的集合類，可以降低代碼維護和學習新API成本。

常用的集合類有哪些？

Map接口和Collection接口是所有集合框架的父接口：

Collection接口的子接口包括：Set接口和List接口Map接口的實現類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等Set接口的實現類主要有：HashSet、TreeSet、LinkedHashSet等List接口的實現類主要有：ArrayList、LinkedList、Stack以及Vector等

List，Set，Map三者的區別？List、Set、Map 是否繼承自 Collection 接口？List、Map、Set 三個接口存取元素時，各有什么特點？

集合框架底層數據結構

Collection

List

Arraylist： Object數組
Vector： Object數組
LinkedList：雙向循環鏈表

HashSet（無序，唯一）：底層采用 HashMap 來保存元素
LinkedHashSet： LinkedHashSet 繼承于HashSet，并且其內部是通過 LinkedHashMap 來實現的。
TreeSet（有序，唯一）：紅黑樹(自平衡的排序二叉樹。)

Map

HashMap： JDK1.8之前HashMap由數組+鏈表組成的；JDK1.8以后鏈表+紅黑樹；
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。
HashTable：數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在
TreeMap：紅黑樹（自平衡的排序二叉樹）

哪些集合類是線程安全的？

vector：就比arraylist多了個同步化機制（線程安全），因為效率較低，現在已經不太建議使用。在web應用中，特別是前臺頁面，往往效率（頁面響應速度）是優先考慮的。
statck：堆棧類，先進后出。
hashtable：就比hashmap多了個線程安全。
enumeration：枚舉，相當于迭代器。

Java集合的快速失敗機制 “fail-fast”？

是java集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會產生 fail-fast 機制。

例如：假設存在兩個線程（線程1、線程2），線程1通過Iterator在遍歷集合A中的元素，在某個時候線程2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這個時候程序就會拋出
ConcurrentModificationException 異常，從而產生fail-fast機制。

原因：迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發生變化，就會改變modCount的值。每當迭代器使用hashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷；否則拋出異常，終止遍歷。

解決辦法：

在遍歷過程中，所有涉及到改變modCount值的地方全部加上synchronized。

使用CopyOnWriteArrayList來替換ArrayList

怎么確保一個集合不能被修改？

可以使用 Collections. unmodifiableCollection(Collection c) 方法來創建一個只讀集合，這樣改變集合的任何操作都會拋出 Java. lang.
UnsupportedOperationException 異常。

Collection接口

List接口

迭代器 Iterator 是什么？

Iterator 接口提供遍歷任何 Collection 的接口。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允許調用者在迭代過程中移除元素。

Iterator 怎么使用？有什么特點？

Iterator 的特點是只能單向遍歷，但是更加安全，因為它可以確保，在當前遍歷的集合元素被更改的時候，就會拋出
ConcurrentModificationException 異常。

如何邊遍歷邊移除 Collection 中的元素？

邊遍歷邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法

Iterator 和 ListIterator 有什么區別？

Iterator 可以遍歷 Set 和 List 集合，而 ListIterator 只能遍歷 List。
Iterator 只能單向遍歷，而 ListIterator 可以雙向遍歷（向前/后遍歷）。
ListIterator 實現 Iterator 接口，然后添加了一些額外的功能，比如添加一個元素、替換一個元素、獲取前面或后面元素的索引位置。

遍歷一個 List 有哪些不同的方式？每種方法的實現原理是什么？Java 中 List 遍歷的最佳實踐是什么？

for 循環遍歷，基于計數器。在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后停止。
迭代器遍歷，Iterator。Iterator 是面向對象的一個設計模式，目的是屏蔽不同數據集合的特點，統一遍歷集合的接口。Java 在 Collections 中支持了 Iterator 模式。
foreach 循環遍歷。foreach 內部也是采用了 Iterator 的方式實現，使用時不需要顯式聲明 Iterator 或計數器。優點是代碼簡潔，不易出錯；缺點是只能做簡單的遍歷，不能在遍歷過程中操作數據集合，例如刪除、替換。

推薦的做法就是，支持 Random Access 的列表可用 for 循環遍歷，否則建議用 Iterator 或 foreach 遍歷。

說一下 ArrayList 的優缺點

優點：隨機訪問快

缺點：插入刪除需復制，耗費性能

如何實現數組和 List 之間的轉換？

數組轉 List：使用 Arrays. asList(array) 進行轉換。
List 轉數組：使用 List 自帶的 toArray() 方法。

ArrayList 和 LinkedList 的區別是什么？

數據結構實現：ArrayList 動態數組，而 LinkedList 雙向鏈表隨機訪問效率：ArrayList 更好增加和刪除效率：LinkedList 更好內存空間占用：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節點除了存儲數據，還存儲了兩個應用線程安全：都不保證線程安全；綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和刪除操作較多時，更推薦使用 LinkedList。

ArrayList 和 Vector 的區別是什么？

線程安全：Vector 使用了 Synchronized 來實現線程同步，是線程安全的，而 ArrayList 是非線程安全的。
性能：ArrayList 在性能方面要優于 Vector。
擴容：ArrayList 和 Vector 都會根據實際的需要動態的調整容量，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%。

插入數據時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存儲性能和特性？

ArrayList、Vector 底層數組方式存儲數據。

LinkedList 雙向鏈表，LinkedList 插入速度較快。

多線程場景下如何使用 ArrayList？

ArrayList 不是線程安全的，如果遇到多線程場景，可以通過 Collections 的 synchronizedList 方法將其轉換成線程安全的容器后再使用

為什么 ArrayList 的 elementData 加上 transient 修飾？

每次序列化時，先調用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍歷 elementData，只序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之后的文件大小。

List 和 Set 的區別

list: 有序元素可重復多個null 有索引 for和iterator 檢索低效插入刪除高效

set: 無序不可重復一個null iterator 查找高效插入刪除低效

Set接口

說一下 HashSet 的實現原理？

HashSet: 底層HashMap hashmap的value統一為PRESENT 底層調用hashmap的方法 hashset不允許重復

HashSet如何檢查重復？HashSet是如何保證數據不可重復的？

檢查重復，不僅比較hash值，還要結合equals方法

值作為hashmap的key，所以不會重復

Queue

BlockingQueue是什么？

阻塞隊列在進行檢索或移除一個元素的時候，它會等待隊列變為非空；當在添加一個元素時，它會等待隊列中的可用空間

在 Queue 中 poll()和 remove()有什么區別？

相同點：返回第一元素，并刪除

不同點：沒有元素，poll返回null remove拋出異常NoSuchElementException

Map接口

說一下 HashMap 的實現原理？

概述： HashMap是基于哈希表的Map接口的非同步實現

數組和鏈表的結合體

1.用key的hashcode作hash計算下標

2.(1)key相同，覆蓋原始值；(2)key不同（出現沖突），key-value放入鏈表

Jdk 1.8中對HashMap的實現做了優化，當鏈表中的節點數據超過八個之后，該鏈表會轉為紅黑樹來提高查詢效率，從原來的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現

JDK1.8之前: 數據+鏈表；之后：鏈表長度大于閾值（默認為8），鏈表轉為紅黑樹

HashMap的put方法的具體流程？

①.判斷鍵值對數組table是否為空或為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可；

⑥.插入成功后，判斷實際存在的鍵值對數量size是否超過了最大容量threshold，如果超過，進行擴容。

HashMap的擴容操作是怎么實現的？

①.在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容；

②.每次擴展的時候，都是擴展2倍；

③.擴展后Node對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。

HashMap是怎么解決哈希沖突的？

什么是哈希：就是把任意長度的輸入通過散列算法，變換成固定長度的輸出，該輸出就是散列值（哈希值）

基本特性：根據同一散列函數計算出的散列值如果不同，那么輸入值肯定也不同。但是，根據同一散列函數計算出的散列值如果相同，輸入值不一定相同

什么是哈希沖突：當兩個不同的輸入值，根據同一散列函數計算出相同的散列值的現象，我們就把它叫做碰撞（哈希碰撞）

HashMap的數據結構：數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易

hash()函數：與自己右移16位進行異或運算（高低位異或）

能否使用任何類作為 Map 的 key？

可以，考慮一下幾點：

1.重寫了 equals() 方法，也應該重寫 hashCode() 方法。

2.遵循與 equals() 和 hashCode() 相關的規則。

3.用戶自定義 Key 類最佳實踐是使之為不可變的

為什么HashMap中String、Integer這樣的包裝類適合作為Key？

1.都是final類型，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況

2.內部已重寫了equals()、hashCode()等方法，遵守了HashMap內部的規范

如果使用Object作為HashMap的Key，應該怎么辦呢？

重寫hashCode()和equals()方法

HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？

hashCode()方法返回的是int整數類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間；哈希值可能不在數組大小范圍內，進而無法匹配存儲位置

HashMap 的長度為什么是2的冪次方

hash%length==hash&(length-1)的前提是 length 是2的 n 次方；

HashMap 與 HashTable 有什么區別？

1.線程安全 hashtable用synchronized修飾

2.效率 hashmap效率高

3.對null key的支持 hashmap可以 hashtable報錯

4.Hashtable 默認大小11，之后擴充，容量為原來2n+1。HashMap 默認大小16。擴充，原來的2倍

如何決定使用 HashMap 還是 TreeMap？

對于在Map中插入、刪除和定位元素，HashMap最好。然而，對一個有序的key集合進行遍歷，TreeMap更好

HashMap 和 ConcurrentHashMap 的區別

1.JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實現,利用CAS算法。

2.hashmap允許null

ConcurrentHashMap 和 Hashtable 的區別？

1.底層數據結構，ConcurrentHashMap：數組+鏈表/紅黑二叉樹；Hashtable：數組+鏈表

2.實現線程安全的方式（重要）：① 在JDK1.7的時候，ConcurrentHashMap（分段鎖）對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高并發訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。）到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，并發控制使用 synchronized 和 CAS 來操作。（JDK1.6以后對 synchronized鎖做了很多優化）整個看起來就像是優化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。

ConcurrentHashMap 底層具體實現知道嗎？實現原理是什么？

JDK1.7: ConcurrentHashMap采用Segment + HashEntry的方式進行實現

JDK1.8: synchronized只鎖定當前鏈表或紅黑二叉樹的首節點

Array 和 ArrayList 有何區別？

Array 存儲基本數據類型和對象，ArrayList 只能存儲對象。Array 是指定固定大小的，而 ArrayList 大小是自動擴展的。Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。

如何實現 Array 和 List 之間的轉換？

Array 轉 List： Arrays. asList(array) ；
List 轉 Array：List 的 toArray() 方法。

comparable 和 comparator的區別？

comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序
comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序

Collection 和 Collections 有什么區別？

java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承接口有List與Set。
Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。

TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？

TreeSet 要求存放的對象所屬的類必須實現 Comparable 接口，該接口提供了比較元素的 compareTo()方法，當插入元素時會回調該方法比較元素的大小。TreeMap 要求存放的鍵值對映射的鍵必須實現 Comparable 接口從而根據鍵對元素進行排序。
Collections 工具類的 sort 方法有兩種重載的形式，

第一種要求傳入的待排序容器中存放的對象比較實現 Comparable 接口以實現元素的比較；

第二種不強制性的要求容器中的元素必須可比較，但是要求傳入第二個參數，參數是Comparator 接口的子類型（需要重寫 compare 方法實現元素的比較），相當于一個臨時定義的排序規則，其實就是通過接口注入比較元素大小的算法，也是對回調模式的應用（Java 中對函數式編程的支持）。

面試造火箭，工作擰螺絲，希望對你有所幫助

多多分享、點贊、評論、收藏、謝謝大家，讓更多人受益！！！