網(wǎng)站建設(shè)都需要什么技術(shù)人員網(wǎng)站優(yōu)化網(wǎng)絡(luò)推廣seo
1.Map的存儲(chǔ)特點(diǎn)
在Map這個(gè)結(jié)構(gòu)中，數(shù)據(jù)是以鍵值對(duì)（key-value）的形式進(jìn)行存儲(chǔ)的，每一個(gè)存儲(chǔ)進(jìn)map的數(shù)據(jù)都是一一對(duì)應(yīng)的。
創(chuàng)建一個(gè)Map結(jié)構(gòu)可以使用new HashMap()以及new TreeMap()兩種方式，兩者之間的區(qū)別是：TreeMap是支持 排序的。
2.HashMap的底層存儲(chǔ)方式
?
總結(jié):
1. 用hashMap存儲(chǔ)數(shù)據(jù)(key,value)的時(shí)候使用put方法
2. put方法會(huì)調(diào)用putVal方法,把hash(hey)和當(dāng)前的key，value作為參數(shù)傳進(jìn)來(lái)
3. 判斷數(shù)組是否為空，即判斷是否是第一次添加數(shù)據(jù),如果是的話，會(huì)先調(diào)用resize方法擴(kuò)容
4. 之后,根據(jù)當(dāng)前key的hash值找到它在數(shù)組中的下標(biāo) (怎么算的? index = (n - 1) & hash)，判斷當(dāng)前下標(biāo)位置是 否已經(jīng)存在元素
5. 如果不存在，直接把key、value包裝成Node節(jié)點(diǎn)作為鏈表頭存入數(shù)組
6. 如果存在，分為三種情況
1. ）比較一下已有數(shù)據(jù)和存入數(shù)據(jù) 如果hash值等于傳過(guò)來(lái)的hash，并且他們的key值也相等 最后會(huì)把 value的值覆蓋處理
2. ）上一步不相等，就判斷一下當(dāng)前是不是紅黑樹(shù)結(jié)構(gòu)，是則調(diào)用putTreeVal()把它加入到紅黑樹(shù)
3. ）既不相等，也不是紅黑樹(shù)結(jié)構(gòu)，說(shuō)明是普通鏈表結(jié)構(gòu)，遍歷這個(gè)鏈表，將數(shù)據(jù)存到鏈表尾部
1. 在遍歷過(guò)程中，如果是最后一個(gè)節(jié)點(diǎn)，則插入新節(jié)點(diǎn) newNode(hash, key, value, null)
2. 如果鏈表長(zhǎng)度超過(guò)了8，則轉(zhuǎn)化為紅黑樹(shù) treeifyBin(tab, hash)3. 如果遍歷的時(shí)候遇到了相同的key 把value的值覆蓋處理
7. 如果當(dāng)前數(shù)組中的元素個(gè)數(shù)超過(guò)閾值，則擴(kuò)容 resize();
8. putVal（）方法 沒(méi)修改value就返回NULL 修改了就返回舊值（之前的value）
3.什么是hash碰撞
Hash Collision 就是我們說(shuō)的 Hash 碰撞或者 Hash 沖突。
這個(gè)其實(shí)也非常好理解，就是 2 個(gè)輸入不同的數(shù)據(jù)，經(jīng)過(guò) Hash 算法后，得到的 Hash 值是一樣的。
在HashMap的查詢和添加過(guò)程中，繞不過(guò)去的是計(jì)算元素在數(shù)組的位置index，key的HashCode作為這個(gè)計(jì)算的 基礎(chǔ)。計(jì)算后的Hash值存在相同的情況，hash與長(zhǎng)度取余的結(jié)果也有相同的情況，這個(gè)時(shí)候運(yùn)算結(jié)果相同的兩個(gè) 對(duì)象就需要存儲(chǔ)到同一個(gè)鏈表中，這就是HashMap中的Hash碰撞。
4.如何解決hash碰撞
1.開(kāi)放地址方法
1）線性探測(cè)
按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上往后加一個(gè)單位，直至不發(fā)生哈希沖突。 就是在
此空間不足時(shí)，直接放入此空間的后一個(gè)空的空間
2）再平方探測(cè)
按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上先加1的平方個(gè)單位，若仍然存在則減1的平方個(gè)
單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。 要注意平方不能超過(guò)容量的值 Size=16的時(shí)候，找備
選的單元只能取i=1,2,3，也就是距離沖突單元1,4,9個(gè)單位的位置了。
3）偽隨機(jī)探測(cè)
按順序決定值時(shí)，如果某數(shù)據(jù)已經(jīng)存在，通過(guò)隨機(jī)函數(shù)隨機(jī)生成一個(gè)數(shù)，在原來(lái)值的基礎(chǔ)上加上隨機(jī)數(shù)，直至不發(fā)
生哈希沖突。
2.鏈?zhǔn)降刂贩?#xff08;HashMap的哈希沖突解決方法）
對(duì)于相同的值，使用鏈表進(jìn)行連接。使用數(shù)組存儲(chǔ)每一個(gè)鏈表。 就是hashmap的底層原理 ：數(shù)組+鏈表 就是沒(méi)有
紅黑樹(shù)
補(bǔ)充：在JDK1.8中HashMap通過(guò)鏈?zhǔn)綄ぶ贩ㄒ云浼t黑樹(shù)來(lái)解決哈希沖突的，其中紅黑樹(shù)是為了優(yōu)化哈希表的鏈表
過(guò)長(zhǎng) 導(dǎo)致遍歷時(shí)間復(fù)雜度增加的問(wèn)題。當(dāng)鏈表長(zhǎng)度大于8并且哈希表的容量大于64,再向鏈表中添加元素,會(huì)轉(zhuǎn)化為
紅黑樹(shù)。優(yōu)點(diǎn)：
1）拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較
2）
由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況； （
3）開(kāi)放定址法為
減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉 鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間； （
4）在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。
只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。 缺點(diǎn)：
1） 指針占用較大空間時(shí)，會(huì)造成空間浪費(fèi)，若空間用于增大散列表規(guī)模進(jìn)而提高開(kāi)放地址法的效率。
3.建立公共溢出區(qū)
建立公共溢出區(qū)存儲(chǔ)所有哈希沖突的數(shù)據(jù)
4.再哈希法
對(duì)于沖突的哈希值再次進(jìn)行哈希處理，直至沒(méi)有哈希沖突。
5.如何解決并發(fā)
HashMap的線程不安全主要體現(xiàn)在下面兩個(gè)方面：
1.在JDK1.7中，當(dāng)并發(fā)執(zhí)行擴(kuò)容操作時(shí)會(huì)造成環(huán)形鏈和數(shù)據(jù)丟失的情況。 2.在JDK1.8中，在并發(fā)執(zhí)行put操作時(shí)會(huì)
發(fā)生數(shù)據(jù)覆蓋的情況。 1、if((p = tab[i =(n -1)& hash])==null)// 1、此處線程不安全——用來(lái)判定索引位置是否
hash碰撞，比如兩個(gè)線程A、B都在進(jìn)行put操作，并且hash函數(shù)計(jì)算出的插入下標(biāo)是相同的，當(dāng)線程A執(zhí)行完第六
行代碼后由于時(shí)間片耗盡導(dǎo)致被掛起，而線程B得到時(shí)間片后在該下標(biāo)處插入了元素，完成了正常的插入，然后線
程A獲得時(shí)間片，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所有此時(shí)不會(huì)再進(jìn)行判斷，而是直接進(jìn)行插入，這就導(dǎo)致 了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。
2、if (++size > threshold)中的++size：同樣還是線程A、B，這兩個(gè)線程同時(shí)進(jìn)行put操作時(shí)，假設(shè)當(dāng)前HashMap
的zise大小為10，當(dāng)線程A執(zhí)行到此行代碼時(shí)，從主內(nèi)存中獲得size的值為10后準(zhǔn)備進(jìn)行+1操作，但是由于時(shí)間片
耗盡只好讓出CPU，線程B快樂(lè)的拿到CPU還是從主內(nèi)存中拿到size的值10進(jìn)行+1操作，完成了put操作并將
size=11寫回主內(nèi)存，然后線程A再次拿到CPU并繼續(xù)執(zhí)行(此時(shí)size的值仍為10)，當(dāng)執(zhí)行完put操作后，還是將
size=11寫回內(nèi)存，此時(shí)線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說(shuō)還是由于數(shù)據(jù)覆蓋又導(dǎo)
致了線程不安全。
解決方法： 1.Hashtable
HashTable為了實(shí)現(xiàn)多線程安全，在幾乎所有的方法上都加上了synchronized鎖（鎖的是類的實(shí)例,也就是整個(gè)
map結(jié)構(gòu)），當(dāng)一個(gè)線程訪 問(wèn) Hashtable 的同步方法時(shí)，其他線程如果也要訪問(wèn)同步方法，會(huì)被阻塞住。
2.Collections.synchronizedMap(一般不用) 缺點(diǎn):從鎖的角度來(lái)看，基本上是鎖住了盡可能大的代碼塊.性能會(huì)比較
差 3.ConcurrentHashMap（常用） JDK 1.7 中，采用分段鎖的機(jī)制，實(shí)現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的 存儲(chǔ)結(jié)構(gòu)，包括兩個(gè)核心靜態(tài)內(nèi)部類 Segment 和 HashEntry。 ①、Segment 繼承 ReentrantLock（重入鎖） 用
來(lái)充當(dāng)鎖的角色，每個(gè) Segment 對(duì)象守護(hù)每個(gè)散列映射表的若干個(gè)桶； ②、HashEntry 用來(lái)封裝映射表的鍵-值 對(duì)； ③、每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來(lái)的鏈表 分段鎖：Segment數(shù)組中，一個(gè)Segment對(duì)象就是一 把鎖,對(duì)應(yīng)一個(gè)HashEntry數(shù)組,該數(shù)組中的數(shù)據(jù)同步依賴于同一把鎖,不同HashEntry數(shù)組的讀寫互不干擾
JDK 1.8中拋棄了原有的 Segment 分段鎖，來(lái)保證采用Node + CAS + Synchronized來(lái)保證并發(fā)安全性。取消類 Segment，直接用table 數(shù)組存儲(chǔ)鍵值對(duì)；當(dāng) Node對(duì)象組成的鏈表長(zhǎng)度超過(guò)TREEIFY_THRESHOLD 時(shí)，鏈表轉(zhuǎn)換
為紅黑樹(shù)，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹(shù)。 CAS性能很高，但synchronized之前一直都是重量級(jí)的 鎖，jdk1.8 引入了synchronized，采用鎖升級(jí)的方式。