自己实现简单的HashMap

自己实现简单的HashMap

自己实现一个底层时数组，数组里存链表，链表里存键值对的一个结构，key不能重复!

代码如下

接口类

package day1_17;



public interface MyMap {

    int size() ;

    boolean isEmpty();

    boolean containsKey(K key) ;

    V get(K key) ;

    void put(K key, V value) ;

    void remove(K key) ;

    void clear() ;

    void showMyHashMap();
}

实现类：

package day1_17;

import java.util.Map;



public class MyHashMap2 implements MyMap {
    //容器中元素的数量
    private int size;
    //数组的初始长度
    private int length = 10;
    //初始原始容器
    Node[] array = new Node[length];

    public MyHashMap2(){
        //每生成一个MyHashMap2就初始化array
        initArray();
    }
    //初始容器对象
    public void initArray(){
        for (int i = 0; i < length; i++) {
            array[i] = new Node<>();
        }
    }
    //判断容器中所装元素的大小
    @Override
    public int size() {
        return size;
    }
    //判断容器是否为空
    @Override
    public boolean isEmpty() {
        return size==0;
    }

    //判断容器中是否含有该key
    @Override
    public boolean containsKey(K key) {
        if(key==null){
            System.out.println("key不能为空!");
            return false;
        }
        //得到该keyhash值所对应的数组位置
        int index = key.hashCode() % length;
            Node node = array[index];
            //判断当前位置下是否有key存放
            while (node != null){
                //在判断该位置链表是否有该key
                if(node.getKey().equals(key)){
                    return true;
                }else {
                    //指向下一个
                    node = node.getNextNode();
                }
            }
        return false;
    }

    //获得对应key的value
    @Override
    public V get(K key) {
        if(key==null){
            System.out.println("key不能为空!");
            return null;
        }
        //得到key对应的数组下标
        int index = key.hashCode() % length;
        Node node = array[index];
        while (node != null){
            if(node.getKey().equals(key)){
                return node.getValue();
            }
        }
        return null;
    }

    //把key,value对放入容器
    @Override
    public void put(K key, V value) {
        if(key==null){
            System.out.println("key不能为空!");
            return;
        }
        //判断size是否超过容器初始容量的3/4,超过就触发扩容方法
        if(size > length * 3 / 4){
            length = length * 2;
            array = CapacityExpansion(array);
        }
        //得到key对应的数组下标
        int index = key.hashCode() % length;
        Node node = array[index];
        while (node.getKey()!=null){
            //判断链表中是否含有该key,如果有就把value覆盖
            if(node.getKey().equals(key)){
                node.setValue(value);
                return;
            }else {
                //向下走
                node = node.getNextNode();
            }
            //如果该链表中是不含有该key，直接把该key,value插入，其他往后移动
            //还原node
            node = array[index];
            Node kvNode = new Node<>(key,value);
            kvNode.setNextNode(node);
            array[index] = kvNode;
            size++;
        }
        //如果array[index]为空，直接把该key,value存入
        node.setKey(key);
        node.setValue(value);
        array[index] = node;
        size++;
    }

    //扩容方法
    private Node[] CapacityExpansion(Node[] oldArray){
        //生成两倍新数组
        Node []newArray = new Node[length];
        for (int j = 0; j < newArray.length; j++) {
            newArray[j] = new Node<>();
        }
        //遍历获得原来数组的key,value对重新存放
        for (int i = 0; i < oldArray.length; i++) {
            Node node = oldArray[i];
            while (node.getKey() != null){
                //获得新数组该对应的下标
                int index = node.getKey().hashCode() % newArray.length;
                Node newNode = newArray[index];
                if (newNode != null){
                    node.setNextNode(newNode);
                }
                    //如果该数组下标为null
                newArray[index] = node;
                //链表继续往下
                node = node.getNextNode();
            }
        }
        return newArray;
    }

    //删除对应的key对
    @Override
    public void remove(K key) {
        if(key==null){
            System.out.println("key不能为空!");
            return;
        }
        //得到key对应的数组下标
        int index = key.hashCode() % length;
        Node node = array[index];
        //如果当前我位置只有一对，直接给他置为null
        if(node==null){
            return ;
        }
        if(node.getNextNode()==null){
            array[index] = new Node<>();
            size--;
            return;
        }
        while (node.getKey() != null){
            //判断链表中是否含有该key,有就删掉
            if(node.getKey().equals(key)){
                //把当前要删的key所对应的key,value替换为下一位的
                node.setKey(node.getNextNode().getKey());
                node.setValue(node.getNextNode().getValue());
                node.setNextNode(node.getNextNode().getNextNode());
                size--;
                return;
            }
                node = node.getNextNode();
        }
        System.out.println("没有该key");
    }

    //清空容器
    @Override
    public void clear() {
        for (int i = 0; i < length; i++) {
            array[i] = null;
        }
        size=0;
    }

    //显示容器中的键值对
    @Override
    public void showMyHashMap() {
        for (int i = 0; i < length; i++) {
            Node node = array[i];
            while (node != null) {
                if(node.getKey()!=null) {
                    System.out.println("key:" + node.getKey() + ";value:" + node.getValue());
                }
                node = node.getNextNode();
            }
        }
    }
}

链表类

package day1_17;



public class Node {
    private K key;//key值
    private V value;//value值
    private Node nextNode;//下一个节点
    public Node(){

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

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }
    
}

注意这里加了toString方法会发生栈溢出！