1.HashMap和ConcurrentHashMap介紹
核心是一個Node數(shù)組,數(shù)據(jù)結(jié)構(gòu)與hashMap相似
使用CAS操作來實現(xiàn)無鎖的更新,提高了并發(fā)性。當更新節(jié)點時,它會使用CAS來替換節(jié)點的值或鏈接,如果CAS失敗,表明有其他線程也在進行修改,當前線程可以重試或鎖定節(jié)點
對于復(fù)雜的結(jié)構(gòu)修改操作 ConcurrentHashMap 使用synchronized關(guān)鍵字來鎖定特定的節(jié)點。
.CAS是什么
CAS是一種用于實現(xiàn)多線程同步的機制。它是一種無鎖的非阻塞算法的一部分,廣泛應(yīng)用于多線程編程中,用于實現(xiàn)高效的同步控制。
CAS的基本思想:
CAS操作包含三個參數(shù):內(nèi)存位置(V),預(yù)期原值(A)和新值(B)。CAS具體操作如下:
比較: 它首先檢查內(nèi)存位置V的當前值是否與預(yù)期原值A(chǔ)相等。
交換: 如果相等,那么處理器會自動將該位置值更新為新值B。
否則: 如果不相等,說明其他線程已經(jīng)修改了該位置的數(shù)據(jù),CAS操作失敗
hashMap插入的過程
1)計算key的哈希碼,使用哈希函數(shù)將哈希碼轉(zhuǎn)換為數(shù)組索引
2)上一步得到的索引,定位到內(nèi)部數(shù)組的特定位置
3)由于不同的鍵可能產(chǎn)生相同的索引
如果是鏈表,則遍歷鏈表,使用 equals() 方法比較鍵對象,直到找到匹配的鍵。
如果是紅黑樹,則在樹中進行搜索,直到找到匹配的鍵。
自定義類作為hashmap的key,那么這個key要滿足什么要求
1)正確實現(xiàn) hashCode()、equals()方法
2)如果兩個對象通過 equals() 方法比較是相等的,那么這兩個對象調(diào)用 hashCode() 方法必須產(chǎn)生相同的整數(shù)結(jié)果。如果兩個對象通過 equals() 方法比較是不相等的,理想情況下它們的 hashCode() 方法產(chǎn)生的整數(shù)也應(yīng)該不同
HashMap改用紅黑樹講講為什么**
鏈表可能會變得很長,這意味著查找效率會降低到O(n)。將鏈表轉(zhuǎn)換成紅黑樹,這樣即使在最壞的情況下,查找效率也能保持在O(log n)
紅黑樹
任何一條從根到葉子的路徑上各個節(jié)點的顏色進行約束,紅黑樹確保沒有一條路徑會比其他路徑長出兩倍,由此達到近似平衡的效果文章來源:http://www.zghlxwxcb.cn/news/detail-796267.html
2. ArrayList和LinkedList的底層原理和區(qū)別**
ArrayList
ArrayList 線程不安全,沒有synchronized
LinkedList
ArrayList和LinkedList的區(qū)別
ArrayList需要連續(xù)內(nèi)存空間
LinkedList不需要連續(xù)內(nèi)存空間文章來源地址http://www.zghlxwxcb.cn/news/detail-796267.html
到了這里,關(guān)于Java面試基礎(chǔ)|數(shù)據(jù)結(jié)構(gòu) -實時更新的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!