基于Java快速實現(xiàn)一個簡單版的HashMap詳解
更新時間：2023年02月08日 08:32:35 作者：帝莘
這篇文章主要為大家詳細介紹了如何利用Java簡單實現(xiàn)一個底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組?+?鏈表的HashMap,不考慮鏈表長度超過8個時變?yōu)榧t黑樹的情況，需要的可以參考一下
簡單實現(xiàn)一個底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組 + 鏈表的HashMap,不考慮鏈表長度超過8個時變?yōu)榧t黑樹的情況。
1.示例圖
2.分析需求
put數(shù)據(jù)時：
- key值hash后的索引處沒有元素，需要創(chuàng)建鏈表頭節(jié)點，放到該位置的數(shù)組空間里。
- key值hash后的索引處有元素，說明產(chǎn)生Hash碰撞，需要在鏈表中結(jié)尾處掛載節(jié)點，如果在遍歷鏈表的過程中，發(fā)現(xiàn)了同key的數(shù)據(jù)，則執(zhí)行覆蓋即可，不再繼續(xù)往下遍歷去掛載新節(jié)點。
- 假設數(shù)組使用的空間超過了總長度的75%，那么對數(shù)組進行擴容。先創(chuàng)建新數(shù)組，把舊數(shù)據(jù)寫到新數(shù)組中(此時需要重新根據(jù)key計算Hash，因為數(shù)據(jù)長度變化了，影響計算結(jié)果了)，在用新數(shù)據(jù)替換掉原來的舊數(shù)組。
get數(shù)據(jù)時：
- key值hash后的索引下標處的元素為空的話，則不存在數(shù)據(jù)。
- key值hash后的索引下標處存在鏈表的話，需要遍歷鏈表，找到key相對應的value值。
3.代碼實現(xiàn)
Node類實現(xiàn)
package com.zaevn.hashmap;
/**
* @author: zae
* @date: 2023/1/30
* @time: 11:25
*/
public class Node {
String key;
String value;
Node next;
public Node(String key, String value, Node nextNode) {
this.key = key;
this.value = value;
this.next = nextNode;
}
}LinkNode類實現(xiàn)
package com.zaevn.hashmap;
/**
* @author: zae
* @date: 2023/1/30
* @time: 11:27
*/
public class ListNode {
// 頭節(jié)點
Node head;
/**
* 添加數(shù)據(jù)，掛載鏈表的節(jié)點
* @param key
* @param value
*/
public void addNode(String key,String value){
// 如果頭節(jié)點是空,則結(jié)束
if(head == null ){return;}
// 如果頭節(jié)點不為空，則往下掛載節(jié)點
Node node = new Node(key,value,null);
Node temp = head;
while(true){
// 遇到相同的key,覆蓋數(shù)據(jù)
if(key.equals(temp.key)){
temp.value = value;
return;
}
if(temp.next == null){
break;
}
temp = temp.next;
}
// 循環(huán)結(jié)束后則掛上數(shù)據(jù)
temp.next = node;
}
/**
* 獲取數(shù)據(jù)
* @param key
* @return
*/
public String getNode(String key){
if(head == null ){return null;}
Node temp = head;
while(true){
if(key.equals(temp.key)){
return temp.value;
}
if(temp.next == null){
break;
}
temp = temp.next;
}
return null;
}
}
MyHashMap類實現(xiàn)
package com.zaevn.hashmap;
/**
* @author: zae
* @date: 2023/1/30
* @time: 11:27
*/
public class MyHashMap {
// 數(shù)組初始化:2的n次方
ListNode[] map = new ListNode[8];
// ListNode的個數(shù)
int size;
// 由于擴容時是先創(chuàng)建一個新數(shù)組，因此先聲明出來
ListNode[] mapNew;
int sizeNew;
/**
* put方法
* @param key
* @param value
*/
public void put(String key,String value){
if(size>map.length * 0.75){
System.out.println("開始進行擴容，當前size="+size+",數(shù)組長度為："+map.length);
doExtendMap();
System.out.println("擴容結(jié)束，當前size="+size+",數(shù)組長度為："+map.length);
}
// 1.對key進行hash算法然后取模
int index = Math.abs(key.hashCode())%map.length;
ListNode listNode = map[index];
// 如果索引位置的元素為空，則新加一個元素(創(chuàng)建頭節(jié)點)
if(listNode == null){
ListNode listNodeNew = new ListNode();
Node node = new Node(key,value,null);
listNodeNew.head = node;
map[index] = listNodeNew;
size ++;
}else{
// 如果索引位置的元素不為空，則往鏈表中掛載數(shù)據(jù)
listNode.addNode(key,value);
}
}
public String get(String key){
// 1.對key進行hash算法然后取模
int index = Math.abs(key.hashCode())%map.length;
if(map[index] == null){
return null;
}else{
return map[index].getNode(key);
}
}
/**
* 達到閾值后開始進行擴容
*/
public void doExtendMap(){
sizeNew = 0;
// 1.先創(chuàng)建一個新的數(shù)組，長度為原來的二倍
mapNew = new ListNode[map.length * 2];
// 2.將舊數(shù)據(jù)映射到新的數(shù)組上(因為數(shù)組長度變化，因此hash規(guī)則變化，所有的值需要重新計算hash值)
for(int i = 0;i<map.length;i++){
ListNode listNode = map[i];
if(listNode == null){
continue;
}
Node temp = listNode.head;
while (true){
doPutData(mapNew,temp.key,temp.value);
if(temp.next == null){
break;
}
temp = temp.next;
}
}
// 3.將新的數(shù)組替換舊的數(shù)組
map = mapNew;
this.size = sizeNew;
}
private void doPutData(ListNode[] mapParam,String key,String value){
int index = Math.abs(key.hashCode())%mapParam.length;
ListNode listNode = mapParam[index];
if(listNode == null){
ListNode listNodeNew = new ListNode();
Node node = new Node(key,value,null);
listNodeNew.head = node;
mapParam[index] = listNodeNew;
sizeNew ++;
}else{
listNode.addNode(key,value);
}
}
public static void main(String[] args) {
// 1、一般校驗
MyHashMap hashMap0=new MyHashMap();
hashMap0.put("key1","value1");
System.out.println("一般校驗："+hashMap0.get("key1"));
System.out.println("--------------------------------------------");
// 2、同key覆蓋校驗
MyHashMap hashMap1=new MyHashMap();
hashMap1.put("key2","value00");
hashMap1.put("key2","value01");
System.out.println("同key覆蓋校驗："+hashMap1.get("key2"));
System.out.println("--------------------------------------------");
// 3、哈希碰撞校驗(k1和k9的經(jīng)過哈希計算后得到的索引都是6)
MyHashMap hashMap2=new MyHashMap();
hashMap2.put("k1","value_k1");
hashMap2.put("k9","value_k9");
System.out.println("哈希碰撞校驗：k1:"+hashMap2.get("k1")+" k9:"+hashMap2.get("k9"));
System.out.println("--------------------------------------------");
// 4、擴容校驗
MyHashMap hashMap3=new MyHashMap();
hashMap3.put("m3","cccccc");
hashMap3.put("c1","kkkkkk");
hashMap3.put("c2","mmmmmmm");
hashMap3.put("b1","bbbbbbb");
hashMap3.put("m1","cccccc");
hashMap3.put("c3","kkkkkk");
hashMap3.put("c4","mmmmmmm");
hashMap3.put("b2","bbbbbbb");
hashMap3.put("m2","cccccc");
hashMap3.put("c5","kkkkkk");
hashMap3.put("c6","mmmmmmm");
hashMap3.put("b3","bbbbbbb");
System.out.println("擴容后的c4:"+hashMap3.get("c4"));
System.out.println("擴容后的b3:"+hashMap3.get("b3"));
}
}3.運行結(jié)果
到此這篇關(guān)于基于Java快速實現(xiàn)一個簡單版的HashMap詳解的文章就介紹到這了,更多相關(guān)Java HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
這篇文章主要介紹了SpringBoot實現(xiàn)物品收藏功能,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2021-04-04 
這篇文章主要介紹了SpringBoot登錄驗證碼實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-04-04 
這篇文章主要介紹了elasticsearch head的安裝及使用過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2019-09-09 
Java 如何快速,優(yōu)雅的實現(xiàn)導出Excel
這篇文章主要介紹了Java 如何快速,優(yōu)雅的實現(xiàn)導出Excel，幫助大家更好的理解和學習使用Java，感興趣的朋友可以了解下
2021-03-03 
這篇文章主要介紹了Spring中ThreadLocal的解析，Spring通過各種DAO模板類降低了開發(fā)者使用各種數(shù)據(jù)持久技術(shù)的難度。這些模板類都是線程安全的，也就是說，多個DAO可以復用同一個模板實例而不會發(fā)生沖突，下面一起進入文章學子詳細內(nèi)容吧
2022-01-01 
這篇文章主要介紹了Thread.join()詳解?,join是Thread類的一個方法，啟動線程后直接調(diào)用，本文通過實例代碼介紹了join方法的作用及用法詳解，需要的朋友可以參考下
2023-09-09 
這篇文章主要為大家介紹了Flowable執(zhí)行完畢的流程查找方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-11-11 
淺談spring-boot-rabbitmq動態(tài)管理的方法
這篇文章主要介紹了淺談spring-boot-rabbitmq動態(tài)管理的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-12-12 
記一次集成swagger2(Knife4j)在線文檔提示:Knude4j文檔請求異常的解決辦法
Knife4j是一個集Swagger2 和 OpenAPI3為一體的增強解決方案,下面這篇文章主要給大家介紹了關(guān)于一次集成swagger2(Knife4j)在線文檔提示:Knude4j文檔請求異常的解決辦法,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
2024-02-02