資訊專欄INFORMATION COLUMN
摘要：很多種方式，在這里就不討論每一種解決方式的利弊，我們只是對(duì)于中的作為研究。
在Java中，有一種而且我們使用很頻繁的數(shù)據(jù)結(jié)構(gòu)，叫做HashMap，其實(shí)準(zhǔn)確的來說，這是散列表的一種沖突解決的實(shí)現(xiàn)，那么什么是散列表呢？這個(gè)概念在網(wǎng)上可以找到很多專業(yè)的回答，這里我們就舉一個(gè)很簡單的例子來說明一下什么是散列表。
首先我們要明確的一點(diǎn)，就是散列表肯定是用來存取東西的，那么如果我們要把西瓜，蘋果，草莓這三種東西按照重量存到某個(gè)地方，方便我們后面再拿來使用，這個(gè)該如何操作呢？首先我們可以拿一個(gè)彈簧，然后使用這個(gè)彈簧將這些東西按照重量彈出去，因?yàn)橹亓康牟煌瑢?huì)落在不同的區(qū)域，這樣就將這些東西“保存”了起來。如果我們后面要使用這些東西的時(shí)候，只需要按照重量再去使用一次彈簧就可以了，這樣就能找到我們所需要找的。
這里我們?cè)倜鞔_幾個(gè)概念，這個(gè)例子中的幾種東西，就是我們要存放的數(shù)據(jù)，彈簧指的是hash算法，因?yàn)檫@些數(shù)據(jù)的存放是無序的，所以這些概念綜合起來看，稱這種形式為散列表。
還有一個(gè)問題，就是如果在這個(gè)散列表中有兩個(gè)數(shù)據(jù)通過hash算法落到了同一個(gè)區(qū)域，那么在這里就稱之為沖突，或者叫hash沖突，在散列表中，解決沖突的方式有線性探測(cè)法，平方探測(cè)法，鏈?zhǔn)降刂贩?/b>。。。很多種方式，在這里就不討論每一種解決方式的利弊，我們只是對(duì)于Java中的HashMap作為研究。
如果看過HashMap源碼的朋友就會(huì)知道，在Java中HashMap是基于鏈?zhǔn)降刂贩▉韺?shí)現(xiàn)的，當(dāng)然也有很多朋友可能不太喜歡看源碼，好的，那么我們就按照HashMap來動(dòng)手寫一個(gè)簡單的實(shí)現(xiàn)。
我們先定義一個(gè)節(jié)點(diǎn)類。
public class Entry {
private Integer key;
private String value;
private Entry next;
public Entry(Integer key, String value, Entry next){
this.key = key;
this.value = value;
this.next = next;
}
}
然后我們?cè)诙x一個(gè)CopyHashMap類。
public class CopyHashMap {
private final static int DEFAULT_CAPCITY = 11;
private Entry[] arrEntry;
public CopyHashMap(){
arrEntry = new Entry[DEFAULT_CAPCITY];
}
public CopyHashMap(int size){
arrEntry = new Entry[size];
}
private int hash(int key){
return key % DEFAULT_CAPCITY;
}
public String get(int key){
int h = hash(key);
Entry entry = arrEntry[h];
for (Entry e = entry; e != null; e = e.getNext()){
if (e.getKey().equals(key)){
return e.getValue();
}
}
return null;
}
public void put(int key, String value){
int h = hash(key);
Entry entry = arrEntry[h];
for (Entry e = entry; e != null; e = e.getNext()){
if (e.getKey().equals(key)){
e.setValue(value);
}
}
arrEntry[h] = new Entry(key, value, arrEntry[h]);
}
}
這里只是簡單的寫了一個(gè)get和put方法，代碼很簡單，看一看應(yīng)該都能明白，可以看到其底層實(shí)現(xiàn)還是依賴于一個(gè)數(shù)組，這里有一個(gè)hash的方法，這個(gè)就是我們剛開始例子中的彈簧，對(duì)于每一個(gè)key都要去計(jì)算對(duì)應(yīng)的hash值是多少，然后才能確定存放在數(shù)組中的哪個(gè)位置，所以能夠看出，散列表中的hash算法的設(shè)計(jì)是非常重要的。
這段代碼中還有一些東西沒有做，比如remove方法，還有rehash方法，如果你有興趣，那么可以動(dòng)手實(shí)現(xiàn)一下這兩個(gè)方法，rehash的過程在這里順便提一下，簡單的說就是如果存儲(chǔ)列表不夠用的情況下，hash表會(huì)擴(kuò)容，然后將里面的數(shù)據(jù)重新hash一次，當(dāng)然這個(gè)rehash會(huì)提前開始進(jìn)行的，所以這里我們可以觀察到一個(gè)現(xiàn)象就是如果散列表rehash一次，對(duì)程序的性能影響還是比較大的，對(duì)了，在JDK8中，HashMap也做了一些改進(jìn)，鏈?zhǔn)酱鎯?chǔ)的時(shí)候，在其長度達(dá)到某一個(gè)定值，后面的存儲(chǔ)方式會(huì)轉(zhuǎn)為紅黑樹的形式，有興趣的話可以看一下源碼。
HashMap在Java中的使用很頻繁，很多人應(yīng)該都懂其原理，可能也有很多人不太明白，希望這篇文章能讓大家初窺HashMap的門道，更深入的研究就只能大家自己探索了。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/76478.html
摘要：基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識(shí)點(diǎn)總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時(shí)間和時(shí)間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對(duì)象鎖和類鎖的區(qū)別，，優(yōu)缺點(diǎn)及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
摘要：基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識(shí)點(diǎn)總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時(shí)間和時(shí)間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對(duì)象鎖和類鎖的區(qū)別，，優(yōu)缺點(diǎn)及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
摘要：基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識(shí)點(diǎn)總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時(shí)間和時(shí)間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對(duì)象鎖和類鎖的區(qū)別，，優(yōu)缺點(diǎn)及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
摘要：哪吒社區(qū)技能樹打卡打卡貼函數(shù)式接口簡介領(lǐng)域優(yōu)質(zhì)創(chuàng)作者哪吒公眾號(hào)作者架構(gòu)師奮斗者掃描主頁左側(cè)二維碼，加入群聊，一起學(xué)習(xí)一起進(jìn)步歡迎點(diǎn)贊收藏留言前情提要無意間聽到領(lǐng)導(dǎo)們的談話，現(xiàn)在公司的現(xiàn)狀是碼農(nóng)太多，但能獨(dú)立帶隊(duì)的人太少，簡而言之，不缺干 ? 哪吒社區(qū)Java技能樹打卡?【打卡貼 day2...
閱讀 829·2021-11-22 11:59
閱讀 3243·2021-11-17 09:33
閱讀 2312·2021-09-29 09:34
閱讀 1944·2021-09-22 15:25
閱讀 1960·2019-08-30 15:55
閱讀 1324·2019-08-30 15:55
閱讀 536·2019-08-30 15:53
閱讀 3351·2019-08-29 13:55
