<------------linkedList和arrayList是線程不安全的

1.linkedlist:

LinkedList是List接口的（雙向）鏈表實現(xiàn)。

2.arrayList:

arrayList是List接口可變數(shù)組的實現(xiàn)

<------------java的散列結(jié)構(gòu)：

hashmap,hashtable,hashset,concurrentHashmap

<-----------hashmap,hashtable,concurrentHashmap區(qū)別

*HashTable：（數(shù)組+列表）key,value均不能為null

線程安全? ?操作數(shù)據(jù)時用synchronized鎖整個hashtable

初始容量size=11? ? ?擴(kuò)容規(guī)則? newsize = oldsize*2+1

index = (hash & 0x7FFFFFFF) % tab.length

（為了在hash為負(fù)值的情況下，去掉起符號位，所以和0x7FFFFFFF進(jìn)行&操作

0x7FFFFFFF 二進(jìn)制 0111 1111 1111 1111 1111 1111 1111 1111

負(fù)數(shù)與其進(jìn)行&操作將產(chǎn)生一個正整數(shù)）

*HashMap:(數(shù)組+列表 +紅黑樹)? key和value都可以為null

線程不安全的?

初始容量size=16? 擴(kuò)容? newsize =? oldsize*2?

當(dāng)加載因子到達(dá)75%時觸發(fā)擴(kuò)容? 擴(kuò)容針對整個Map? 擴(kuò)容時會將原來數(shù)組的元素重新取hash 重新放置

插入元素后才判斷該不該擴(kuò)容，有可能無效擴(kuò)容（插入后如果擴(kuò)容，如果沒有再次插入，就會產(chǎn)生無效擴(kuò)容）

列表的長度size>8時 存儲結(jié)構(gòu)變成了紅黑樹

計算index方法：index = hash & (tab.length – 1)

樹的長度小于6時，存儲結(jié)構(gòu)轉(zhuǎn)為散列結(jié)構(gòu)

*ConcurrentHashMap（分段數(shù)組+列表）線程安全

1.7（分段鎖思想）

把整個Map分為N個Segment，可以提供相同的線程安全? 效率提升N倍 默認(rèn)提升16倍

數(shù)組（Segment） + 數(shù)組（HashEntry） + 鏈表（HashEntry節(jié)點）

底層一個Segments數(shù)組，存儲一個Segments對象，一個Segments中儲存一個Entry數(shù)組，存儲的每個Entry對象又是一個鏈表頭結(jié)點。

1.8??

Node數(shù)組+鏈表 / 紅黑樹： 類似hashMap<jdk1.8>

Node數(shù)組使用來存放樹或者鏈表的頭結(jié)點，當(dāng)一個鏈表中的數(shù)量到達(dá)一個數(shù)目時，會使查詢速率降低，所以到達(dá)一定閾值時，會將一個鏈表轉(zhuǎn)換為一個紅黑二叉樹，通告查詢的速率。

（讀操作是不加鎖的 因為 HashEntry的value變量是volatile的 也能保證讀到最新的值）