掘金 后端 ( ) • 2024-03-06 11:23
💪手写mini-HashMap
mini 💪

引言

先来放一张图, 表示HashMap的内部的一些原理 HashMap.png

概述

在本节中，我们将深入研究手写的HashMap实现，名为MyHashMap。我们将逐步解释其结构和工作原理，并对关键方法进行讲解。 image.png ( 此图来自：https://pdai.tech/md/java/collection/java-map-HashMap&HashSet.html）

MyHashMap的基础知识

创建HashMap的基本结构

MyHashMap的核心结构是一个数组，数组中的每个元素是一个链表的头节点，用于存储哈希冲突的键值对。

javaCopy code
private Node<K, V>[] table;

哈希节点的定义

Node类用于表示链表节点，存储键、值、哈希码，以及指向下一个节点的引用。

static class Node<K, V> {
    int hash;
    K key;
    V value;
    Node next;
​
    // 构造方法和toString方法
}

put方法实现

image.png ( 此图来自：https://pdai.tech/md/java/collection/java-map-HashMap&HashSet.html） image.png

public V put(K key, V value) {
    // 处理key为null的情况
    if (key == null) {
        return putForNullKey(value);
    }
​
    // 计算哈希值并获取索引位置
    int index = Math.abs(key.hashCode()) % table.length;
    Node<K, V> node = table[index];
​
    // 如果对应位置上没有值
    if (null == table[index]) {
        table[index] = new Node<K, V>(key.hashCode(), key, value, null);
        size++;
        return value;
    }
​
    // 如果有链表
    Node<K, V> pre = node;
    while (node != null) {
        if (key.equals(node.key)) {
            // 如果键已存在，更新值并返回旧值
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        pre = node;
        node = node.next;
    }
​
    // 如果键不存在，将新节点添加到链表末尾
    pre.next = new Node<>(key.hashCode(), key, value, null);
    size++;
    return value;
}

在put方法中，我们首先处理了键为null的特殊情况，然后计算了键的哈希值，并根据取余操作找到对应的索引位置。接着，我们检查该位置是否已经有节点，如果没有，则直接创建新节点。如果已经有链表，我们遍历链表，查找是否存在相同的键，如果找到则更新其值，否则将新节点追加到链表末尾。

putForNullKey方法实现

private V putForNullKey(V value) {
Node<K, V> node = table[0];
if (node == null) {
    // 如果对应位置上没有值，创建新节点
    table[0] = new Node<>(0, null, value, null);
    size++;
    return value; // 返回新值
}
​
// 说明有单向链表
Node<K, V> pre = node;
while (node != null) {
    if (node.key == null) {
        // 如果键已存在，更新值并返回旧值
        V oldValue = node.value;
        node.value = value;
        return oldValue;
    }
    pre = node;
    node = node.next;
}
​
// 如果键不存在，将新节点添加到链表末尾
pre.next = new Node<K, V>(0, null, value, null);
return value;  // 返回新值
}

putForNullKey方法用于处理键为null的情况。与put方法类似，我们首先判断是否已经有节点，如果没有，则创建新节点。如果有链表，我们遍历链表，查找是否存在null键，如果找到则更新其值，否则将新节点追加到链表末尾。

get方法实现

image.png

public V get(K key) {
// key为null
if (null == key) {
    Node<K, V> node = table[0];
    if (node == null) {
        return null;
    }
​
    // 存在链表
    while (node != null) {
        if (null == node.key) {
            // 如果找到null键，返回对应的值
            return node.value;
        }
        node = node.next;
    }
}
​
// key不是null
int hash = key.hashCode();
int index = Math.abs(hash % 16);
Node<K, V> node = table[index];
​
// 遍历链表查找键值对
while (node != null) {
    if (node.key.equals(key)) {
        // 如果找到键，返回对应的值
        return node.value;
    }
    node = node.next;
}
​
// 不存在key
return null;
}

在get方法中，我们首先处理键为null的情况，遍历存储在索引0处的链表。如果键不为null，我们计算哈希值并获取索引位置，然后遍历对应的链表查找键值对。如果找到了相应的键，返回其对应的值，否则返回null。

重写toString方法

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < table.length; i++) {
        Node<K, V> node = table[i];
        while (node != null) {
            sb.append(node);
            node = node.next;
        }
    }
    return sb.toString();
}

toString方法用于输出MyHashMap的字符串表示形式。我们遍历数组中的每个链表，将节点的字符串表示逐个添加到StringBuilder中。

完整代码

​
public class MyHashMap<K, V> {
​
    private Node<K, V>[] table;
​
    private int size;
​
    public MyHashMap() {
        this.table = new Node[16];
    }
​
    static class Node<K, V> {
        int hash;
​
        K key;
​
        V value;
​
        Node next;
​
        @Override
        public String toString() {
            return new StringBuilder()
                    .append("[")
                    .append(key)
                    .append(",")
                    .append(value)
                    .append("]")
                    .toString();
        }
​
​
        public Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
​
​
        }
    }
​
    public V put(K key, V value) {
        // 处理key为null的情况
        if (key == null) {
            return putForNullKey(value);
        }
        // 不为null，取对应位置
        int index = Math.abs(key.hashCode()) % table.length;
        Node<K, V> node = table[index];
​
        // 如果对应位置上没有值
        if (null == table[index]) {
            table[index] = new Node<K, V>(key.hashCode(), key, value, null);
            size++;
            return value;
        }
        // 如果有链表
        Node<K, V> pre = node;
        while (node != null) {
            if (key.equals(node.key)) {
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            pre = node;
            node = node.next;
        }
        pre.next = new Node<>(key.hashCode(), key, value, null);
        size++;
        return value;
    }
​
    private V putForNullKey(V value) {
        Node<K, V> node = table[0];
        if (node == null) {
            table[0] = new Node<>(0, null, value, null);
            size++;
            return value; // 返回新值
        }
        // 说明有单向链表
        Node<K, V> pre = node;
        while (node != null) {
            if (node.key == null) {
                V oldValue = node.value;
                node.value = value; // 覆盖原有的值
                return oldValue;
            }
            pre = node;
            node = node.next;
        }
        // node为null后
        pre.next = new Node<K, V>(0, null, value, null);
        return value;  // 返回新值
    }
​
    /**
     * get方法
     */
    public V get(K key) {
        // key为null
        if (null == key) {
            Node<K, V> node = table[0];
            if (node == null) {
                return null;
            }
            // 存在链表
            while (node != null) {
                if (null == node.key) {
                    return node.value;
                }
                node = node.next;
            }
        }
        // key不是null
        int hash = key.hashCode();
        int index = Math.abs(hash % 16);
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        // 不存在key
        return null;
    }
​
    /**
     * 重写toString方法，输出map集合时会调用
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            while (node != null) {
                sb.append(node);
                node = node.next;
            }
        }
        return sb.toString();
    }
}

测试

iShot_2024-03-06_10.18.03.png

总结

在本节中，我们深入了解了MyHashMap的实现。我们介绍了其基本结构、put和get方法的实现，以及特殊情况下的处理。

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，其由 数组+链表+红黑树组成，我们目前只实现了数组+链表的结构。
相关内容
计划有变 12.9英寸iPad Air将不会采用mini LED显示屏
微软美股盘前涨0.42% | 微软美股盘前涨0.42%，公司此前宣布，推出小型AI模型Phi-3-mini。
早报|机构预测华为今年重回国内手机市场第一/美团 CEO 点评理想 L6/12.9 英寸 iPad Air 或搭载 mini-LED 屏幕
AI赋能语音转写，好看好写好轻薄的汉王N10 mini 2024
聚焦CCF科普工委 | “群星计划”四周年mini沙龙在苏州举行
苹果iPad mini 7今年亮相 优化“果冻屏”效应