21.ArrayList Vector LinkedList的區(qū)別?
這三者都是實現(xiàn)集合框架中的List,也就是所謂的有序集合,因此具體功能也比較類似,比如都提供按照位置進(jìn)行定位 添加或者刪除的操作,都提供迭代器以遍歷其內(nèi)容等埃元。但因為具體的設(shè)計區(qū)別 在行為 性能 線程安全等方面,表現(xiàn)又有很大不同将硝。
Vector是Java早期提供的線程安全的動態(tài)數(shù)組,如果不需要線程安全,并不建議選擇,畢竟同步是有額外開銷的豺鼻。Vector內(nèi)部是使用對象數(shù)組來保存數(shù)據(jù),可以根據(jù)需要自動的增加容量,當(dāng)數(shù)組以滿時,會創(chuàng)建新的數(shù)組,并拷貝原有數(shù)組數(shù)據(jù)锹安。
ArrayList是應(yīng)用更加廣泛的動態(tài)數(shù)組實現(xiàn),它本身不是線程安全的,所以性能要好很多。與Vector近似,ArrayList也是可以根據(jù)需要調(diào)整容量,不過兩者的調(diào)整邏輯有所區(qū)別,Vector在擴容時會提高1倍,而ArrayList則是增加50%赴魁。
LinkedList顧明思議是Java提供的雙向鏈表,所以它不需要像上面兩種那樣調(diào)整容量,它也不是線程安全的。
Vector和ArrayList作為動態(tài)數(shù)組,其內(nèi)部元素以數(shù)組形式順序存儲的,所以非常適合隨即訪問的場合。除了尾部出入元素和刪除元素,往往性能會相對較差,比如我們在中間位置插入一個元素,需要移動后續(xù)所有元素烂叔。而LinkedList進(jìn)行節(jié)點插入 刪除卻要高效得很多,但是隨即訪問性能則要比動態(tài)數(shù)組慢。
22.如何保證集合是線程安全的? ConcurrentHashMap 如何實現(xiàn)高效的線程安全?
Java提供了不同層面的線程安全支持固歪。在傳統(tǒng)集合框架內(nèi)部,除了Hashtable Vector等同步容器,還提供了同步包裝器,我們可以調(diào)用Collections工具類提供的包裝方法,來獲取一個同步的包裝容器(例如Collections.synchronizedMap),但是它們都是利用非常粗粒度的同步方式,在高并發(fā)情況下,性能比較底下,另外,更加普遍的選擇是利用并發(fā)包提供的線程安全容器類长已。具體保證線程安全的方式,包括有從簡單的synchronize方式,到基于更加精細(xì)化的,比如基于分離式鎖實現(xiàn)的ConcurrentHashMap等并發(fā)實現(xiàn)等。具體選擇要看開發(fā)的場景需求,總體來說,并發(fā)包內(nèi)提供的容器通用場景,遠(yuǎn)優(yōu)于早期的簡單同步實現(xiàn)昼牛。
23.為什么需要ConcurrentHashMap?
Hashtable本身比較低效,因為它的實現(xiàn)基本就是put get size等各種方法加上"synchronized"术瓮。簡單來說,這就導(dǎo)致了所有并發(fā)操作都要競爭同一把鎖,一個線程在進(jìn)行同步操作時,其他線程只能等待,大大降低了并發(fā)操作的效率。前面說過HashMap不是線程安全的,那么能不能利用Collections提供的同步包裝器來解決問題?實際上同步器只是利用輸入Map構(gòu)造了另一個同步版本,所有操作不再聲明為synchronized方法,但是還是利用了"this"作為互斥的mutex,沒有真正意義上的改進(jìn)贰健。
所以,Hashtable或者同步包裝版本,都只是適合在非高度并發(fā)的場景下胞四。
24.HashMap中hash函數(shù)怎么是是實現(xiàn)的?
我們可以看到在hashmap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置伶椿。
如何計算這個位置就是hash算法辜伟？
前面說過hashmap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當(dāng)然希望這個hashmap里面的元素位置盡量的分布均勻些脊另，盡量使得每個位置上的元素數(shù)量只有一個,這樣當(dāng)我們用hash算法求得這個位置的時候导狡，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表偎痛。
所以我們首先想到的就是把hashcode對數(shù)組長度取模運算旱捧，這樣一來，元素的分布相對來說是比較均勻的踩麦。
但是枚赡，“模”運算的消耗還是比較大的谓谦，能不能找一種更快速贫橙，消耗更小的方式，我們來看看JDK1.8的源碼是怎么做的（被樓主修飾了一下）
簡單來說就是
1反粥、高16bt不變卢肃，低16bit和高16bit做了一個異或(得到的HASHCODE轉(zhuǎn)化為32位的二進(jìn)制，前16位和后16位低16bit和高16bit做了一個異或)
2才顿、(n·1)&hash=->得到下標(biāo)
25.拉鏈法導(dǎo)致的鏈表過深問題為什么不用二叉查找樹代替莫湘，而選擇紅黑樹？為什么不一直使用紅黑樹娜膘？
之所以選擇紅黑樹是為了解決二叉查找樹的缺陷逊脯，二叉查找樹在特殊情況下會變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題）竣贪，遍歷查找會非常慢军洼。
而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋巩螃，右旋、變色這些操作來保持平衡匕争，引入紅黑樹就是為了查找數(shù)據(jù)快避乏，解決鏈表查詢深度的問題。我們知道紅黑樹屬于平衡二叉樹甘桑，但是為了保持“平衡”是需要付出代價的拍皮，但是該代價所損耗的資源要比遍歷線性鏈表要少
所以當(dāng)長度大于8的時候，會使用紅黑樹跑杭，如果鏈表長度很短的話铆帽，根本不需要引入紅黑樹，引入反而會慢德谅。
26.說說你對紅黑樹的見解爹橱？
1、每個節(jié)點非紅即黑
2窄做、根節(jié)點總是黑色的
3愧驱、如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）
4椭盏、每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）
5组砚、從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）
27.hashMap解決hash 碰撞還有那些辦法掏颊？
使用開放定址法糟红。
當(dāng)沖突發(fā)生時，使用某種探查技術(shù)在散列表中形成一個探查(測)序列蚯舱。沿此序列逐個單元地查找改化，直到找到給定的地址掩蛤。
按照形成探查序列的方法不同枉昏，可將開放定址法區(qū)分為線性探查法、二次探查法揍鸟、雙重散列法等兄裂。
下面給一個線性探查法的例子
問題：已知一組關(guān)鍵字為(26，36阳藻，41晰奖，38，44腥泥，15匾南，68，12蛔外，06蛆楞，51)溯乒，用除余法構(gòu)造散列函數(shù)，用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的散列表豹爹。
解答：為了減少沖突裆悄，通常令裝填因子α由除余法因子是13的散列函數(shù)計算出的上述關(guān)鍵字序列的散列地址為(0，10臂聋，2光稼，12，5孩等，2艾君，3，12肄方，6腻贰，12)。前5個關(guān)鍵字插入時扒秸，其相應(yīng)的地址均為開放地址播演，故將它們直接插入T[0]，T[10)伴奥，T[2]写烤，T[12]和T[5]中。當(dāng)插入第6個關(guān)鍵字15時拾徙，其散列地址2(即h(15)=15％13=2)已被關(guān)鍵字41(15和41互為同義詞)占用洲炊。故探查h1=(2+1)％13=3，此地址開放尼啡，所以將15放入T[3]中暂衡。當(dāng)插入第7個關(guān)鍵字68時，其散列地址3已被非同義詞15先占用崖瞭，故將其插入到T[4]中狂巢。當(dāng)插入第8個關(guān)鍵字12時，散列地址12已被同義詞38占用书聚，故探查hl=(12+1)％13=0唧领，而T[0]亦被26占用，再探查h2=(12+2)％13=1雌续，此地址開放斩个，可將12插入其中。類似地驯杜，第9個關(guān)鍵字06直接插入T[6]中受啥；而最后一個關(guān)鍵字51插人時，因探查的地址12，0滚局，1叁温，…，6均非空核畴，故51插入T[7]中膝但。
28.如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦谤草？
默認(rèn)的負(fù)載因子大小為0.75
也就是說跟束，當(dāng)一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣丑孩，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組來重新調(diào)整map的大小冀宴，并將原來的對象放入新的bucket數(shù)組中。
這個過程叫作rehashing温学，因為它調(diào)用hash方法找到新的bucket位置略贮。這個值只可能在兩個地方，一個是原下標(biāo)的位置仗岖，另一種是在下標(biāo)為<原下標(biāo)+原容量>的位置
29.重新調(diào)整HashMap大小存在什么問題嗎逃延？
當(dāng)重新調(diào)整HashMap大小的時候，確實存在條件競爭轧拄，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了揽祥，它們會同時試著調(diào)整大小。
在調(diào)整大小的過程中檩电，存儲在鏈表中的元素的次序會反過來拄丰，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部俐末，而是放在頭部
這是為了避免尾部遍歷(tail traversing)料按。如果條件競爭發(fā)生了，那么就死循環(huán)了卓箫。(多線程的環(huán)境下不使用HashMap）
30.關(guān)于ConcurrentHashMap工作機制（拓展部分）
在早期的ConcurrentHashMap,其實現(xiàn)是基于分離鎖,也就是將內(nèi)部進(jìn)行分段,里面則是HashEntry的數(shù)據(jù)载矿。和HashMap類似,哈希相同的條目也是以鏈表形式存放。(簡單點來說,就是在ConcurrentHashMap中,把Map分成了N個Segment,put和get的時候,都是現(xiàn)根據(jù)key.hashCode()算出放到哪個Segment中)
在構(gòu)造的時候,Segment的數(shù)量由所謂的concurrentcyLevel來決定,默認(rèn)是16,也可以在相應(yīng)構(gòu)造函數(shù)直接指定丽柿。注意,Java需要它是2的冪數(shù)值,如果輸入是類似15這種非冪值,會自動調(diào)整到16之類2的冪數(shù)值恢准。
看如下的測試代碼:
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapTest {
private static ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<Integer, Integer>();
public static void main(String[] args) {
new Thread("Thread1"){
@Override
public void run() {
map.put(3, 33);
}
};
new Thread("Thread2"){
@Override
public void run() {
map.put(4, 44);
}
};
new Thread("Thread3"){
@Override
public void run() {
map.put(7, 77);
}
};
System.out.println(map);
}
}
我們創(chuàng)建了3個線程分別向ConcurrentHashMap中添加數(shù)據(jù),根據(jù)ConcurrentHashMap.segmentFor的算法，當(dāng)我們向ConcurrentHashMap中put key為3或者4的數(shù)據(jù)時,此時他們對應(yīng)的Segment都是segments[1]甫题，而put key為7對應(yīng)的數(shù)據(jù)時,此時對應(yīng)的Segment是segments[12]。那么當(dāng)線程1在put(3,33)時,線程2也想put(4,44)時,因為線程1和線程2操作的都是同一個Segment,線程1會首先獲取到鎖,可以進(jìn)入,線程2則會阻塞在鎖上涂召。線程3在put數(shù)據(jù)時,他對應(yīng)的segments是12,他不會上鎖坠非。 以上就是ConcurrentHashMap的工作機制，通過把整個Map分為N個Segment（類似HashTable）果正，可以提供相同的線程安全炎码，但是效率提升N倍盟迟，默認(rèn)提升16倍。
