1.前言
以前看hashmap的原理看了很多次，過(guò)了很久都忘記了。真心發(fā)現(xiàn)以前的看書(shū)方法不對(duì)款筑。感覺(jué)學(xué)習(xí)還是要靠背書(shū)智蝠。這節(jié) 好好的踏實(shí)的把散列這屆記錄下。
2.正題
散列函數(shù)：
將關(guān)鍵字(key) 映射成0--tablesize-1 這個(gè)范圍中的某一個(gè)數(shù)奈梳，然后放到適當(dāng)?shù)膯卧需就濉＿@個(gè)映射就叫做“散列函數(shù)”。
沖突: 倆個(gè)或者多個(gè)關(guān)鍵字散列到同一個(gè)單元的時(shí)候攘须。就會(huì)產(chǎn)生沖突漆撞。
裝填因子:散列表的元素個(gè)數(shù) 比上 tablesize 得到的值，為裝填因子于宙。
通常對(duì)于key為String的 關(guān)鍵字來(lái)說(shuō)浮驳。一種方法就是將String 的每個(gè)字符，轉(zhuǎn)換成Ascll碼捞魁。然后累加至会。之后在%tablesize。(tablesize 不能為素?cái)?shù))谱俭。
還有一種散列函數(shù)沒(méi)搞明白奉件，就不記錄了。昆著。
介紹完了散列函數(shù)瓶蚂。那么就來(lái)寫(xiě)下 如何解決沖突問(wèn)題：
1.分離鏈接法
在沖突的地方，加入一個(gè)單向鏈表宣吱。如何待插入的數(shù)據(jù)是一個(gè)新數(shù)據(jù)的時(shí)候窃这，那么它將被插入鏈表的前端。不僅因?yàn)榉矫嬲骱颉８且驗(yàn)樽钚虏迦氲臄?shù)據(jù)最有可能被用到杭攻。
當(dāng)進(jìn)行插入的時(shí)候。發(fā)現(xiàn)鏈表中有之前的一摸一樣的key疤坝。那么就會(huì)替換掉oldValue：
兆解。
問(wèn)題1：hashmap為什么是無(wú)序的？
因?yàn)樗峭ㄟ^(guò)散列函數(shù)跑揉，映射得到數(shù)組的下標(biāo)的锅睛。所以是無(wú)序的。
問(wèn)題2：hashmap在多線程的情況下历谍，是不安全的
hashmap 的源碼是沒(méi)有假如任何的鎖機(jī)制现拒。多線程的情況下。假設(shè)新插入的元素都是無(wú)重復(fù)的望侈。那么在多線程的情況下印蔬，最后一個(gè)線程插入的數(shù)據(jù)，會(huì)覆蓋之前插入的數(shù)據(jù)脱衙。所以鏈表的第一個(gè)數(shù)組侥猬，是最后一個(gè)線程的數(shù)例驹。
缺點(diǎn)：由于給新單元分配地址需要時(shí)間，導(dǎo)致算法速度有些慢退唠。
2.線程探測(cè)法
探測(cè)性散列表的table 要大于 分離鏈接法鹃锈。一般來(lái)說(shuō) 探測(cè)性散列表的裝填因子<0.5。
線性探測(cè)法：以增量序列1瞧预，2屎债，......，（TableSize－1）循環(huán)試探下一個(gè)存儲(chǔ)地址
一次聚集現(xiàn)象:如上圖的表插入30 之后松蒜。明顯右邊的數(shù)據(jù)要密集些。左邊的數(shù)據(jù)要稀疏一點(diǎn)已旧。這樣的現(xiàn)象就叫做 聚集現(xiàn)象秸苗。
缺點(diǎn): 當(dāng)表很大的時(shí)候，出現(xiàn)聚集情況运褪，會(huì)導(dǎo)致新插入的數(shù)據(jù)要和每個(gè)單元進(jìn)行比較惊楼。插入不成功的情況大大增多。
3.平方探測(cè)法
針對(duì)線性探測(cè)法的缺點(diǎn)秸讹，偉大的算法工程師檀咙，又想出了 平方探測(cè)法，來(lái)解決線性探測(cè)法的聚集現(xiàn)象璃诀。
缺點(diǎn)：產(chǎn)生二次聚集弧可。
3.LinkHashMap
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數(shù)組中保存的元素Entry劣欢，該Entry除了保存當(dāng)前對(duì)象的引用外棕诵，還保存了其上一個(gè)元素before和下一個(gè)元素after的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表凿将。參考http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
LinkHashMap 鏈表部分 采用了雙向鏈表校套。保證了插入順序和訪問(wèn)順序。
插入順序
訪問(wèn)順序
