集合概念
集合與數組
數組是固定長度；集合是動態長度的數據結構，需要動態增加或刪除元素
數組可以包含基本數據類型和對象；集合只能包含對象
數組可以直接訪問元素；集合需要通過迭代器訪問元素
線程安全的集合？
java.util包：
- Vector：線程安全的動態數組，內部方法大部分都經過synchronized修飾
- Hashtable：線程安全的哈希表，內部方法大部分都經過synchronized修飾，這樣被所著的就是整個Table對象（底層是數組+鏈表）
并發Map：
- ConcurrentHashMap：
- JDK7，ConcurrentMap加的是分段鎖（Segment鎖），每個分段鎖含有整個table的一部分，不同分段之間的并發互不影響【每個Segment都類似一個小的HashMap，對于插入、更新、刪除操作時，需要先定位到具體的Segment，再在Segment上加鎖】
- JDK8，取消了Segment字段，直接在table元素上枷鎖，實現對每一行進行加鎖，進一步減少了并發沖突。主要通過volatile + CAS（樂觀鎖）或 synchronized（悲觀鎖）來實現的線程安全。
添加元素時，先判斷容器是否為空：
- 為空：直接使用volatile + CAS來初始化
- 不為空：根據存儲的元素計算該位置是否為空
- 如果存儲的元素計算結果為空，利用CAS設置該節點
- 如果存儲的元素計算結果不為空，使用synchronized，然后遍歷桶中的元素，并替換或新增節點到桶中，再判斷是否需要轉成紅黑樹。（當發生hash碰撞時說明容量不夠用或已經有大量線程訪問，因此使用synchronized來處理hash比CAS效率高）
- ConcurrentSkipListMap：實現了一個基于跳表（SkipList）算法的可排序的并發集合，通過維護多個指向其他元素的跳躍鏈接來實現高效查詢
并發Set：
- ConcurrentSkipListSet：線程安全的有序集合，底層是使用ConcurrentSkipListMap實現
- CopyOnWriteArraySet：線程安全的HashSet
并發List：
- CopyOnWriteArrayList：線程安全的ArrayList，底層通過一個數組保存數據，使用volatile關鍵字修飾數組，保證當前線程對數組對象重新賦值后，其他線程可以感知到；在寫入新元素時，會將原來的數組拷貝一份并讓原來數組的長度+1后就得到一個新數組，將元素放入新數組的最后一個位置，用新數組地址替換舊數組地址就能得到最新數據了；讀操作時不加鎖，一直都能讀的。
并發Queue：
- ConcurrentLinkedQueue：高并發場景下的隊列，通過無鎖（CAS）的方式，實現高并發狀態下的高性能。
- BlockingQueue：提供一種讀寫等待的機制，簡化多線程間的數據共享。
并發Deque：
-
LinkedBlockingDeque：線程安全的雙端隊列，內部使用雙向鏈表結構
-
ConcurrentLinkedQueue：基于鏈表節點的無限并發鏈表，可以安全的并發執行插入、刪除、訪問的操作
List
ArrayList是線程安全的嘛？有什么辦法可以把ArrayList變成線程安全的？
- 使用Collections類的synchronizedList方法將ArrayList包裝成線程安全的List
List<String> synchronizedList = Collections.synchronizedList(arrayList);
- 使用CopyOnWriteArrayList（這是一個線程安全的List）代替ArrayList
CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);
- 使用Vector類代替ArrayList
Vector<String> vector = new Vector<>(arrayList);
Map
HashMap是線程安全的嗎？
HashMap不是線程安全的，在多線程環境下會存在以下問題：
- JDK7，采用數組+鏈表，多線程環境下，數組擴容時會存在Entry鏈死循環和數據丟失的問題
- JDK8，采用數組+鏈表+紅黑樹，解決了Entry鏈死循環和數據丟失的問題，但是多線程環境下，put元素會出現覆蓋的情況
保證線程安全：
- 使用Collections.synchronizedMap同步加鎖的方式，還可以使用HashTable。
- 使用ConcurrentHashMap。（JDK7使用分段鎖；JDK8使用CAS+synchronized）
HashMap一般用什么作為Key？為什么String適合做key？
用String做key，因為String對象是不可變的，一旦創建舊不能被修改，保證了key的穩定性。如果key是可變的，會導致hashCode和equals方法的不一致。
為什么HashMap要用紅黑樹而不是平衡二叉樹？
平衡二叉樹追求的是絕對平衡，導致每次在插入或刪除節點時，都需要通過左旋或右旋來調整，使它再次稱為一顆符合要求的平衡二叉樹
紅黑樹不支持這種完全平衡的規則， 犧牲了一部分的查找效率，但是可以換取一部分維持平衡狀態的成本。
HashMap的key可以為null嘛
HashMap使用hash()方法來計算key的哈希值，當key為空時，直接設置hash值為0，不走hashCode方法。
static final int hash(){return (key == null) ? 0 : 走hashCode()后處理
}
null作為key只能有一個，作為value可以有多個
重寫HashMap的equals和hashCode方法需要注意什么？
從HashMap中獲取值時，這些方法也會被用到，如果這些方法沒有被正確的實現，兩個不同的Key可能會產生相同的hashCode()和equals()輸出，HashMap會認為他們是相同的，把他們存在不同的地方。
重寫HashMap的equals方法不當會出現什么情況？
HashMap在比較元素時，先比較hashCode方法，如果hash值相同，再比較equals方法。
如果重寫hashCode方法，但是不重寫equals方法，會出現equals方法返回false，導致hashMap中存儲多個一樣的對象，與hashMap只有唯一的key的規范不符合。
HashMap在多線程下可能出現的問題？
- JDK7使用頭插法插入元素，多線程環境下，擴容時可能導致環形鏈表的出現，形成死循環。因此JDK8使用尾插法插入元素，在擴容時保持鏈表原本的順序不變，不會出現環形鏈表的問題
因為JDK7使用頭插法，對數組長度進行擴容時，如果原來是1->2->3，擴容后就會變成3->2->1
如果多個線程同時對HashMap進行擴容操作，可能會導致鏈表的指針混亂，形成環形鏈表。
- 多線程同時執行put操作，如果計算出來的索引位置是想通的，那會造成前一個key被后一個key覆蓋，從而導致元素丟失的問題
HashMap的擴容機制
在擴充HashMap時，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0
索引 = (數組下標 - 1) & 哈希值
- 如果是0：索引沒變
- 如果是1：索引 = 原索引 + 舊容量
所以HashMap的大小是2的n次方，這樣就不需要重新計算hash值。
HashMap和HashTable的區別
- HashMap線程不安全，可以存儲null的key和value，每次擴容成原來的2n，要保證線程安全也可以用ConcurrentHashMap。
- HashTable線程安全，所有的方法都加synchronized鎖，不可以有null的key和value，效率低，每次擴容為原來的2n + 1。
HashTable和ConcurrentHashMap的區別？
- ConcurrentHashMap是線程安全的。讀操作不需要加鎖，寫操作需要加鎖。JDK7，ConcurrentHashMap采用數組 + 鏈表，并發控制用分段鎖；JDK8，ConcurrentHashMap采用數組 + 鏈表 + 紅黑樹，并發控制用CAS + synchronized
- HashTable采用的是數組 + 鏈表，所有的方法都加synchronized鎖
Set
Set集合的特點？
Set集合是唯一的，不會有重復的元素。
向Set集合中插入元素時，先通過hashCode確定元素的存儲位置，再通過equals判斷是否存在相同的元素，如果存在不會再次插入。
有序Set是什么？
有序的Set是TreeSet和LinkedHashSet
- TreeSet是基于紅黑樹來保證元素的自然順序
- LinkedHashSet是基于雙向鏈表和哈希表的結合來保證元素添加的自然順序（可以記錄插入順序的集合，不僅保證元素的唯一性，還可以保證元素的插入順序）
排序技術)
)
