當你停下來休息的時候,不要忘記,別人還在奔跑~
1.List,Set,Map三者的區(qū)別？
- List： List接口存儲一組可重復、有序的對象
- Set: 不允許重復的但可以有序集合。不會有多個元素引用相同的對象。
- Map: 使用鍵值對存儲。Map會維護與Key有關聯(lián)的值。兩個Key可以引用相同的對象，但Key不能重復，典型的Key是String類型，但也可以是任何對象。如果key重復，新的value將覆蓋舊value。
2.Arraylist 與 LinkedList 區(qū)別?
是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
底層數(shù)據(jù)結構： Arraylist 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是 雙向鏈表 數(shù)據(jù)結構。
查詢、插入和刪除時間效率不一樣：
① ArrayList 采用數(shù)組存儲，支持通過下標獲取元素，所以時間復雜度為O(1)。但是插入和刪除元素的時間復雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。
② LinkedList 采用鏈表存儲，獲取元素需要遍歷鏈表，所以時間復雜度為O(N)。但是對于add(E e)方法的插入，刪除元素時間復雜度不受元素位置的影響，近似 O（1），如果是要在指定位置i插入和刪除元素的話（(add(int index, E element)） 時間復雜度近似為o(n))因為需要先移動到指定位置再插入。是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法)。
內存空間占用： ArrayList的空 間浪費主要體現(xiàn)在在list列表的結尾會預留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅以及數(shù)據(jù)）。
3.ArrayList 與 Vector 區(qū)別呢?為什么要用Arraylist取代Vector呢？
- Vector類的所有方法都是同步的?？梢杂蓛蓚€線程安全地訪問一個Vector對象，但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。
- Arraylist不是同步的，所以在不需要保證線程安全時建議使用Arraylist。
- ArrayList每次擴容1.5倍左右，Vector不傳入擴容因子下默認每次擴容2倍。
4.HashMap 和 Hashtable 的區(qū)別
- 線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?；
-
效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException。 -
初始容量大小和每次擴充容量大小的不同 ：
①創(chuàng)建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變?yōu)樵瓉淼?n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變?yōu)樵瓉淼?倍。
②創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大?。℉ashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方。 - 底層數(shù)據(jù)結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。
HashMap 中帶有初始容量的構造函數(shù)：
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
下面這個方法保證了 HashMap 總是使用2的冪作為哈希表的大小。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
5.HashMap 和 HashSet區(qū)別
HashSet 底層就是基于 HashMap 實現(xiàn)的。（HashSet 的源碼非常非常少，因為除了 clone()、writeObject()、readObject()是 HashSet 自己不得不實現(xiàn)之外，其他方法都是直接調用 HashMap 中的方法。
6.HashSet如何檢查重復
當你把對象加入HashSet時，HashSet會先計算對象的hashcode值來判斷對象加入的位置，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode，HashSet會假設對象沒有重復出現(xiàn)。但是如果發(fā)現(xiàn)有相同hashcode值的對象，這時會調用equals（）方法來檢查hashcode相等的對象是否真的相同。如果兩者相同，HashSet就不會讓加入操作成功。
hashCode（）與equals（）的相關規(guī)定：
- 如果兩個對象相等，則hashcode一定也是相同的
兩個對象相等,對兩個equals方法返回true
兩個對象有相同的hashcode值，它們也不一定是相等的
綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋(為了保證確實是同一個對象)
hashCode()的默認行為是對堆上的對象產生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數(shù)據(jù)）。 - ==與equals的區(qū)別
==是判斷兩個變量或實例是不是指向同一個內存空間 equals是判斷兩個變量或實例所指向的內存空間的值是不是相同
==是指對內存地址進行比較 equals()是對字符串的內容進行比較
==指引用是否相同 equals()指的是值是否相同
7.ConcurrentHashMap 和 Hashtable 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同。
-
底層數(shù)據(jù)結構：
①JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結構跟HashMap1.8的結構一樣，數(shù)組+鏈表/紅黑二叉樹。
②Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結構類似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的； -
實現(xiàn)線程安全的方式（重要）：
① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） 對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數(shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭，提高并發(fā)訪問率。 到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結構來實現(xiàn)，并發(fā)控制使用 synchronized 和 CAS 來操作。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結構，但是已經簡化了屬性，只是為了兼容舊版本；
② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態(tài)，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。
集合框架底層數(shù)據(jù)結構總結
Collection
1. List
- Arraylist： Object數(shù)組
- Vector： Object數(shù)組
- LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán))
2. Set
- HashSet（無序，唯一）: 基于 HashMap 實現(xiàn)的，底層采用 HashMap 來保存元素
- LinkedHashSet： LinkedHashSet 繼承于 HashSet，并且其內部是通過 LinkedHashMap 來實現(xiàn)的。有點類似于我們之前說的LinkedHashMap 其內部是基于 HashMap 實現(xiàn)一樣，不過還是有一點點區(qū)別的
- TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹)
Map
- HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）。JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間
- LinkedHashMap： LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現(xiàn)了訪問順序相關邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》
- Hashtable： 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的
- TreeMap： 紅黑樹（自平衡的排序二叉樹）
如何選用集合?
主要根據(jù)集合的特點來選用，比如我們需要根據(jù)鍵值獲取到元素值時就選用Map接口下的集合，需要排序時選擇TreeMap,不需要排序時就選擇HashMap,需要保證線程安全就選用ConcurrentHashMap.當我們只需要存放元素值時，就選擇實現(xiàn)Collection接口的集合，需要保證元素唯一時選擇實現(xiàn)Set接口的集合比如TreeSet或HashSet，不需要就選擇實現(xiàn)List接口的比如ArrayList或LinkedList，然后再根據(jù)實現(xiàn)這些接口的集合的特點來選用。
