集合

List 和 Set 區(qū)別

• List 可以重復(fù)，set不可以斋否，list有序枫耳，set有的實(shí)現(xiàn)類是無(wú)序的

• List 實(shí)現(xiàn)類：

  • ArrayList：提供了使用索引的隨意訪問(wèn)怨咪，底層是數(shù)組屋剑，線程不安全

    • new的時(shí)候capacity是0 ,add的時(shí)候加載默認(rèn) capacity 10

  • LinkedList：提供了添加刪除的便捷操作，底層是鏈表诗眨，

  • Vector：可實(shí)現(xiàn)自動(dòng)增長(zhǎng)的對(duì)象數(shù)組唉匾。表示底層數(shù)組，線程安全

    • elementData 是"Object[]類型的數(shù)組"匠楚，它保存了添加到Vector中的元素肄鸽。elementData是個(gè)動(dòng)態(tài)數(shù)組，如果初始化Vector時(shí)油啤，沒指定動(dòng)態(tài)數(shù)組的>大小，則使用默認(rèn)大小10蟀苛。隨著Vector中元素的增加益咬，Vector的容量也會(huì)動(dòng)態(tài)增長(zhǎng)，capacityIncrement是與容量增長(zhǎng)相關(guān)的增長(zhǎng)系數(shù)帜平，具體的增長(zhǎng)方式幽告，請(qǐng)參考源碼分析中的ensureCapacity()函數(shù)。

    • elementCount 是動(dòng)態(tài)數(shù)組的實(shí)際大小裆甩。

    • capacityIncrement 是動(dòng)態(tài)數(shù)組的增長(zhǎng)系數(shù)冗锁。如果在創(chuàng)建Vector時(shí)，指定了capacityIncrement的大朽退ā冻河；則，每次當(dāng)Vector中動(dòng)態(tài)數(shù)組容量增加時(shí)>茉帅，增加的大小都是capacityIncrement叨叙。

• set實(shí)現(xiàn)類

  • Set集合判斷元素是否是同一個(gè)使用的是equals方法
  • HashSet：調(diào)用該對(duì)象的hashCode()方法來(lái)得到該對(duì)象的hashCode值，然后根據(jù) hashCode值來(lái)決定該對(duì)象在HashSet中存儲(chǔ)位置
  • LinkedHashSet：集合同樣是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置堪澎，但是它同時(shí)使用鏈表維護(hù)元素的次序擂错。當(dāng)遍歷該集合時(shí)候，LinkedHashSet將會(huì)以元素的添加順序訪問(wèn)集合的元素樱蛤。 LinkedHashSet在迭代訪問(wèn)Set中的全部元素時(shí)钮呀，性能比HashSet好，但是插入時(shí)性能稍微遜色于HashSet昨凡。
  • TreeSet：是SortedSet接口的唯一實(shí)現(xiàn)類爽醋，底層的數(shù)據(jù)結(jié)構(gòu)是紅黑樹，TreeSet可以確保集合元素處于排序狀態(tài)土匀。TreeSet支持兩種排序方式子房，自然排序 和定制排序。
    • 自然排序：使用要排序元素的CompareTo（Object obj）方法來(lái)比較元素之間大小關(guān)系，然后將元素按照升序排列证杭。
    • 定制排序：應(yīng)該使用Comparator接口田度，實(shí)現(xiàn) int compare(T o1,T o2)方法。

• 相互轉(zhuǎn)換：

  • 因?yàn)長(zhǎng)ist和Set都實(shí)現(xiàn)了Collection接口的addAll(Collection<? extends E> c)方法解愤，因此可以采用addAll()方法將List和Set互相轉(zhuǎn)換镇饺；另外，List和Set也提供了Collection<? extends E> c作為參數(shù)的構(gòu)造函數(shù)送讲，因此通常采用構(gòu)造函數(shù)的形式完成互相轉(zhuǎn)化奸笤。

List 和 Map的區(qū)別

• 存儲(chǔ)特點(diǎn)：

  • list是存儲(chǔ)單列數(shù)據(jù)的集合，map是存儲(chǔ)鍵和(key,value)}這樣的雙列數(shù)據(jù)的集合哼鬓，List 中存

  儲(chǔ)的數(shù)據(jù)是有順序监右，并且允許重復(fù)；Map 中存儲(chǔ)的數(shù)據(jù)是沒有順序的异希，其鍵是不能重復(fù)的健盒，

  它的值是可以有重復(fù)的。

ArrayList和LinkedList和Vector區(qū)別

• ArrayList：

  • 線程不安全称簿，（沒有在添加元素的地方加鎖扣癣，會(huì)有值覆蓋和數(shù)組越界的情況發(fā)生）。
  • 屬性信息：capacity：默認(rèn)是10 （new的時(shí)候憨降，長(zhǎng)度是0父虑，add元素后讀取默認(rèn)長(zhǎng)度）。
  • 擴(kuò)容：
    • 條件：長(zhǎng)度不夠的時(shí)候授药。
    • 擴(kuò)容后士嚎，長(zhǎng)度為原來(lái)長(zhǎng)度的 1.5倍。
  • 底層是數(shù)組烁焙，優(yōu)勢(shì)是便利航邢，劣勢(shì)是修改元素。占用內(nèi)存是連續(xù)的骄蝇。

• LinkedList：

  • 線程不安全的膳殷，（添加元素時(shí)倒數(shù)第二個(gè)指向后一個(gè)的元素會(huì)被最后一次覆蓋，造成丟失）九火，（操作數(shù)modCount和expectmodCount不等）
  • 屬性信息：僅僅是指針的指向赚窃，不存在capacity
  • 表面上實(shí)現(xiàn)了list，背地里還是一個(gè)隊(duì)列岔激。
  • 底層書雙向鏈表勒极，優(yōu)勢(shì)修改新增快，便利慢虑鼎。不依賴連續(xù)內(nèi)存空間辱匿。

• ArrayList主要控件開銷在于需要在lList列表預(yù)留一定空間键痛；而LinkList主要控件開銷在于需要存儲(chǔ)結(jié)點(diǎn)信息以及結(jié)點(diǎn)指針信息

• Vector：線程安全

  • Vector與ArrayList一樣，也是通過(guò)數(shù)組實(shí)現(xiàn)的匾七，不同的是它支持線程的同步絮短，即某一時(shí)刻只有一個(gè)線程能夠?qū)慥ector，避免多線程同時(shí)寫而引起的不一致性昨忆，但實(shí)現(xiàn)同步需要很高的花費(fèi)丁频，因此，訪問(wèn)它比訪問(wèn)ArrayList慢邑贴。
  • 擴(kuò)容時(shí)長(zhǎng)度為原來(lái)的兩倍

HashMap 和HashTable的區(qū)別

• HashMap:
  • 不是線程安全的席里，可以允許null key 和null value。
• HashTable
  • 線程安全的拢驾，不可以允許null key 也不可以有 null value奖磁。

HashSet 和 HashMap區(qū)別

• hashmap 存儲(chǔ)的時(shí)鍵值對(duì)，hashset存儲(chǔ)的是對(duì)象
• 使用hashset的時(shí)候繁疤，最好優(yōu)先重寫 hashcode 和 equals

HashMap和Concurrent HashMap的區(qū)別

• ConcurrentHashMap對(duì)整個(gè)桶數(shù)組進(jìn)行了分段署穗，而HashMap則沒有

• ConcurrentHashMap在每一個(gè)分段上都用鎖進(jìn)行保護(hù)，從而讓鎖的粒度更精細(xì)一些嵌洼，并發(fā)性能更好，而HashMap沒有鎖機(jī)制封恰，不是線程安全的麻养。

HashMap的工作原理及代碼實(shí)現(xiàn)

• 容量和負(fù)載因子：容量的默認(rèn)大小是 16，負(fù)載因子是 0.75

• 內(nèi)部包含了一個(gè) Entry 類型的數(shù)組 table诺舔。HashMap的主干是一個(gè)Entry數(shù)組鳖昌。Entry是HashMap的基本組成單元，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)低飒。

• 哈希沖突的解決方案有多種:開放定址法（發(fā)生沖突许昨，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址），再散列函數(shù)法褥赊，鏈地址法糕档，而HashMap即是采用了鏈地址法，也就是數(shù)組+鏈表的方式拌喉。（jdk8中鏈表為8時(shí)轉(zhuǎn)為紅黑樹存儲(chǔ)速那，長(zhǎng)度低于6轉(zhuǎn)回來(lái)）

• 擴(kuò)容為原來(lái)的2倍大小。

• 簡(jiǎn)單來(lái)說(shuō)尿背，HashMap由數(shù)組+鏈表組成的端仰，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的田藐，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對(duì)于查找荔烧，添加等操作很快吱七，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表鹤竭，對(duì)于添加操作踊餐，其時(shí)間復(fù)雜度為O(n)，首先遍歷鏈表诺擅，存在即覆蓋市袖，否則新增；對(duì)于查找操作來(lái)講烁涌，仍需遍歷鏈表苍碟，然后通過(guò)key對(duì)象的equals方法逐一比對(duì)查找。所以撮执，性能考慮微峰，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好

• 在常規(guī)構(gòu)造器中抒钱，沒有為數(shù)組table分配內(nèi)存空間（有一個(gè)入?yún)橹付∕ap的構(gòu)造器例外）蜓肆，而是在執(zhí)行put操作的時(shí)候才真正構(gòu)建table數(shù)組。

• capacity一定是 2的次冪

  為何HashMap的數(shù)據(jù)長(zhǎng)度一定是2的次冪谋币？