HashMap原理及手寫(xiě)實(shí)現(xiàn)部分區(qū)塊鏈特征
寫(xiě)在前面
最近有很多的粉絲私信我，說(shuō)自己在面試的時(shí)候，老是被人問(wèn)HashMap的原理，但是在實(shí)際的工作中，也只是使用HashMap，從來(lái)就沒(méi)有關(guān)注過(guò)它的原來(lái)，今天博主本人，根據(jù)自己的實(shí)際經(jīng)驗(yàn)，淺談一下HashMap的實(shí)現(xiàn)原理。并附上自己根據(jù)原理，手寫(xiě)的MHashMap，并且還帶上了部分區(qū)塊鏈的特征。
JDK7和JDK8中的HashMap
JDK7：數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu) JDK8：數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)，紅黑樹(shù) 兩者之間的區(qū)別就是，JDK8中加上了紅黑樹(shù)。 因?yàn)榻裉焓且粋€(gè)HashMap的原理淺析，這里就不附帶講解紅黑樹(shù)，后面的博文，我會(huì)專(zhuān)門(mén)來(lái)講解紅黑樹(shù)。
正文
現(xiàn)在我開(kāi)始正式進(jìn)入我對(duì)HashMap講解中來(lái)。 HashMap的特征
存儲(chǔ)結(jié)構(gòu)：key，value鍵值對(duì)的形式
查詢數(shù)據(jù)：
- 1，通過(guò)key進(jìn)行mod（取模），獲取到當(dāng)前數(shù)組對(duì)應(yīng)的node，
- 2，根據(jù)node存放的hash和key對(duì)應(yīng)的hash進(jìn)行比較，是否一致，如果不一致，則同當(dāng)前node的下一個(gè)node進(jìn)行比對(duì)。
- 3，還是不一致，就繼續(xù)從當(dāng)前比較的Node取下一個(gè)節(jié)點(diǎn)進(jìn)行比較。
存儲(chǔ)數(shù)據(jù)：
- 1，對(duì)key進(jìn)行mod計(jì)算
- 2，將數(shù)據(jù)存放到data[mod]中去
- 3，如果當(dāng)前的data[mod]已經(jīng)有值存在了，則將當(dāng)前已經(jīng)存在的對(duì)象oldNode，存放到新的Node的next中去
我們定義一個(gè)數(shù)組，并給給它一個(gè)默認(rèn)的長(zhǎng)度
private final static int defaultDataLength = 16;
再創(chuàng)建一個(gè)指定長(zhǎng)度的數(shù)組
private Node[] data = new Node[defaultDataLength];
這里的Node為我們自己定義的一個(gè)內(nèi)部類(lèi)對(duì)象
@Getter
@Setter
static class Node {
private int hashCode;
private Object key;
private Object value;
private Node next;
public static Node instance(int hashCode, Object key, Object value, Node next) {
Node node = new Node();
node.setHashCode(hashCode);
node.setKey(key);
node.setValue(value);
node.setNext(next);
return node;
}
}
它由四個(gè)元素組成，當(dāng)前傳入key的hash值，當(dāng)前的key，當(dāng)前的value及下一個(gè)對(duì)象。
完整代碼
package com.moonl.jvm.utils;
import lombok.Getter;
import lombok.Setter;
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.Map;
import java.util.Set;
public class MHashMap<K, V> {
private final static int defaultDataLength = 16;
private Node[] data = new Node[defaultDataLength];
private Integer previousHashCode = 0;
public V put(K key, V value) {
int hash = hash(key);
int mod = hashMod(key);
if (null == data[mod]) {
data[mod] = Node.instance(hash, key, value, null);
return value;
}
//舊的node緩存
Node oldNode = data[mod];
//新的key，存放到指定位置的數(shù)組中去，并將原有節(jié)點(diǎn)存放到next中
data[mod] = Node.instance(hash, key, value, oldNode);
return value;
}
public V get(K key) {
Node node = data[hashMod(key)];
//root node hashCode
this.previousHashCode = hash((K) ("root_" + hashMod(key)));
return findKey(node, key);
}
public V findKey(Node node, K key) {
if (null == key) {
return null;
}
if (node == null) {
return null;
}
String chain = "The Previous HashCode:" + previousHashCode + " Now HashCode :" + node.getHashCode();
//傳入的key對(duì)應(yīng)的hash
int hash = hash(key);
//當(dāng)前節(jié)點(diǎn)存儲(chǔ)的hashCode
int hashCode = node.getHashCode();
if (hash == hashCode) {
System.out.println("input key is :" + key + " and hash:" + hashCode);
System.out.println("query key is :" + node.getKey() + " and hash:" + node.getHashCode());
return (V) node.getValue();
}
//當(dāng)前找到的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
Node nextNode = node.getNext();
//如果要從下一個(gè)節(jié)點(diǎn)開(kāi)始查詢，則當(dāng)前節(jié)點(diǎn)變更為上一個(gè)節(jié)點(diǎn)
previousHashCode = node.getHashCode();
chain = chain + " Next Node HashCode :" + nextNode.getHashCode();
System.out.println(chain);
return findKey(nextNode, key);
}
public int hash(K key) {
int hashCode = 0;
return key == null ? 0 : key.hashCode();
}
public int hashMod(K key) {
return Math.abs(key.hashCode() % 16);
}
@Getter
@Setter
static class Node {
private int hashCode;
private Object key;
private Object value;
private Node next;
public static Node instance(int hashCode, Object key, Object value, Node next) {
Node node = new Node();
node.setHashCode(hashCode);
node.setKey(key);
node.setValue(value);
node.setNext(next);
return node;
}
}
}
在代碼中，我對(duì)根節(jié)點(diǎn)，也就是數(shù)組節(jié)點(diǎn)的記錄方式是"root_"+mod值共同生成的hash // 現(xiàn)在我們開(kāi)始使用封裝數(shù)據(jù)（put），并逐步（get）數(shù)據(jù)
@Test
public void testHashMap() {
// Map<String, Object> maps = new HashMap<String, Object>();
MHashMap<String, Object> zhaoMaps = new MHashMap<String, Object>();
for (int i = 0; i < 1000; i++) {
zhaoMaps.put("趙"+i+"姐","趙穎"+i+"姐 is 250");
}
MHashMap<String, Object> yingMaps = new MHashMap<String, Object>();
for (int i = 0; i < 1000; i++) {
yingMaps.put("大穎"+i+"姐","大穎"+i+"姐 is 250");
}
System.out.println(zhaoMaps.get("趙162姐"));
System.out.println(yingMaps.get("大穎456姐"));
}
輸出的結(jié)果是
The Previous HashCode:-925311973 Now HashCode :-914498616 Next Node HashCode :-914499608
The Previous HashCode:-914498616 Now HashCode :-914499608 Next Node HashCode :-914500600
The Previous HashCode:-914499608 Now HashCode :-914500600 Next Node HashCode :-914501592
The Previous HashCode:-914500600 Now HashCode :-914501592 Next Node HashCode :-914502584
The Previous HashCode:-914501592 Now HashCode :-914502584 Next Node HashCode :-914503576
The Previous HashCode:-914502584 Now HashCode :-914503576 Next Node HashCode :-914529368
The Previous HashCode:-914503576 Now HashCode :-914529368 Next Node HashCode :-914530360
The Previous HashCode:-914529368 Now HashCode :-914530360 Next Node HashCode :-914531352
The Previous HashCode:-914530360 Now HashCode :-914531352 Next Node HashCode :-914532344
The Previous HashCode:-914531352 Now HashCode :-914532344 Next Node HashCode :-914533336
The Previous HashCode:-914532344 Now HashCode :-914533336 Next Node HashCode :-914560120
The Previous HashCode:-914533336 Now HashCode :-914560120 Next Node HashCode :-914561112
The Previous HashCode:-914560120 Now HashCode :-914561112 Next Node HashCode :-914562104
The Previous HashCode:-914561112 Now HashCode :-914562104 Next Node HashCode :-914563096
The Previous HashCode:-914562104 Now HashCode :-914563096 Next Node HashCode :-914584424
The Previous HashCode:-914563096 Now HashCode :-914584424 Next Node HashCode :-914590872
The Previous HashCode:-914584424 Now HashCode :-914590872 Next Node HashCode :-914591864
The Previous HashCode:-914590872 Now HashCode :-914591864 Next Node HashCode :-914592856
The Previous HashCode:-914591864 Now HashCode :-914592856 Next Node HashCode :-914614184
The Previous HashCode:-914592856 Now HashCode :-914614184 Next Node HashCode :-914615176
The Previous HashCode:-914614184 Now HashCode :-914615176 Next Node HashCode :-914621624
The Previous HashCode:-914615176 Now HashCode :-914621624 Next Node HashCode :-914622616
The Previous HashCode:-914621624 Now HashCode :-914622616 Next Node HashCode :-914643944
The Previous HashCode:-914622616 Now HashCode :-914643944 Next Node HashCode :-914644936
The Previous HashCode:-914643944 Now HashCode :-914644936 Next Node HashCode :-914645928
The Previous HashCode:-914644936 Now HashCode :-914645928 Next Node HashCode :-914652376
The Previous HashCode:-914645928 Now HashCode :-914652376 Next Node HashCode :-914673704
The Previous HashCode:-914652376 Now HashCode :-914673704 Next Node HashCode :-914674696
The Previous HashCode:-914673704 Now HashCode :-914674696 Next Node HashCode :-914675688
The Previous HashCode:-914674696 Now HashCode :-914675688 Next Node HashCode :-914676680
The Previous HashCode:-914675688 Now HashCode :-914676680 Next Node HashCode :-914703464
The Previous HashCode:-914676680 Now HashCode :-914703464 Next Node HashCode :-914704456
The Previous HashCode:-914703464 Now HashCode :-914704456 Next Node HashCode :-914705448
The Previous HashCode:-914704456 Now HashCode :-914705448 Next Node HashCode :-914706440
The Previous HashCode:-914705448 Now HashCode :-914706440 Next Node HashCode :-914707432
The Previous HashCode:-914706440 Now HashCode :-914707432 Next Node HashCode :-914733224
The Previous HashCode:-914707432 Now HashCode :-914733224 Next Node HashCode :-914734216
The Previous HashCode:-914733224 Now HashCode :-914734216 Next Node HashCode :-914735208
The Previous HashCode:-914734216 Now HashCode :-914735208 Next Node HashCode :-914736200
input key is :趙162姐 and hash:-914736200
query key is :趙162姐 and hash:-914736200
趙穎162姐 is 250
The Previous HashCode:-925311975 Now HashCode :-2010266582 Next Node HashCode :-2010267574
The Previous HashCode:-2010266582 Now HashCode :-2010267574 Next Node HashCode :-2010268566
The Previous HashCode:-2010267574 Now HashCode :-2010268566 Next Node HashCode :-2010269558
The Previous HashCode:-2010268566 Now HashCode :-2010269558 Next Node HashCode :-2010270550
The Previous HashCode:-2010269558 Now HashCode :-2010270550 Next Node HashCode :-2010271542
The Previous HashCode:-2010270550 Now HashCode :-2010271542 Next Node HashCode :-2010296342
The Previous HashCode:-2010271542 Now HashCode :-2010296342 Next Node HashCode :-2010297334
The Previous HashCode:-2010296342 Now HashCode :-2010297334 Next Node HashCode :-2010298326
The Previous HashCode:-2010297334 Now HashCode :-2010298326 Next Node HashCode :-2010299318
The Previous HashCode:-2010298326 Now HashCode :-2010299318 Next Node HashCode :-2010300310
The Previous HashCode:-2010299318 Now HashCode :-2010300310 Next Node HashCode :-2010301302
The Previous HashCode:-2010300310 Now HashCode :-2010301302 Next Node HashCode :-2010302294
The Previous HashCode:-2010301302 Now HashCode :-2010302294 Next Node HashCode :-2010326102
The Previous HashCode:-2010302294 Now HashCode :-2010326102 Next Node HashCode :-2010327094
The Previous HashCode:-2010326102 Now HashCode :-2010327094 Next Node HashCode :-2010328086
The Previous HashCode:-2010327094 Now HashCode :-2010328086 Next Node HashCode :-2010329078
The Previous HashCode:-2010328086 Now HashCode :-2010329078 Next Node HashCode :-2010330070
The Previous HashCode:-2010329078 Now HashCode :-2010330070 Next Node HashCode :-2010331062
The Previous HashCode:-2010330070 Now HashCode :-2010331062 Next Node HashCode :-2010332054
The Previous HashCode:-2010331062 Now HashCode :-2010332054 Next Node HashCode :-2010333046
The Previous HashCode:-2010332054 Now HashCode :-2010333046 Next Node HashCode :-2010355862
The Previous HashCode:-2010333046 Now HashCode :-2010355862 Next Node HashCode :-2010356854
The Previous HashCode:-2010355862 Now HashCode :-2010356854 Next Node HashCode :-2010357846
The Previous HashCode:-2010356854 Now HashCode :-2010357846 Next Node HashCode :-2010358838
The Previous HashCode:-2010357846 Now HashCode :-2010358838 Next Node HashCode :-2010359830
The Previous HashCode:-2010358838 Now HashCode :-2010359830 Next Node HashCode :-2010360822
The Previous HashCode:-2010359830 Now HashCode :-2010360822 Next Node HashCode :-2010361814
The Previous HashCode:-2010360822 Now HashCode :-2010361814 Next Node HashCode :-2010362806
The Previous HashCode:-2010361814 Now HashCode :-2010362806 Next Node HashCode :-2010363798
The Previous HashCode:-2010362806 Now HashCode :-2010363798 Next Node HashCode :-2010385622
The Previous HashCode:-2010363798 Now HashCode :-2010385622 Next Node HashCode :-2010386614
The Previous HashCode:-2010385622 Now HashCode :-2010386614 Next Node HashCode :-2010387606
The Previous HashCode:-2010386614 Now HashCode :-2010387606 Next Node HashCode :-2010388598
The Previous HashCode:-2010387606 Now HashCode :-2010388598 Next Node HashCode :-2010389590
The Previous HashCode:-2010388598 Now HashCode :-2010389590 Next Node HashCode :-2010390582
The Previous HashCode:-2010389590 Now HashCode :-2010390582 Next Node HashCode :-2010391574
The Previous HashCode:-2010390582 Now HashCode :-2010391574 Next Node HashCode :-2010392566
The Previous HashCode:-2010391574 Now HashCode :-2010392566 Next Node HashCode :-2010393558
The Previous HashCode:-2010392566 Now HashCode :-2010393558 Next Node HashCode :-2010394550
The Previous HashCode:-2010393558 Now HashCode :-2010394550 Next Node HashCode :-2010416374
The Previous HashCode:-2010394550 Now HashCode :-2010416374 Next Node HashCode :-2010417366
The Previous HashCode:-2010416374 Now HashCode :-2010417366 Next Node HashCode :-2010418358
The Previous HashCode:-2010417366 Now HashCode :-2010418358 Next Node HashCode :-2010419350
input key is :大穎456姐 and hash:-2010419350
query key is :大穎456姐 and hash:-2010419350
大穎456姐 is 250
通過(guò)輸出的日志，我們可以看見(jiàn)，node節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是按照區(qū)塊鏈的特性，記錄上個(gè)節(jié)點(diǎn)的信息和下一個(gè)節(jié)點(diǎn)的信息關(guān)系來(lái)存儲(chǔ)數(shù)據(jù)。
當(dāng)然，這里我們對(duì)Node對(duì)象再寫(xiě)深入一些，加上一些共識(shí)的算法，加密解密驗(yàn)簽的算法，并做節(jié)點(diǎn)的共享，那么一個(gè)簡(jiǎn)單的區(qū)塊鏈就完成了。
本文，主要是為了解答粉絲在面試過(guò)程中，面試官不停問(wèn)HashMap原理而編寫(xiě)的，區(qū)塊鏈就不做更多的闡述了。
更多關(guān)于HashMap區(qū)塊鏈特征的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
在java中控制流程語(yǔ)句是由選擇語(yǔ)句、循環(huán)語(yǔ)句、跳轉(zhuǎn)語(yǔ)句構(gòu)成,選擇語(yǔ)句包括if和switch,在過(guò)多的使用if語(yǔ)句嵌套會(huì)使程序很難閱讀,這時(shí)就可以用到switch語(yǔ)句,這篇文章主要給大家介紹了關(guān)于Java中Switch的使用方法及新特性的相關(guān)資料,需要的朋友可以參考下2023-11-11
javaweb前端向后端傳值的幾種方式總結(jié)(附代碼)
javaweb是java開(kāi)發(fā)中的一個(gè)方向,下面這篇文章主要給大家介紹了關(guān)于javaweb前端向后端傳值的幾種方式的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
這篇文章主要介紹了 Java抽象類(lèi)示例,抽象類(lèi)通常用于定義一些公共的方法和屬性，但是這些方法沒(méi)有具體的實(shí)現(xiàn),需要的朋友可以參考下2023-05-05
Java輸入三個(gè)整數(shù)并把他們由小到大輸出(x,y,z)
這篇文章主要介紹了輸入三個(gè)整數(shù)x,y,z，請(qǐng)把這三個(gè)數(shù)由小到大輸出,需要的朋友可以參考下2017-02-02
springboot整合jquery和bootstrap框架過(guò)程圖解
這篇文章主要介紹了springboot整合jquery和bootstrap框架過(guò)程圖解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
Java中的Set、List、Map的用法與區(qū)別介紹
這篇文章主要介紹了Java中的Set、List、Map的用法與區(qū)別,需要的朋友可以參考下2016-06-06
SpringBoot中實(shí)現(xiàn)登錄攔截器的代碼實(shí)例
這篇文章主要介紹了SpringBoot中實(shí)現(xiàn)登錄攔截器的代碼實(shí)例,對(duì)于管理系統(tǒng)或其他需要用戶登錄的系統(tǒng),登錄驗(yàn)證都是必不可少的環(huán)節(jié),在SpringBoot開(kāi)發(fā)的項(xiàng)目中,通過(guò)實(shí)現(xiàn)攔截器來(lái)實(shí)現(xiàn)用戶登錄攔截并驗(yàn)證,需要的朋友可以參考下2023-10-10
springboot跨域如何設(shè)置SameSite的實(shí)現(xiàn)
這篇文章主要介紹了springboot跨域如何設(shè)置SameSite的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
springBoot之如何獲取接口請(qǐng)求數(shù)據(jù)和返回?cái)?shù)據(jù)實(shí)現(xiàn)日志
這篇文章主要介紹了springBoot之如何獲取接口請(qǐng)求數(shù)據(jù)和返回?cái)?shù)據(jù)實(shí)現(xiàn)日志問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
這篇文章主要介紹了Java中的StringBuilder類(lèi)解析,該類(lèi)被設(shè)計(jì)用作StringBuffer的一個(gè)簡(jiǎn)易替換,用在字符串緩沖區(qū)被單線程使用的時(shí)候,如果可能,優(yōu)先采用該類(lèi),因?yàn)樵诖蠖鄶?shù)實(shí)現(xiàn)中,String Builder比StringBuffer要快,需要的朋友可以參考下2023-09-09