HashMap與ConcurrentHashMap的區(qū)別

　　在Java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是模擬指針(引用)，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。

　　1. HashMap實際上是一個“鏈表的數(shù)組”的數(shù)據(jù)結(jié)構(gòu)，每個元素存放鏈表頭結(jié)點的數(shù)組，即數(shù)組和鏈表的結(jié)合體。HashMap底層就是一個數(shù)組，數(shù)組中的每一項又是一個鏈表。當(dāng)新建一個HashMap的時候，就會初始化一個數(shù)組。

　　2. ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數(shù)據(jù)。

　　3. 一個ConcurrentHashMap里包含一個Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個Segment里包含一個HashEntry數(shù)組。

　　4. 每個HashEntry是一個鏈表結(jié)構(gòu)的元素， 每個Segment守護(hù)者一個HashEntry數(shù)組里的元素,當(dāng)對HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時，必須首先獲得它對應(yīng)的Segment鎖。

　　ArrayList 與 LinkedList有什么區(qū)別?

　　因為 Array 是基于索引(index)的數(shù)據(jù)結(jié)構(gòu)，它使用索引在數(shù)組中搜索和讀取數(shù)據(jù)是很快的。Array 獲取數(shù)據(jù)的時間復(fù)雜度是 O(1),但是要刪除數(shù)據(jù)卻是開銷很大的，因為這需要重排數(shù)組中的所有數(shù)據(jù)。

　　相對于 ArrayList，LinkedList 插入是更快的。因為 LinkedList 不像 ArrayList 一樣，不需要改變數(shù)組的大小，也不需要在數(shù)組裝滿的時候要將所有的數(shù)據(jù)重新裝入一個新的數(shù)組，這是 ArrayList 最壞的一種情況，時間復(fù)雜度是 O(n)，而 LinkedList 中插入或刪除的時間復(fù)雜度僅為 O(1)。ArrayList 在插入數(shù)據(jù)時還需要更新索引(除了插入數(shù)組的尾部)。

　　類似于插入數(shù)據(jù)，刪除數(shù)據(jù)時，LinkedList 也優(yōu)于 ArrayList。

　　LinkedList 需要更多的內(nèi)存，因為 ArrayList 的每個索引的位置是實際的數(shù)據(jù)，而 LinkedList 中的每個節(jié)點中存儲的是實際的數(shù)據(jù)和前后節(jié)點的位置。

　　如果你的應(yīng)用經(jīng)常需要隨機(jī)訪問數(shù)據(jù),則考慮使用ArrayList。因為如果需要LinkedList 中的第 n 個元素的時候，你需要從第一個元素順序數(shù)到第 n 個數(shù)據(jù)，然后讀取數(shù)據(jù)。

　　你的應(yīng)用經(jīng)常進(jìn)行插入和刪除元素，更少的讀取數(shù)據(jù),考慮使用LinkedList。因為插入和刪除元素不涉及重排數(shù)據(jù)，所以它要比 ArrayList 要快。

　　更多關(guān)于“Java培訓(xùn)”的問題，歡迎咨詢千鋒教育在線名師。千鋒已有十余年的培訓(xùn)經(jīng)驗，課程大綱更科學(xué)更專業(yè)，有針對零基礎(chǔ)的就業(yè)班，有針對想提升技術(shù)的好程序員班，高品質(zhì)課程助力你實現(xiàn)java程序員夢想。