什么是HashMap

這一節(jié)課，我們來(lái)手寫(xiě)一個(gè)簡(jiǎn)單的HashMap，所謂HashMap，就是一個(gè)映射表。

比如現(xiàn)在我有一個(gè)客戶類，就用之前的就好。

現(xiàn)在我有100個(gè)客戶，名字各不相同，有叫張三的，也有叫李四的，還有的人叫張全蛋。如果現(xiàn)在要你從這100個(gè)人中找到一個(gè)叫做王尼瑪?shù)娜?，你怎么辦？

這好像很簡(jiǎn)單，我們不是剛剛做了一個(gè)TuziLinkedList嗎？一個(gè)個(gè)add進(jìn)去，數(shù)據(jù)初始化，然后再用foreach去遍歷不就行了？可是，這樣的效率是很低的，假如王尼瑪正好在鏈表的最后一個(gè)，那就需要遍歷100次才能找到。復(fù)雜度是o（n）

這個(gè)時(shí)候，要是有一種辦法能讓我們一下子就通過(guò)name，去找到王尼瑪這個(gè)人就好了。

其實(shí)這個(gè)辦法是有的，就是查表法，我們需要的就是這樣的一個(gè)映射表。

映射表分為key和value，在這個(gè)例子中，key就是name字段。這樣一來(lái)，復(fù)雜度就是o（1），只需要遍歷一次就可以了。

簡(jiǎn)單來(lái)說(shuō)，不管有多少個(gè)數(shù)據(jù)，如果你用關(guān)系映射表Map，只需要一次，你就直接通過(guò)某一個(gè)key，拿到了對(duì)應(yīng)的Customer對(duì)象。

為什么這么神奇呢？

那是因?yàn)?，Map的底層是一個(gè)數(shù)組。

什么是數(shù)組？

數(shù)組的知識(shí)比較基礎(chǔ)，網(wǎng)上已經(jīng)被講爛了，直接參考菜鳥(niǎo)教程即可：

https://www.runoob.com/java/java-array.html

因?yàn)閿?shù)組是直接用數(shù)字下標(biāo)去獲取對(duì)應(yīng)的值的，復(fù)雜度是最低的，所以Map的查詢才會(huì)這么快。

我們要做的一種映射關(guān)系表，寫(xiě)法大概是這樣的。

public class TestMap {
    public static void main(String[] args) {
        Map csts = new HashMap<>();
        csts.put("王大錘",new Customer("王大錘"));
        csts.put("王尼瑪",new Customer("王尼瑪"));
        csts.put("趙鐵柱",new Customer("趙鐵柱"));
        //直接根據(jù)name拿到對(duì)應(yīng)的實(shí)體對(duì)象
        Customer customer = (Customer) csts.get("王大錘");
        System.out.println(customer.getName());
    }
}

這是java自帶的HashMap，我們就需要實(shí)現(xiàn)類似的功能。

HashCode和數(shù)組

先考慮第一個(gè)問(wèn)題，既然HashMap底層是用數(shù)組，可是key不一定是數(shù)字，那么就得想辦法把key轉(zhuǎn)化為一個(gè)數(shù)字。

HashCode就是一種hash碼值，任何一個(gè)字符串，對(duì)象都有自己的Hash碼，計(jì)算方式如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用 int 算法，這里 s[i] 是字符串的第 i 個(gè)字符，n 是字符串的長(zhǎng)度，^ 表示求冪。空字符串的哈希值為 0。

比如字符串是“abc”, 套用公式計(jì)算如下：

String a = "abc";
//  97 * 31^(3-1) + 98 * 31^(3-2) + 99 ^ (3-3)
//= 93217 + 3038 + 99 = 96354
System.out.println(a.hashCode());

答案正是：

我們99%的情況，HashMap的key就是String，所以都可以用這個(gè)公式去計(jì)算。HashCode算法的牛逼之處在于，任何字符串都可以對(duì)應(yīng)唯一的一個(gè)數(shù)字。

相信你肯定有一個(gè)疑惑，就是為啥Hash算法用的是31的冪等運(yùn)算？

在名著 《Effective Java》第 42 頁(yè)就有對(duì) hashCode 為什么采用 31 做了說(shuō)明：

之所以使用 31， 是因?yàn)樗且粋€(gè)奇素?cái)?shù)。如果乘數(shù)是偶數(shù)，并且乘法溢出的話，信息就會(huì)丟失，因?yàn)榕c2相乘等價(jià)于移位運(yùn)算（低位補(bǔ)0）。使用素?cái)?shù)的好處并不很明顯，但是習(xí)慣上使用素?cái)?shù)來(lái)計(jì)算散列結(jié)果。 31 有個(gè)很好的性能，即用移位和減法來(lái)代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i， 現(xiàn)代的 VM 可以自動(dòng)完成這種優(yōu)化。這個(gè)公式可以很簡(jiǎn)單的推導(dǎo)出來(lái)。

反正大概意思就是一些數(shù)學(xué)家發(fā)現(xiàn)，用31計(jì)算hash值的話，性能是最好的。畢竟你也不希望算個(gè)HashCode花太多時(shí)間吧。

一開(kāi)始，我們不需要做的太完美，剛開(kāi)始的時(shí)候，完成永遠(yuǎn)優(yōu)于完美。

public class TuziHashMap {
    private Object arr[];
    private int capacity = 20; //初始化容量
    public  TuziHashMap(){
        arr = new Object[capacity];
    }
}

TuziHashMap內(nèi)部維護(hù)了一個(gè)數(shù)組，初識(shí)容量為20。接下來(lái)，實(shí)現(xiàn)put方法，put方法就是給這個(gè)Map添加新的元素。

public Object put(String key,Object value){
        //1\. 算出HashCode
        int hashCode = key.hashCode();
        //2\. 直接取模，得到余數(shù)，這個(gè)余數(shù)就是數(shù)組的下標(biāo)
        int index = hashCode % capacity;
        //3\. 將對(duì)應(yīng)的數(shù)據(jù)放入數(shù)組的對(duì)應(yīng)格子
        this.arr[index] = value;
        return  value;

    }

然后是get方法，接收對(duì)應(yīng)的key值，返回對(duì)應(yīng)的元素。

public Object get(String key){
        //1\. 算出HashCode
        int hashCode = key.hashCode();
        //2\. 直接取模，得到余數(shù)，這個(gè)余數(shù)就是數(shù)組的下標(biāo)
        int index = hashCode % capacity;
        //3\. 將對(duì)應(yīng)的數(shù)據(jù)放入數(shù)組的對(duì)應(yīng)格子
        return this.arr[index];
    }

代碼非常相似，先別管優(yōu)不優(yōu)化，實(shí)現(xiàn)功能再說(shuō)，這就是踏出的第一步。

TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
System.out.println(map.get("王大錘"));

效果：

Hash碰撞

Hash碰撞也叫做Hash沖突，就是當(dāng)兩個(gè)key算出來(lái)HashCode相同的情況下，就會(huì)產(chǎn)生沖突。

目前我們的Map類中，底層的數(shù)組長(zhǎng)度默認(rèn)值20（真正的HashMap默認(rèn)值是16），當(dāng)存入的數(shù)據(jù)足夠多并且不進(jìn)行擴(kuò)容的話，Hash碰撞是必然的。所謂Hash碰撞，就是比如說(shuō)兩個(gè)key明明是不同的，但是經(jīng)過(guò)hash算法后，hash值竟然是相同的。那么另一個(gè)key的value就會(huì)覆蓋之前的，從而引起錯(cuò)誤。

添加專門(mén)的hash方法，然后先寫(xiě)死hashcode為10，那就一定會(huì)發(fā)生hash碰撞！

private int hash(String key){
    //return key.hashCode();
    return 10;
}

get方法也要改過(guò)來(lái)，用hash方法：

public Object get(String key){
        //1\. 算出HashCode
        int hashCode = hash(key);
        //2\. 直接取模，得到余數(shù)，這個(gè)余數(shù)就是數(shù)組的下標(biāo)
        int index = hashCode % capacity;
        //3\. 將對(duì)應(yīng)的數(shù)據(jù)放入數(shù)組的對(duì)應(yīng)格子
        return this.arr[index];
    }

TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
map.put("王尼瑪",new Customer("王尼瑪"));
System.out.println(map.get("王大錘"));

結(jié)果：

Customer{name=‘王尼瑪', sex=‘null', birthDate=‘null', phoneNumber=‘null', status=0}

原因：產(chǎn)生了Hash碰撞，后面的王尼瑪直接把王大錘給覆蓋了。

怎么解決Hash碰撞呢？因?yàn)镠ash碰撞在實(shí)際應(yīng)用中肯定會(huì)出現(xiàn)，所以，我們就不能在數(shù)組的每一個(gè)格子中直接存Object對(duì)象，而應(yīng)該弄一個(gè)鏈表。

假如出現(xiàn)Hash碰撞，就直接在鏈表中加一個(gè)節(jié)點(diǎn)。然后，下次取元素的時(shí)候，如果遇到Hash碰撞的情況就去循環(huán)那個(gè)鏈表，從而解決了Hash沖突的問(wèn)題。

有了基本的思路，我們就得去修改put方法。

put方法接收一個(gè)key，一個(gè)value。如果發(fā)生Hash沖突，就得把新的key和value加到鏈表的末尾。

初步代碼如下：

但是，這樣有個(gè)問(wèn)題，你沒(méi)法取。為什么沒(méi)法取呢？因?yàn)?，鏈表上的每一個(gè)節(jié)點(diǎn)，我們只保存了value，沒(méi)有key。那么相同的key的情況，怎么去獲取對(duì)應(yīng)的元素呢？比如兩個(gè)key，分別是“王大錘”和“王尼瑪”，假如他們的HashCode是相同的，因?yàn)殒湵砩蠜](méi)有保存“王大錘”和“王尼瑪”兩個(gè)key，我們就沒(méi)法區(qū)分了。

沒(méi)有辦法，只好修改一下之前的Node。為什么之前沒(méi)有加key呢？因?yàn)橹暗腘ode類是為L(zhǎng)inkedList服務(wù)的，LinkedList不需要key這個(gè)東西。

在linkedList中，原來(lái)的add方法是不需要key的，所以也需要做一個(gè)修改：

/**
 * 原來(lái)的add方法保留，調(diào)用重載的add方法
 * @param object
 * @return
 */
public boolean add(Object object){
	return add(null,object);
}
/**
 * 新增的add方法,增加參數(shù)key
 */
public boolean add(Object key,Object object){
	//將數(shù)據(jù)用節(jié)點(diǎn)類包裝好，這樣才能實(shí)現(xiàn)下一個(gè)數(shù)據(jù)的指向
	Node data = new Node(object);
	if(key != null){
		data.key = key;
	}
	//先判斷是否是第一個(gè)節(jié)點(diǎn)
	if(this.firstNode == null){
		this.firstNode = data;
		this.currentNode = data;
	}else{
		//不是第一個(gè)節(jié)點(diǎn)，就指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即currentNode.next
		this.currentNode.next = data;
		//因?yàn)橐呀?jīng)指向下一個(gè)了，所以當(dāng)前節(jié)點(diǎn)也要移動(dòng)過(guò)來(lái)
		this.currentNode = data;
	}
	size++;
	return true;

}

如果你讀過(guò)jdk里面的源碼，就一定會(huì)知道，在很多Java基礎(chǔ)類中，都有一大堆的構(gòu)造方法，一大堆方法重載。而且，很多方法里面都會(huì)調(diào)用同名的方法，只不過(guò)參數(shù)傳的不一樣罷了。

我之前也一直不理解，為什么要整的這么麻煩，后來(lái)當(dāng)自己嘗試寫(xiě)一些數(shù)據(jù)結(jié)構(gòu)的時(shí)候，才明白，不這樣搞真的不行。方法重載的意義不是去秀肌肉的，而是減少代碼的工作量。

比如，因?yàn)長(zhǎng)inkedList需要增加key的保存，原來(lái)的add方法是沒(méi)有的。我們不太好直接修改原來(lái)的add方法，因?yàn)槿f(wàn)一這個(gè)類被很多調(diào)用了，那么很多地方都會(huì)受到不同程度的影響。所以，類的設(shè)計(jì)思路有一條很重要，那就是：

做增量好過(guò)做修改。

還是原來(lái)的測(cè)試代碼：

TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
map.put("王尼瑪",new Customer("王尼瑪"));
System.out.println(map.get("王大錘"));

因?yàn)槲覀冃薷牧薶ash方法，強(qiáng)行導(dǎo)致Hash碰撞，所以目前是肯定沖突的。

運(yùn)行：

Customer{name=‘王大錘', sex=‘null', birthDate=‘null', phoneNumber=‘null', status=0}

成功了，王尼瑪沒(méi)有覆蓋掉王大錘。

toString方法

為了更好的調(diào)試，我們給TuziHashMap添加toString方法

public String toString(){
    StringBuffer sb = new StringBuffer("[\n");
    for (int i = 0; i < arr.length; i++) {
        LinkedList list = arr[i];
        if(list != null){
            while(list.hasNext()){
                Node node = list.nextNode();
                sb.append(String.format("\t{%s=%s}",node.key,node.data));

                if(list.hasNext())
                    sb.append(",\n");
                else
                    sb.append("\n");
            }
        }
    }
    sb.append("]");
    return sb.toString();
}

運(yùn)行之前的測(cè)試代碼，就是這樣的：

百萬(wàn)級(jí)數(shù)據(jù)壓測(cè)

做一點(diǎn)性能測(cè)試，又有新的問(wèn)題了。。。

步驟 1 來(lái)100w條數(shù)據(jù)，看看要花多久？

long startTime = System.currentTimeMillis();     //獲取開(kāi)始時(shí)間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis();      //獲取結(jié)束時(shí)間
System.out.println("程序運(yùn)行時(shí)間為："+(overTime-startTime)+"毫秒");

上面的代碼就是循環(huán)10w次，然后用一個(gè)toString全部打印出來(lái)，看看需要多久吧？

大概是800毫秒左右。

可如果是100w呢？

直接報(bào)錯(cuò)了，原因是JVM內(nèi)存溢出。這是為什么呢？

那是因?yàn)?，我們的Map初識(shí)容量是20,100w條數(shù)據(jù)插進(jìn)去，想也知道鏈表是扛不住了。

步驟 2 設(shè)計(jì)思路

1.初始化數(shù)組

2.每次put的時(shí)候，就計(jì)算是不是快溢出來(lái)了，如果是，數(shù)組翻倍。

3.由于數(shù)組容量翻倍了，原來(lái)的數(shù)據(jù)需要重新計(jì)算hash值，散列到新的數(shù)組中去。（不這樣做的話，數(shù)組利用率會(huì)不夠，很多數(shù)據(jù)全部擠在前半段）

步驟 3 添加一個(gè)size

現(xiàn)在的數(shù)組長(zhǎng)度是20，最理想的情況，添加20個(gè)元素，一次Hash碰撞都沒(méi)有，均勻分布在20個(gè)格子里面。當(dāng)添加第21個(gè)的時(shí)候，一定會(huì)發(fā)生Hash碰撞，這個(gè)時(shí)候我們就需要去擴(kuò)容數(shù)組了。

步驟 4 先設(shè)計(jì)，后實(shí)現(xiàn)

因?yàn)榇a寫(xiě)到這里，已經(jīng)開(kāi)始慢慢變得復(fù)雜了。我們可以參考之前接口的章節(jié)，先設(shè)計(jì)，再談如何實(shí)現(xiàn)。只要設(shè)計(jì)是合理了，就別擔(dān)心能不能實(shí)現(xiàn)的問(wèn)題。如果你一開(kāi)始就陷入到各種細(xì)節(jié)里面，那你就很難更進(jìn)一步。

利用DIEA的自動(dòng)提示功能，生成擴(kuò)容方法。

步驟 5 擴(kuò)容方法

private void enlarge() {
    capacity *= 2; // 等同于 capacity = capacity * 2 ，這么寫(xiě)只是因?yàn)槲蚁胙b個(gè)逼。
    LinkedList[] newArr = new LinkedList[capacity];
    System.out.println("數(shù)組擴(kuò)容到" + capacity);
    int len = arr.length; //把a(bǔ)rr的長(zhǎng)度寫(xiě)在外面，這樣能減少一丟丟的計(jì)算
    for (int i = 0; i < len; i++) {
        LinkedList linkedList = arr[i];
        if(arr[i] != null){
            while(linkedList.hasNext()){
                Node node = linkedList.nextNode();
                Object key = node.key;
                Object value = node.data;
                //將原有的數(shù)據(jù)一個(gè)個(gè)塞到新的數(shù)組
                reHash(newArr,key,value);
            }
        }
    }
    //新數(shù)組正式上位
    this.arr = newArr;
}

每個(gè)數(shù)組元素都是一個(gè)鏈表，這個(gè)鏈表里面每一個(gè)數(shù)據(jù)都應(yīng)該要遍歷到，需要再寫(xiě)一個(gè)reHash方法，重新計(jì)算Hash值。

步驟 6 reHash方法

private void reHash(LinkedList[] newArr, Object key, Object value) {
    //1\. 算出HashCode
    int hashCode = hash(key.toString());
    //2\. 直接取模，得到余數(shù)，這個(gè)余數(shù)就是數(shù)組的下標(biāo)
    int index = hashCode % capacity ;
    //3\. 將對(duì)應(yīng)的數(shù)據(jù)放入數(shù)組的對(duì)應(yīng)格子
    if(newArr[index] == null){
        newArr[index] = new LinkedList();
    }
    newArr[index].add(key,value);
}

和put方法差不多，只是多了一個(gè)參數(shù)，如果是JDK的套路，肯定又得做函數(shù)重載了吧。不過(guò)現(xiàn)在趕進(jìn)度，就不做優(yōu)化了。

步驟 7 新的問(wèn)題出現(xiàn)

做個(gè)測(cè)試，我們來(lái)個(gè)26條數(shù)據(jù)，肯定會(huì)觸發(fā)擴(kuò)容的。

long startTime = System.currentTimeMillis();     //獲取開(kāi)始時(shí)間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 260; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis();      //獲取結(jié)束時(shí)間
System.out.println("程序運(yùn)行時(shí)間為："+(overTime-startTime)+"毫秒");

天啊，竟然報(bào)錯(cuò)了！

從錯(cuò)誤信息看，index是-142，也就是說(shuō)hashCode是負(fù)數(shù)。

hashCode怎么會(huì)是負(fù)數(shù)呢？

答案是：hashCode肯定有可能是負(fù)數(shù)。因?yàn)镠ashCode是int類型

int型的值取值范圍為

Integer.MIN_VALUE(-2147483648)～I(xiàn)nteger.MAX_VALUE(2147483647)

那怎么修改呢？可以想到取絕對(duì)值，其實(shí)還有一個(gè)更酷的方法，就是用與邏輯。

為了防止漏改，我們把取模的運(yùn)算抽出來(lái)做成方法。

老規(guī)矩，先把方法寫(xiě)出來(lái)，做設(shè)計(jì)。待會(huì)再去寫(xiě)實(shí)現(xiàn)。

步驟 8 indexForTable方法

private int indexForTable(int hashCode) {
    return hashCode & Integer.MAX_VALUE % capacity;
}

這樣的做法就是確保不會(huì)出現(xiàn)負(fù)數(shù)，效率還高。如果你問(wèn)為什么，那就是計(jì)算機(jī)里面存的int，其實(shí)是有符號(hào)的。如果是負(fù)數(shù)，第一位也就是符號(hào)位就是1，而Integer.MAX_VALUE是正數(shù)。

0x是表示16進(jìn)制的前綴。

第一個(gè)7是16進(jìn)制的7，換算成2進(jìn)制，就是好多個(gè)1，如果算出來(lái)的hashCode是負(fù)數(shù)，那么第一個(gè)就是1，和0進(jìn)行&操作，就會(huì)變成0，于是就變成正數(shù)了。

假如我們的hashCode是10，換算成二進(jìn)制就是1010。你可以用1248法快速口算。

那么，進(jìn)行&運(yùn)算：

可見(jiàn)，這個(gè)操作其實(shí)就是取絕對(duì)值，但是效率更高。

步驟 9 重新轉(zhuǎn)測(cè)

所有用到取模運(yùn)算的地方，都改成indexForTable方法，代碼我就不貼了。

重新測(cè)試，就發(fā)現(xiàn)不報(bào)錯(cuò)了。

步驟 10 再次測(cè)試100w數(shù)據(jù)

其實(shí)站長(zhǎng)剛才測(cè)試的時(shí)候又報(bào)內(nèi)存溢出了，想著估計(jì)是System.out.print語(yǔ)句太多了。（可能之前也是這個(gè)原因，哈哈）

于是，我修改了一下測(cè)試代碼：

long startTime = System.currentTimeMillis();     //獲取開(kāi)始時(shí)間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100 * 10000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis();      //獲取結(jié)束時(shí)間
System.out.println("程序運(yùn)行時(shí)間為："+(overTime-startTime)+"毫秒");

只花了2秒多，這可是100w條數(shù)據(jù)啊，可見(jiàn)HashMap的性能還是很客觀的。

步驟 11 PK 原生JDK8的HashMap

long startTime = System.currentTimeMillis();     //獲取開(kāi)始時(shí)間
HashMap map = new HashMap();
for (int i = 0; i < 100 * 10000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis();      //獲取結(jié)束時(shí)間
System.out.println("程序運(yùn)行時(shí)間為："+(overTime-startTime)+"毫秒");

100w數(shù)據(jù)的情況下，時(shí)間測(cè)下來(lái)是差不多的。不過(guò)即便如此，我們也不要太較真，因?yàn)閖dk8的HashMap肯定寫(xiě)的比我們的好，完善。就比如我們?cè)跀?shù)組的每個(gè)節(jié)點(diǎn)放的是鏈表，而jdk8開(kāi)始，則是鏈表+紅黑樹(shù)的結(jié)構(gòu)，當(dāng)Hash沖突很多的情況下，會(huì)自動(dòng)轉(zhuǎn)換為紅黑樹(shù)，效率會(huì)更加高一點(diǎn)。

補(bǔ)丁

目前的HashMap還只是實(shí)現(xiàn)了最最基本的功能，好多方法都還未實(shí)現(xiàn)，比如remove方法。

步驟 1 put元素的bug

其實(shí)put方法是有一個(gè)bug的，不知道你發(fā)現(xiàn)了沒(méi)有？

原生的HashMap，當(dāng)put相同key的時(shí)候，是直接覆蓋的，而目前的情況是直接追加到鏈表了。這就會(huì)導(dǎo)致我們執(zhí)行

map.get("a")

得到的就是A，而不是AA，AA是永遠(yuǎn)拿不到了。

這個(gè)作為課后作業(yè)，歡迎進(jìn)群一起學(xué)習(xí)交流哦。

步驟 2 HashMap為什么是無(wú)序的？

Java面試題中經(jīng)常會(huì)遇到這個(gè)問(wèn)題，HashMap為什么是無(wú)序的？

現(xiàn)在我們自己寫(xiě)了一個(gè)HashMap，相信你肯定知道原因了吧？key在進(jìn)行hash算法的時(shí)候，誰(shuí)知道會(huì)匹配到哪一個(gè)數(shù)組下標(biāo)呢？所以，肯定是無(wú)序的。

步驟 3 作業(yè)1答案

public Object put(String key,Object value){
    if(size > capacity){
        enlarge();
    }
    //1\. 算出HashCode
    int hashCode = hash(key);
    //2\. 直接取模，得到余數(shù)，這個(gè)余數(shù)就是數(shù)組的下標(biāo)
    int index = indexForTable(hashCode);
    //3\. 將對(duì)應(yīng)的數(shù)據(jù)放入數(shù)組的對(duì)應(yīng)格子
    if(this.arr[index] == null){
        this.arr[index] = new LinkedList();
    }
    LinkedList linkedList = this.arr[index];
    if(linkedList.size() == 0){
        linkedList.add(key,value);
    }
    //遍歷這個(gè)node的鏈表，如果發(fā)現(xiàn)重復(fù)key，直接覆蓋
    Node firstNode = linkedList.firstNode;
    Node node = firstNode;
    while(node != null){
        if(node.key.equals(key)){
            node.data = value;
        }
        node = node.next;
    }
    this.size++;
    return value;
}

以上就是java編程進(jìn)階小白也能手寫(xiě)HashMap的詳細(xì)內(nèi)容，更多關(guān)于手寫(xiě)HashMap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論