HashMap学习--手动写一个简单的HashMap进行理解

1.结点Node的定义

public class Node {
    public int hash;
    public Object key;
    public Object value;
    public Node next;
}

HashMap的基础时一个数组，数组里每个元素是一个node，他必须包括:hash值，key键值，value，next下一个结点，同一个hash值的结点用一条链栓起来。

2.HashMap的定义

Node[] table;//核心数组
    int size;//元素个数
    
     public HashmapTest(){
        table=new Node[16];//初始化数组大小，尽量2的整数幂
        size=0;
    }

这个数组大小有讲究，从两个极端理解，当大小为1时，也就是所有的元素栓在一个位子上，也就是退化成了链表。如果数组很大，也就是元素所有元素几乎可以散在数组的每个位子上，也就是退化成了数组。至于取2的整数幂，可以将取余的操作使用按位&，加快速度，除法在计算机中的速度是很慢的。

3.HashMap的增删改查

增加一个元素

 public void put(K key,V value){
        Node newNode=new Node();
        Node lastNode=null;
        Boolean isRepeat=false;
        newNode.hash=myhash(key.hashCode(),table.length);//简单的计算hash值的函数，就是对数组大小进行取余，不考虑扩容以及优化
        newNode.key=key;
        newNode.value=value;
        newNode.next=null;
        if(table[newNode.hash]==null){
            table[newNode.hash]=newNode;
        }else{
            Node tmp=table[newNode.hash];
            while (tmp!=null){
                if(tmp.key.equals(key)){
                    isRepeat=true;
                    tmp.value=value;
                    break;
                }else{
                    lastNode=tmp;
                    tmp=tmp.next;
                }

            }
            if(isRepeat==false){
                lastNode.next=newNode;
            }

        }

    }

删除对应key值的元素

 public void delete(K key){
        int hash=myhash(key.hashCode(),table.length);
        Node temp=table[hash];
        Node prevNode=null;//记住前一个结点，删除时要接上。
        while(temp!=null){
            //第一个结点的特殊操作
            if(temp.key.equals(table[hash].key)){
                //第一个对上了
                if(temp.key.equals(key)){
                     table[hash]=temp.next;
                    break;
                }else{
                    prevNode=temp;
                    temp=temp.next;
                }
            }else{
                if(temp.key.equals(key)){
                    prevNode.next=temp.next;
                    break;
                }else{
                    temp=temp.next;
                }

            }
        }
    }

修改一个元素

public void set(K key,V value){
        Node temp=table[myhash(key.hashCode(),table.length)];
        while (temp!=null){
            if(temp.key.equals(key)){
                temp.value=value;
                break;
            }else {
                temp=temp.next;
            }
        }
    }

查找一个元素

 public V get(K key){
        int hash=myhash(key.hashCode(),table.length);
        Node tmp=table[hash];
        if(tmp==null){
            return null;
        }else{
            while (tmp!=null){
                if(tmp.key.equals(key)){
                    return (V)tmp.value;
                }else {
                    tmp=tmp.next;
                }
            }
            return null;
        }
    }