手写HashMap

1.定义HashMap的存储单元Node

class Node<K,V>{
    final K key;
    V value;
    Node<K, V> next;
    Node(K key, V value){
        this.key = key;
        this.value = value;
    }
}

2.构造器初始化和默认参数

//定义一个默认的初始容量
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
//构造参数
private Node<K,V>[] table;//哈希表
private int size; //当前哈希表中元素个数
private int capacity; //当前哈希表的容量
//构造函数
public SimpleHashMap(){
    this.capacity = DEFAULT_CAPACITY;
    this.table = new Node[capacity];
    this.size = 0;
}

3.计算索引

private int hash(K key){
    return key==null?0:Objects.hashCode(key) & (capacity-1);
}

4.插入/更新put

public void put(K key, V value){
    int hash = hash(key);
    Node<K,V> node = table[hash];
    while(node!=null){
        if(Objects.equals(node.key, key)){
            //如果找到key，更新值
            node.value = value;
            return;
        }
        node = node.next;
    }
    //否则，将新的节点插入链表头
    Node<K,V> newNode = new Node<>(key,value);
    //头插法
    newNode.next = table[hash];
    table[hash] = newNode;
    size++;
    //插入元素后，判断是否需要扩容
    if(size>=capacity * LOAD_FACTOR){
        resize();
    }
}

5.获取get

public V get(K key){
    int hash = hash(key);
    Node<K,V> node = table[hash];
    //遍历链表，寻找key
    while(node!=null){
        if(Objects.equals(node.key, key)){
            //返回找到的值
            return node.value;
        }
        //如果没有找到，返回null
        node = node.next;
    }
    return null;
}

6.删除remove

public V remove(K key){
    int hash = hash(key);
    Node<K,V> node = table[hash];
    Node<K,V> prev = null;
    //遍历链表，找到要删除的节点
    while(node!=null){
        if(Objects.equals(node.key, key)){
            if(prev==null){
                //如果要删除的节点是头节点
                table[hash] = node.next;
            }else{
                prev.next = node.next;
            }
            size--;
            return node.value;
        }
        prev = node;
        node = node.next;
    }
    return null;
}

7.扩展哈希表的容量resize

public void resize(){
    capacity = capacity * 2;
    Node<K,V>[] newTable = new Node[capacity];
    for(Node<K,V>node:table){
        while(node!=null){
            Node<K,V> next = node.next;
            int hash = Objects.hashCode(node.key)&(capacity-1);
            node.next=newTable[hash];
            newTable[hash] = node;
            node = next;
        }
    }
    table = newTable;
}

8.完整代码

import java.util.Objects;

class SimpleHashMap<K, V> {

    // 定义一个默认的初始容量
    private static final int DEFAULT_CAPACITY = 16;
    // 定义装载因子，用于扩展哈希表的大小
    private static final float LOAD_FACTOR = 0.75f;
    
    // 哈希表中的节点类
    class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node<K, V>[] table; // 哈希表
    private int size;           // 当前哈希表中元素个数
    private int capacity;       // 当前哈希表的容量

    // 构造函数
    public SimpleHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        this.table = new Node[capacity];
        this.size = 0;
    }

    // 获取哈希值
    private int hash(K key) {
        return key == null ? 0 : Objects.hashCode(key) & (capacity - 1);
    }

    // 插入或更新key-value对
    public void put(K key, V value) {
        int hash = hash(key);
        Node<K, V> node = table[hash];
        // 遍历链表，检查是否已经存在该key
        while (node != null) {
            if (Objects.equals(node.key, key)) {
                node.value = value; // 如果找到key，更新值
                return;
            }
            node = node.next;
        }
        // 否则，将新节点插入链表头
        Node<K, V> newNode = new Node<>(key, value);
        newNode.next = table[hash];
        table[hash] = newNode;
        size++;

        // 检查是否需要扩容
        if (size >= capacity * LOAD_FACTOR) {
            resize();
        }
    }

    // 获取key对应的value
    public V get(K key) {
        int hash = hash(key);
        Node<K, V> node = table[hash];
        // 遍历链表，寻找key
        while (node != null) {
            if (Objects.equals(node.key, key)) {
                return node.value; // 返回找到的值
            }
            node = node.next;
        }
        return null; // 如果未找到，返回null
    }

    // 删除key对应的节点
    public V remove(K key) {
        int hash = hash(key);
        Node<K, V> node = table[hash];
        Node<K, V> prev = null;

        // 遍历链表，寻找要删除的节点
        while (node != null) {
            if (Objects.equals(node.key, key)) {
                if (prev == null) {
                    // 如果要删除的是链表头节点
                    table[hash] = node.next;
                } else {
                    prev.next = node.next;
                }
                size--;
                return node.value; // 返回被删除的值
            }
            prev = node;
            node = node.next;
        }
        return null; // 未找到返回null
    }

    // 扩展哈希表的容量
    private void resize() {
        capacity = capacity * 2;
        Node<K, V>[] newTable = new Node[capacity];

        // 重新散列所有元素到新表
        for (Node<K, V> node : table) {
            while (node != null) {
                Node<K, V> next = node.next;
                int hash = Objects.hashCode(node.key) & (capacity - 1);
                node.next = newTable[hash];
                newTable[hash] = node;
                node = next;
            }
        }
        table = newTable;
    }

    // 获取当前哈希表中的元素个数
    public int size() {
        return size;
    }

    // 检查哈希表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        SimpleHashMap<String, Integer> map = new SimpleHashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        System.out.println("Get 'two': " + map.get("two"));  // 输出 2
        System.out.println("Remove 'two': " + map.remove("two")); // 删除并输出 2
        System.out.println("Get 'two' after removal: " + map.get("two")); // 输出 null

        System.out.println("Map size: " + map.size()); // 输出 2
    }
}