手写HashMap基础部分代码

package com.north.hashmap;

import java.util.Map;

/**
 * @Author North
 * @Date 2024/3/3
 * 手写HashMap
 */
@SuppressWarnings("all")
public class MyHashMap<K , V> {
    /**
     * 哈希表
     */
    private Node<K,V>[] table;

    /**
     * 键值对的个数
     */
    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        // 注意：new数组的时候，不能使用泛型。这样写是错误的：new Node<K,V>[16];
        this.table = new Node[16];
    }

    static class Node<K,V>{
        /**
         * key的hashCode()方法的返回值。
         * 哈希值,哈希码
         */
        int hash;
        /**
         * key
         */
        K key;
        /**
         * value
         */
        V value;
        /**
         * 下一个结点的内存地址
         */
        Node<K,V> next;

        /**
         * 构造一个结点对象
         * @param hash 哈希值
         * @param key 键
         * @param value 值
         * @param next 下一个结点地址
         */
        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString(){
            return "["+key+", "+value+"]";
        }
    }

    /**
     * 获取集合中的键值对的个数
     * @return 个数
     */
    public int size(){
        return size;
    }

    /**
     * 向MyHashMap集合中添加一个键值对。
     * @param key 键
     * @param value 值
     * @return value，如果key重复，则返回oldValue，如果key不重复，则返回newValue
     */
    public V put(K key, V value){
        /*
        【第一步】：处理key为null的情况
            如果添加键值对的key就是null，则将该键值对存储到table数组索引为0的位置。
        【第二步】：获得key对象的哈希值
            如果添加键值对的key不是null，则就调用key的hashcode()方法，获得key的哈希值。
        【第三步】：获得键值对的存储位置
            因为获得的哈希值在数组合法索引范围之外，因此我们就需要将获得的哈希值转化为[0，数组长度-1]范围的整数，
            那么可以通过取模法来实现，也就是通过“哈希值 % 数组长度”来获得索引位置（i）。
        【第四步】：将键值对添加到table数组中
            当table[i]返回结果为null时，则键键值对封装为Node对象并存入到table[i]的位置。
            当table[i]返回结果不为null时，则意味着table[i]存储的是单链表。我们首先遍历单链表，如果遍历出来节点的
            key和添加键值对的key相同，那么就执行覆盖操作；如果遍历出来节点的key和添加键值对的key都不同，则就将键键
            值对封装为Node对象并插入到单链表末尾。
         */
        if(key == null){
            return putForNullKey(value);
        }
        // 程序执行到此处说明key不是null
        // 获取哈希值
        int hash = key.hashCode();
        // 将哈希值转换成数组的下标
        int index = Math.abs(hash % table.length);
        // 取出下标index位置的Node
        Node<K,V> node = table[index];
        if(null == node){
            table[index] = new Node<>(hash, key, value, null);
            size++;
            return value;
        }
        // 有单向链表（遍历单向链表，尾插法）
        Node<K,V> prev = null;
        while(null != node){
            if(node.key.equals(key)){
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            prev = node;
            node = node.next;
        }
        prev.next = new Node<>(hash, 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;
        }
        // 程序可以执行到此处，说明下标为0的位置上有单向链表
        Node<K, V> prev = null;
        while(node != null){
            if(node.key == null){
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            prev = node;
            node = node.next;
        }
        prev.next = new Node<>(0, null,value,null);
        size++;
        return value;
    }

    /**
     * 通过key获取value
     * @param key 键
     * @return 值
     */
    public V get(K key){
        /*
        【第一步】：处理key为null的情况
        如果查询的key就是null，则就在table数组索引为0的位置去查询。
        【第二步】：获得key对象的哈希值
        如果查询的key不是null，则就调用key的hashcode()方法，获得key的哈希值。
        【第三步】：获得键值对的存储位置
        因为获得的哈希值在数组合法索引范围之外，因此我们就需要将获得的哈希值转化为[0，数组长度-1]范围的整数，
        那么可以通过取模法来实现，也就是通过“哈希值 % 数组长度”来获得索引位置（i）。
        【第四步】：遍历单链表，根据key获得value值
        如果table[i]返回的结果为null，则证明单链表不存在，那么返回null即可
        如果table[i]返回的结果不为null时，则证明单链表存在，那么就遍历整个单链表。如果遍历出来节点的key和查询
        的key相同，那么就返回遍历出来节点的value值；如果整个单链表遍历完毕，则遍历出来节点的key和查询的key都不
        相等，那么就证明查询key在链表中不存在，则直接返回null即可。
         */
        if(null == key){
            Node<K,V> node = table[0];
            if(null == node){
                return null;
            }
            // 程序执行到这里，数组下标为0的位置不是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 % table.length);
        Node<K,V> node = table[index];
        if(null == node){
            return null;
        }
        while(null != node){
            if(node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        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];
            // 如果node不是空，就遍历整个单向链表
            while(node != null){
                sb.append(node);
                node = node.next;
            }
        }
        return sb.toString();
    }
}