java实现自己的map

文章参考于https://blog.csdn.net/m0_37499059/article/details/80623438

package com.wpw.springbootmymap;

public interface MyMap {
    /**
     * 返回map集合大小
     * @return map集合大小
     */
    int size();

    /**
     * 判断map是否为空
     * @return true/false
     */
    boolean isEmpty();

    /**
     * 根据key获取value
     * @param key 键
     * @return 根据键返回的value
     */
    Object get(Object key);

    /**
     * 添加元素
     * @param key 键
     * @param value 值
     * @return 旧值
     */
    Object put(Object key,Object value);
    interface Entry<k,v>{
        /**
         * 获取key
         * @return 键
         */
        k getKey();

        /**
         * 获取值
         * @return 值
         */
        v getValue();
    }
}

package com.wpw.springbootmymap;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.experimental.Accessors;

import java.util.Set;

public class MyHashMap<K, V> implements MyMap {
    /**
     * 默认容量为16
     */
    private static final int DEFAULT_CAPACITY = 1 << 4;
    /**
     * 内部存储结构
     */
    Node[] table = new Node[DEFAULT_CAPACITY];
    /**
     * 长度
     */
    private int size;
    Set<K> keySet;

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    @Builder
    @Accessors(chain = true)
    static class Node implements MyMap.Entry {
        /**
         * hash值
         */
        int hash;
        /**
         * key
         */
        Object key;
        /**
         * value
         */
        Object value;
        /**
         * 指向下个节点（单链表）
         */
        Node next;

        @Override
        public Object getKey() {
            return this.key;
        }

        @Override
        public Object getValue() {
            return this.value;
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Object get(Object key) {
        int hashValue = hash(key);
        int i = indexFor(hashValue, table.length);
        for (Node node = table[i]; node != null; node = node.next) {
            if (node.key.equals(key) && hashValue == node.hash) {
                return node.value;
            }
        }
        return null;
    }

    /**
     * 获取hash值
     *
     * @param key
     * @return
     */
    public int hash(Object key) {
        return key.hashCode();
    }

    /**
     * 获取插入的位置
     *
     * @param hashValue
     * @param length
     * @return
     */
    private int indexFor(int hashValue, int length) {
        return hashValue % length;
    }

    @Override
    public Object put(Object key, Object value) {
        /**通过key获取hash值
         * */
        int hashValue = hash(key);
        /**通过hash找到这个key应该放的位置*/
        int i = indexFor(hashValue, table.length);
        for (Node node = table[i]; node != null; node = node.next) {
            Object k;
            if (node.hash == hashValue && ((k = node.key) == key || key.equals(k))) {
                Object oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        }
        /**
         * 如果i位置没有数据，或者i位置有数据但是key是新的key，新增节点
         */
        addEntry(key, value, hashValue, i);
        return null;
    }

    private void addEntry(Object key, Object value, int hashValue, int i) {
        /***
         * 如果超过了原数组大小，则扩大数组
         */
        if (++size == table.length) {
            Node[] newTable = new Node[table.length << 1];
            System.arraycopy(table, 0, newTable, 0, table.length);
            table = newTable;
        }
        Node eNode = table[i];
        /**新增节点，将该节点的next指向前一个节点*/
        table[i] = new Node(hashValue, key, value, eNode);
    }
}

package com.wpw.springbootmymap;

public class Test {
    public static void main(String[] args) {
        MyMap myMap=new MyHashMap<>();
        myMap.put("a",1);
        myMap.put("a",2);
        System.out.println(myMap.get("a"));
        System.out.println(myMap.isEmpty());
        System.out.println(myMap.size());
        System.out.println(myMap.put("a",3));
    }
}