1、java集合分類

• 線程安全的集合對(duì)象：
  Vector ：是ArrayList的線程安全的實(shí)現(xiàn)
  HashTable
  StringBuffer
• 線程不安全的集合對(duì)象
  ArrayList 、LinkedList、HashMap、HashSet、TreeMap、TreeSet、StringBulider；

image.png

image.png

2、ArrayList 和LinkedList 區(qū)別

https://www.cnblogs.com/sierrajuan/p/3639353.html

ArrayList 實(shí)際上是封裝了對(duì)數(shù)組的操作，而LinkedList是采用鏈表的數(shù)據(jù)結(jié)構(gòu)，兩者截然不同的實(shí)現(xiàn)方式

ArrayList屬性：元素?cái)?shù)組，數(shù)組容量； LinkedList屬性：頭節(jié)點(diǎn)，尾節(jié)點(diǎn)，鏈表長(zhǎng)度（節(jié)點(diǎn)包含屬性：前驅(qū)節(jié)點(diǎn)，后去節(jié)點(diǎn)，元素內(nèi)容）；

由于ArrayList實(shí)際上就是一個(gè)數(shù)組（一塊連續(xù)的內(nèi)存空間，如果在數(shù)組的任意位置插入元素，必然導(dǎo)致在該位置后的所有元素需要重新排列），當(dāng)添加元素的都會(huì)判斷是否需要擴(kuò)容，所以添加性能低，但是讀取性能高；

而LinkedList采用鏈表，添加的直接往最后一個(gè)元素添加即可，所 以添加性能高，但是讀取的時(shí)候要根據(jù)序號(hào)遍歷到對(duì)應(yīng)的節(jié)點(diǎn)獲取，所以讀取性能低；

3、HashMap的實(shí)現(xiàn)原理

entry數(shù)組+鏈表 的實(shí)現(xiàn)方式；根據(jù)一定的算法，將數(shù)據(jù)散列的分配到數(shù)組里，數(shù)組中的節(jié)點(diǎn)采用鏈表的方式存儲(chǔ)多條數(shù)據(jù)；

image.png

/* ---------------- Fields -------------- */
  transient Node<K,V>[] table;
  transient int size; // put進(jìn)去多少數(shù)據(jù) ；size <= table.length
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

怎么根據(jù)hash值找到對(duì)應(yīng)的entry

將對(duì)象的key的哈希值與entry數(shù)組的長(zhǎng)度-1 進(jìn)行邏輯與&運(yùn)算，得到一個(gè)小于等于entry數(shù)組的長(zhǎng)度-1的數(shù)字
注意這里數(shù)組的長(zhǎng)度一定是一個(gè)2的整數(shù)次冪的數(shù)，在初始化時(shí)傳入一個(gè)非2的冪的數(shù)，jdk會(huì)轉(zhuǎn)化為大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)，以保證在進(jìn)行與運(yùn)算時(shí)，得到的數(shù)均勻分布

put插入數(shù)據(jù)的過(guò)程

首先獲取key的hashcode，找到對(duì)應(yīng)的entry，如果entry為空，則直接給entry賦值，如果entry不為空，那么遍歷鏈表，如果對(duì)應(yīng)的key已經(jīng)存在于鏈表上，則直接覆蓋，否則在鏈表最末端加上新的值；
在這之后會(huì)有個(gè)擴(kuò)容判斷，如果當(dāng)前size已經(jīng)超過(guò)了閾值（默認(rèn)entry數(shù)組的長(zhǎng)度的0.75），則進(jìn)行double擴(kuò)容；

擴(kuò)容的過(guò)程

新建一個(gè)容量是原來(lái)兩倍的entry數(shù)組，然后對(duì)原來(lái)的entry數(shù)組中的元素進(jìn)行遍歷，重新根據(jù)hash值計(jì)算它應(yīng)該在新數(shù)組的哪個(gè)位置上，然后進(jìn)行放置；
然后將原來(lái)數(shù)組的數(shù)據(jù)逐個(gè)設(shè)置為null，使引用失效；

get獲取數(shù)據(jù)的過(guò)程

根據(jù)key的hashcode找到對(duì)應(yīng)的entry，然后判斷entry鏈表的第一個(gè)節(jié)點(diǎn)的key是不是相同，否則循環(huán)遍歷整個(gè)鏈表直到找到為止！

為什么要用hash分組的方式

分組是為了利用數(shù)組的線性查找提高數(shù)據(jù)的查找效率（數(shù)組是連續(xù)的一塊內(nèi)存空間），根據(jù)key值的hascode可以快速定位到在哪個(gè)entry里，不然的話全部遍歷時(shí)間復(fù)雜度為O(n)

為什么entry里的數(shù)據(jù)要用鏈表的方式

鏈表的好處就是利用鏈表的尋址修改，增刪快

為什么hashmap線程不安全

1. put的時(shí)候，A線程已經(jīng)定位到了要插入的鏈表位置，這個(gè)時(shí)候B在同樣的位置先執(zhí)行了插入操作，但是A是不知道的，A繼續(xù)執(zhí)行插入就會(huì)覆蓋調(diào)B的數(shù)據(jù)；
2. 多線程resize時(shí)可能出現(xiàn)死循環(huán)，在鏈表從老的數(shù)組拷貝到新數(shù)組時(shí)，可能出現(xiàn)鏈表循環(huán)引用的問(wèn)題，導(dǎo)致死循環(huán)；
   jdk1.8修復(fù)了此問(wèn)題：用 head 和 tail 來(lái)保證鏈表的順序和之前一樣，這樣就不會(huì)產(chǎn)生循環(huán)引用
   引用

JDK 1.8對(duì)hashMap的改動(dòng)

鏈表引入紅黑樹，修復(fù)多線程resize死循環(huán)問(wèn)題
在給鏈表追加數(shù)據(jù)的時(shí)候，如果量表長(zhǎng)度超過(guò)閾值（8），則就把鏈表轉(zhuǎn)換為紅黑樹

4、ConcurrentHashMap原理：

對(duì)value 加上 volatile、讀取不加鎖、

1.7：分段鎖，segment 繼承自ReentrantLock，segment結(jié)構(gòu)和hashmap類似；獲取鎖會(huì)從自旋鎖升級(jí)為阻塞鎖

1.8：和1.8的hashmap基本一樣
不同點(diǎn)：數(shù)據(jù)結(jié)構(gòu)變化、ReentrantLock 改為了 synchronized、紅黑樹
put時(shí)，根據(jù)key定位到node，如果node為空，則cas自旋插入；否則synchronized在鏈表末尾插入，鏈表長(zhǎng)度超過(guò)8轉(zhuǎn)換為紅黑樹

5、HashSet和HashMap

HashSet其實(shí)就是HashMap實(shí)現(xiàn)的，它只是封裝了一個(gè) HashMap 對(duì)象來(lái)存儲(chǔ)所有的集合元素，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來(lái)保存，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT，它是一個(gè)靜態(tài)的 Object 對(duì)象。

6、LinkedHashMap 和 HashMap

1. LinkedHashMap extends HashMap
2. LinkedHashMap采用雙向鏈表+散列表的結(jié)構(gòu)來(lái)保存數(shù)據(jù)，保證節(jié)點(diǎn)的有序性（hashmap只是用鏈表來(lái)解決哈希沖突）；