參考答案

Java 容器分為 Collection 和 Map 兩大類，各自都有很多子類。

可以比較的點(diǎn)：

• 有序、無(wú)序

• 可重復(fù)、不可重復(fù)

• 鍵、值是否可為null

• 底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)（數(shù)組、鏈表、哈希...）

• 線程安全性

------------------------------------------------------------------------

• List：有序集合，元素可重復(fù)

• Set：不重復(fù)集合，LinkedHashSet按照插入排序，SortedSet可排序，HashSet無(wú)序

• Map：鍵值對(duì)集合，存儲(chǔ)鍵、值和之間的映射；Key無(wú)序，唯一；value 不要求有序，允許重復(fù)

參考答案

相同點(diǎn)：

• 底層都使用數(shù)組實(shí)現(xiàn)

• 功能相同，實(shí)現(xiàn)增刪改查等操作的方法相似

• 長(zhǎng)度可變的數(shù)組結(jié)構(gòu)

不同點(diǎn)：

• Vector是早期JDK版本提供，ArrayList是新版本替代Vector的

• Vector 的方法都是同步的，線程安全；ArrayList 非線程安全，但性能比Vector好

• 默認(rèn)初始化容量都是10，Vector 擴(kuò)容默認(rèn)會(huì)翻倍，可指定擴(kuò)容的大??；ArrayList只增加 50%

參考答案

JDK 1.8 中 HashMap 和 Hashtable 主要區(qū)別如下：

• 線程安全性不同。HashMap線程不安全；Hashtable 中的方法是Synchronize的，線程安全。
• key、value是否允許null。HashMap的key和value都是可以是null，key只允許一個(gè)null；Hashtable的key和value都不可為null。
• 迭代器不同。HashMap的Iterator是fail-fast迭代器；Hashtable還使用了enumerator迭代器。
• hash的計(jì)算方式不同。HashMap計(jì)算了hash值；Hashtable使用了key的hashCode方法。
• 默認(rèn)初始大小和擴(kuò)容方式不同。HashMap默認(rèn)初始大小16，容量必須是2的整數(shù)次冪，擴(kuò)容時(shí)將容量變?yōu)樵瓉?lái)的2倍；Hashtable默認(rèn)初始大小11，擴(kuò)容時(shí)將容量變?yōu)樵瓉?lái)的2倍加1。
• 是否有contains方法。HashMap沒(méi)有contains方法；Hashtable包含contains方法，類似于containsValue。
• 父類不同。HashMap繼承自AbstractMap；Hashtable繼承自Dictionary。
  
  

• 深入的細(xì)節(jié)，可以參考：

  https://www.cnblogs.com/williamjie/p/9099141.html

參考答案

• 隊(duì)列中的add（）和offer（）都是向尾部添加一個(gè)元素的。

• 在容量已滿的情況下，add（）方法會(huì)引發(fā)IllegalStateException異常，offer（）方法只會(huì)返回false。

同樣地：

• 隊(duì)列中remove（）和poll（）都是從串行頭部刪除一個(gè)元素。

• 在某種元素為空的情況下，remove（）方法會(huì)引發(fā)NoSuchElementException異常，poll（）方法只會(huì)返回null。

• 隊(duì)列中element（）和peek（）都是用來(lái)返回初始化的頭元素，不刪除。

• 在某種元素為空的情況下，element（）方法會(huì)引發(fā)NoSuchElementException異常，peek（）方法只會(huì)返回null。

參考答案

• Vector

• Stack

• Hashtable

• java.util.concurrent 包下所有的集合類 ArrayBlockingQueue、ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque...

參考答案

• Java中是使用泛型來(lái)約束 HashMap 中的key和value的類型的，HashMap

• 泛型在Java的規(guī)定中必須是對(duì)象Object類型的，基本數(shù)據(jù)類型不是Object類型，不能作為鍵值

• map.put(0, "kun")中編譯器已將 key 值 0 進(jìn)行了自動(dòng)裝箱，變?yōu)榱?Integer 類型

參考答案

數(shù)組的優(yōu)點(diǎn)：

• 數(shù)組的效率高于集合類

• 數(shù)組能存放基本數(shù)據(jù)類型和對(duì)象；集合中只能放對(duì)象

  
  

數(shù)組的缺點(diǎn)：

• 不是面向?qū)ο蟮?/span>，存在明顯的缺陷

• 數(shù)組長(zhǎng)度固定且無(wú)法動(dòng)態(tài)改變；集合類容量動(dòng)態(tài)改變

• 數(shù)組無(wú)法判斷其中實(shí)際存了多少元素，只能通過(guò)length屬性獲取數(shù)組的申明的長(zhǎng)度

• 數(shù)組存儲(chǔ)的特點(diǎn)是順序的連續(xù)內(nèi)存；集合的數(shù)據(jù)結(jié)構(gòu)更豐富

JDK 提供集合的意義：

• 集合以類的形式存在，符合面向?qū)ο?，通過(guò)簡(jiǎn)單的方法和屬性調(diào)用可實(shí)現(xiàn)各種復(fù)雜操作

• 集合有多種數(shù)據(jù)結(jié)構(gòu)，不同類型的集合可適用于不同場(chǎng)合

• 彌補(bǔ)了數(shù)組的一些缺點(diǎn)，比數(shù)組更靈活、實(shí)用，可提高開(kāi)發(fā)效率

參考答案

• HashMap 基于 Hash 算法實(shí)現(xiàn)，通過(guò) put(key,value) 存儲(chǔ)，get(key) 來(lái)獲取 value

• 當(dāng)傳入 key 時(shí)，HashMap 會(huì)根據(jù) key，調(diào)用 hash(Object key) 方法，計(jì)算出 hash 值，根據(jù) hash 值將 value 保存在 Node 對(duì)象里，Node 對(duì)象保存在數(shù)組里

• 當(dāng)計(jì)算出的 hash 值相同時(shí)，稱之為 hash 沖突，HashMap 的做法是用鏈表和紅黑樹(shù)存儲(chǔ)相同 hash 值的 value

• 當(dāng) hash 沖突的個(gè)數(shù)：小于等于 8 使用鏈表；大于 8 時(shí)，使用紅黑樹(shù)解決鏈表查詢慢的問(wèn)題，當(dāng)紅黑樹(shù)的節(jié)點(diǎn)數(shù)超過(guò)6的時(shí)候會(huì)變成鏈表。

ps：

• 上述是 JDK 1.8 HashMap 的實(shí)現(xiàn)原理，并不是每個(gè)版本都相同，比如 JDK 1.7 的 HashMap 是基于數(shù)組 + 鏈表實(shí)現(xiàn)，所以 hash 沖突時(shí)鏈表的查詢效率低

• hash(Object key)? 方法的具體算法是?(h = key.hashCode()) ^ (h >>> 16)，經(jīng)過(guò)這樣的運(yùn)算，讓計(jì)算的 hash 值分布更均勻

  
  

參考答案

HashMap 是線程不安全的，效率高；HashTable 是線程安全的，效率低。

ConcurrentHashMap 可以做到既是線程安全的，同時(shí)也可以有很高的效率，得益于使用了分段鎖

實(shí)現(xiàn)原理

JDK 1.7：

• ConcurrentHashMap 是通過(guò)數(shù)組 + 鏈表實(shí)現(xiàn)，由 Segment 數(shù)組和 Segment 元素里對(duì)應(yīng)多個(gè) HashEntry 組成

• value 和鏈表都是 volatile 修飾，保證可見(jiàn)性

• ConcurrentHashMap 采用了分段鎖技術(shù)，分段指的就是 Segment 數(shù)組，其中 Segment 繼承于 ReentrantLock（可重入鎖）

• 理論上 ConcurrentHashMap 支持 CurrencyLevel (Segment 數(shù)組數(shù)量)的線程并發(fā)，每當(dāng)一個(gè)線程占用鎖訪問(wèn)一個(gè) Segment 時(shí)，不會(huì)影響到其他的 Segment

put 方法的邏輯較復(fù)雜：

• 嘗試加鎖，加鎖失敗 scanAndLockForPut 方法自旋，超過(guò) MAX_SCAN_RETRIES 次數(shù)，改為阻塞鎖獲取

• 將當(dāng)前 Segment 中的 table 通過(guò) key 的 hashcode 定位到 HashEntry

• 遍歷該 HashEntry，如果不為空則判斷傳入的 key 和當(dāng)前遍歷的 key 是否相等，相等則覆蓋舊的 value

• 不為空則需要新建一個(gè) HashEntry 并加入到 Segment 中，同時(shí)會(huì)先判斷是否需要擴(kuò)容

• 最后釋放所獲取當(dāng)前 Segment 的鎖

get 方法較簡(jiǎn)單：

• 將 key 通過(guò) hash 之后定位到具體的 Segment，再通過(guò)一次 hash 定位到具體的元素上

• 由于 HashEntry 中的 value 屬性是用 volatile 關(guān)鍵詞修飾的，保證了其內(nèi)存可見(jiàn)性

JDK 1.8：

• 拋棄了原有的 Segment 分段鎖，采用了 CAS + synchronized 來(lái)保證并發(fā)安全性

• HashEntry 改為 Node，作用相同

• val next 都用了 volatile 修飾

put 方法邏輯：

• 根據(jù) key 計(jì)算出 hash 值

• 判斷是否需要進(jìn)行初始化

• 根據(jù) key 定位出的 Node，如果為空表示當(dāng)前位置可以寫(xiě)入數(shù)據(jù)，利用 CAS 嘗試寫(xiě)入，失敗則自旋

• 如果當(dāng)前位置的 hashcode == MOVED == -1，則需要擴(kuò)容

• 如果都不滿足，則利用 synchronized 鎖寫(xiě)入數(shù)據(jù)

• 如果數(shù)量大于 TREEIFY_THRESHOLD 則轉(zhuǎn)換為紅黑樹(shù)

get 方法邏輯：

• 根據(jù)計(jì)算出來(lái)的 hash?值尋址，如果在桶上直接返回值

• 如果是紅黑樹(shù)，按照樹(shù)的方式獲取值

• 如果是鏈表，按鏈表的方式遍歷獲取值

?

JDK 1.7 到 JDK 1.8 中的 ConcurrentHashMap 最大的改動(dòng)：

• 鏈表上的 Node 超過(guò) 8 個(gè)改為紅黑樹(shù)，查詢復(fù)雜度 O(logn)

• ReentrantLock 顯示鎖改為 synchronized，說(shuō)明 JDK 1.8 中 synchronized 鎖性能趕上或超過(guò) ReentrantLock

參考答案

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 測(cè)試剔除List的相同元素
 * @date 2019-11-06 16:33:17
 */
public class TestRemoveListSameElement {

	public static void main(String[] args) {
		List l = Arrays.asList("1", "2", "3", "1");
		Set s = new HashSet(l);
		System.out.println(s);
	}
	
}

更多信息請(qǐng)關(guān)注公眾號(hào)：「軟件老王」，關(guān)注不迷路，軟件老王和他的IT朋友們，分享一些他們的技術(shù)見(jiàn)解和生活故事。