快捷導(dǎo)航

基于Java快速實(shí)現(xiàn)一個(gè)簡單版的HashMap詳解

更新時(shí)間：2023年02月08日 08:32:35 作者：帝莘

這篇文章主要為大家詳細(xì)介紹了如何利用Java簡單實(shí)現(xiàn)一個(gè)底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組?+?鏈表的HashMap,不考慮鏈表長度超過8個(gè)時(shí)變?yōu)榧t黑樹的情況，需要的可以參考一下

1.示例圖

2.分析需求

put數(shù)據(jù)時(shí)：

key值hash后的索引處沒有元素，需要?jiǎng)?chuàng)建鏈表頭節(jié)點(diǎn)，放到該位置的數(shù)組空間里。
key值hash后的索引處有元素，說明產(chǎn)生Hash碰撞，需要在鏈表中結(jié)尾處掛載節(jié)點(diǎn)，如果在遍歷鏈表的過程中，發(fā)現(xiàn)了同key的數(shù)據(jù)，則執(zhí)行覆蓋即可，不再繼續(xù)往下遍歷去掛載新節(jié)點(diǎn)。
假設(shè)數(shù)組使用的空間超過了總長度的75%，那么對(duì)數(shù)組進(jìn)行擴(kuò)容。先創(chuàng)建新數(shù)組，把舊數(shù)據(jù)寫到新數(shù)組中(此時(shí)需要重新根據(jù)key計(jì)算Hash，因?yàn)閿?shù)據(jù)長度變化了，影響計(jì)算結(jié)果了)，在用新數(shù)據(jù)替換掉原來的舊數(shù)組。

get數(shù)據(jù)時(shí)：

key值hash后的索引下標(biāo)處的元素為空的話，則不存在數(shù)據(jù)。
key值hash后的索引下標(biāo)處存在鏈表的話，需要遍歷鏈表，找到key相對(duì)應(yīng)的value值。

3.代碼實(shí)現(xiàn)

Node類實(shí)現(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類實(shí)現(xiàn)

package com.zaevn.hashmap;

/**
 * @author: zae
 * @date: 2023/1/30
 * @time: 11:27
 */
public class ListNode {
    // 頭節(jié)點(diǎn)
    Node head;

    /**
     * 添加數(shù)據(jù)，掛載鏈表的節(jié)點(diǎn)
     * @param key
     * @param value
     */
    public void addNode(String key,String value){
        // 如果頭節(jié)點(diǎn)是空,則結(jié)束
        if(head == null ){return;}

        // 如果頭節(jié)點(diǎn)不為空，則往下掛載節(jié)點(diǎn)
        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類實(shí)現(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的個(gè)數(shù)
    int size;

    // 由于擴(kuò)容時(shí)是先創(chuàng)建一個(gè)新數(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("開始進(jìn)行擴(kuò)容，當(dāng)前size="+size+",數(shù)組長度為："+map.length);
            doExtendMap();
            System.out.println("擴(kuò)容結(jié)束，當(dāng)前size="+size+",數(shù)組長度為："+map.length);
        }

        // 1.對(duì)key進(jìn)行hash算法然后取模
        int index = Math.abs(key.hashCode())%map.length;

        ListNode listNode = map[index];
        // 如果索引位置的元素為空，則新加一個(gè)元素(創(chuàng)建頭節(jié)點(diǎn))
        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.對(duì)key進(jìn)行hash算法然后取模
        int index = Math.abs(key.hashCode())%map.length;

        if(map[index] == null){
            return null;
        }else{
            return map[index].getNode(key);
        }
    }

    /**
     * 達(dá)到閾值后開始進(jìn)行擴(kuò)容
     */
    public void doExtendMap(){
        sizeNew = 0;
        // 1.先創(chuàng)建一個(gè)新的數(shù)組，長度為原來的二倍
        mapNew = new ListNode[map.length * 2];

        // 2.將舊數(shù)據(jù)映射到新的數(shù)組上(因?yàn)閿?shù)組長度變化，因此hash規(guī)則變化，所有的值需要重新計(jì)算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、一般校驗(yàn)
        MyHashMap hashMap0=new MyHashMap();
        hashMap0.put("key1","value1");
        System.out.println("一般校驗(yàn)："+hashMap0.get("key1"));
        System.out.println("--------------------------------------------");


        // 2、同key覆蓋校驗(yàn)
        MyHashMap hashMap1=new MyHashMap();
        hashMap1.put("key2","value00");
        hashMap1.put("key2","value01");
        System.out.println("同key覆蓋校驗(yàn)："+hashMap1.get("key2"));
        System.out.println("--------------------------------------------");

        // 3、哈希碰撞校驗(yàn)(k1和k9的經(jīng)過哈希計(jì)算后得到的索引都是6)
        MyHashMap hashMap2=new MyHashMap();
        hashMap2.put("k1","value_k1");
        hashMap2.put("k9","value_k9");
        System.out.println("哈希碰撞校驗(yàn)：k1:"+hashMap2.get("k1")+"  k9:"+hashMap2.get("k9"));
        System.out.println("--------------------------------------------");


        // 4、擴(kuò)容校驗(yàn)
        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("擴(kuò)容后的c4:"+hashMap3.get("c4"));
        System.out.println("擴(kuò)容后的b3:"+hashMap3.get("b3"));
    }

}