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