前言 : 這幾天一直沉迷于HashMap ,LinkedHashMap , ConcurrentHashMap的源碼之中越陷越深.. 這里說明一下 對于源碼這個東西不能太過于詳細(xì)去挖掘 不然就會出現(xiàn)我這幾天這樣的情況 ConcurrentHashMap的原理最讓人難以理解. 推薦大概看一下源碼后找個對應(yīng)的視頻來解惑. 太難了 .. 廢話不多說了 總的來說看了源碼之后收獲還是有的

集合框架

Java集合里使用接口來定義功能，是一套完善的繼承體系。Iterator是所有集合的總接口，其他所有接口都繼承于它，該接口定義了集合的遍歷操作，Collection接口繼承于Iterator，是集合的次級接口（Map獨(dú)立存在），定義了集合的一些通用操作。

集合框架體系圖png

• set 無序 不可重復(fù) ,重復(fù)元素會蓋掉 繼承于Collection接口 (元素雖然無放入順序，但是元素在set中位置是由該元素的HashCode決定的，其位置其實(shí)是固定，加入Set的Object必須定義equals()方法;) 檢索元素效率低下，刪除和插入效率高，插入和刪除不會引起元素位置改變

• list 有序 可重復(fù) 插入和刪除過程伴隨著數(shù)據(jù)的移動 繼承于Collection接口,另外list支持for循環(huán)，也就是通過下標(biāo)來遍歷，也可以使用迭代器Iterator, 和數(shù)組類似，List可以動態(tài)增長，查找元素效率高,插入和刪除比較慢

• Map：映射鍵值對，鍵唯一，值多個

• 并發(fā)問題

  	HashSet	Vector	ArrayList	LinkedList	HashMap
  線程安全		安全			不安全
  線程不安全	不安全		不安全	不安全
  是否重復(fù)	不重復(fù)	可以	可以	可以	(key)不重復(fù)
  是否有序	無序	有序	有序	有序	無序

ArrayList , LinkedList和Vector的區(qū)別

• ArrayList

  • 優(yōu)點(diǎn)：ArrayList是實(shí)現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu),因地址連續(xù)，一旦數(shù)據(jù)存儲好了，查詢操作效率會比較高（在內(nèi)存里是連著放的）。

  • 缺點(diǎn): ArrayList要移動數(shù)據(jù),所以插入和刪除操作效率比較低

  • 適用場景:當(dāng)需要對數(shù)據(jù)進(jìn)行對應(yīng)訪問的情況下選用ArrayList 插入數(shù)據(jù)效率一般 不代表不用使用

• LinkedList

  • 優(yōu)點(diǎn):LinkedList 基于鏈表的數(shù)據(jù)結(jié)構(gòu) 地址是任意的, 對于新增和刪除數(shù)據(jù)有較好的性能

  • 缺點(diǎn): 查詢較慢 因?yàn)?code>LinkedList插敘需要移動指針 詳情見LinkedList簡述

  • 適用場景 :對數(shù)據(jù)對此進(jìn)行添加和刪除操作時采用linkedList性能較高

• Vector

  • 優(yōu)點(diǎn):Vector是多線程安全的,Vector可以設(shè)置增長因子

  • 缺點(diǎn):Vector是一種老的動態(tài)數(shù)組，是線程同步的使用悲觀鎖synchronied，效率很低，一般不贊成使用

  • 適用場景 :和ArrayList如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時，在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù)，用Vector有一定的優(yōu)勢。一般不使用Vector

ArrayList和LinkedList的動態(tài)擴(kuò)容

• ArrayList

  • ArrayList的初始大小為0, 當(dāng)添加第一個元素時候數(shù)組大小變成10 在后續(xù)擴(kuò)容的時候會變成之前容量的1.5倍

  • 數(shù)組的擴(kuò)容 只能新建一個指定容量的數(shù)組然后對數(shù)組進(jìn)行元素的賦值

• LinkedList

  • LinkedList 雙向鏈表 沒有初始化大小, 也沒有擴(kuò)容機(jī)制 添加元素只需要移動指針即可

HashSet和TreeSet的區(qū)別

• HashSet

  • 優(yōu)點(diǎn) 基于哈希表實(shí)現(xiàn)的,允許有一個Null 無序不可重復(fù)

  • 缺點(diǎn) :HashSet中存放的數(shù)據(jù)必須實(shí)現(xiàn)HashCode() 放入對象是以hashCode為標(biāo)識 不能存放hashCode相同元素

  • 適用場景 :HashSet基于hash算法實(shí)現(xiàn) 為了快速查找使用 HashSet

• TreeSet

  • 優(yōu)點(diǎn) 基于紅黑樹實(shí)現(xiàn) TreeSet中存放的數(shù)據(jù)時自動排序好的

  • 缺點(diǎn) 不允許有null

  • 適用場景 排序功能使用TreeSet

set集合為何能保證元素不重復(fù)

• 在往set中添加元素時，如果指定元素不存在，則添加成功。

• 當(dāng)向HashSet中添加元素時 首先會計算出元素的HashCode值,然后用這個元素的HashCode/hashset集合的大小(size)+1 得出元素的存儲位置, 如果這個位置為空,直接添加到這個位置,不為空,用equals比較二個元素是否相等,相等就不添加 則否找一個空的位置添加

HashMap與TreeMap、HashTable的區(qū)別及適用場景( 重點(diǎn))

• HashMap

  • 優(yōu)點(diǎn): HashMap允許空鍵值 允許一個null鍵和多個null值 基于哈希表實(shí)現(xiàn),

  • 缺點(diǎn):

    • 非線程安全 ,

    • 使用HashMap要求的鍵類明確定義了hashCode()和equals()可以重寫hasCode()和equals()，為了優(yōu)化HashMap空間的使用，您可以調(diào)優(yōu)初始容量和負(fù)載因子,

    • 散列表的沖突處理主分兩種，一種是開放定址法，另一種是鏈表法。HashMap實(shí)現(xiàn)中采用的是鏈表法。

    • HashMap沒有排序

  • 適用場景 適用于Map中插入、刪除和定位元素。

• TreeMap

  • 優(yōu)點(diǎn) :安全基于紅黑樹實(shí)現(xiàn)

  • 缺點(diǎn) 非線程

  • 適用場景 適用于按自然順序或自定義順序遍歷鍵(key)

• HashTable

  • 優(yōu)點(diǎn) HashTable是同步的

  • 缺點(diǎn) HashTable不允許Null鍵。

  • 適用場景 HashTable是同步的

• HashMap和HashTable的主要區(qū)別

  • HashMap沒有排序，允許一個null鍵和多個null 值,而Hashtable 不允許

  • HashMap 把Hashtable 的contains 方法去掉了，改成containsvalue 和containsKey, 因?yàn)閏ontains 方法容易讓人引起誤解；

  • Hashtable 繼承自Dictionary 類，HashMap 是Jdk1.2 引進(jìn)的Map 接口的實(shí)現(xiàn)；

  • Hashtable 的方法是Synchronized 的，而HashMap 不是，在多個線程訪問Hashtable 時，不需要自己為它的方法實(shí)現(xiàn)同步，而HashMap 就必須為之提供額外的同步。Hashtable和HashMap 采用的hash/rehash 算法大致一樣，所以性能不會有很大的差異。

  • HashMap和Hashtable的底層實(shí)現(xiàn)都是數(shù)組 + 鏈表(+紅黑樹 ---jdk8)結(jié)構(gòu)實(shí)現(xiàn)的