Java容器之自定义HashMap

前言

小菜模仿JDK1.7版本HashMap简单自己实现了代码，在jdk1.8以上是使用数组加红黑树的方式实现HashMap，而在jdk1.7是使用数组加链表实现。下图表示jdk1.7存储结构。

实现

定义node节点：

package hashmap;

//定义节点

public class Node<K,V> {

    //hash值

    int hash;

    //键

    K key;

    //值

    V value;

    //下一个节点

    Node next;

}

实现HashMap：

package hashmap;

public class NewHashMap<K,V> {

    //定义位桶数组

    Node[] table;

    //有效键值对个数

    int size;

    public NewHashMap(){

        //位运算需求此处长度数为2的整数次幂

        table=new Node[16];

    }

    //put操作

    public void put(K key,V value){

        //定义节点

        Node node=new Node();

        node.hash=hash(key.hashCode(),table.length);

        node.key=key;

        node.value=value;

        node.next=null;

        //放入位桶数组

        Node temp=table[node.hash];

        Node iterlast=null;

        boolean keyRepeat=false;

        if(temp==null){

            //此处数组值为空

            table[node.hash]=node;

            keyRepeat=true;size++;

        }else{

          //数组中有值

            while(temp!=null){

                //如果key不重复放入链表之后

                //如果key重复，覆盖

                if(temp.key.equals(key)){

                    temp.value=value;

                }else{

                    iterlast=temp;

                    temp=temp.next;

                }

            }

        }

        if(!keyRepeat) {

            iterlast.next = node;

            size++;

        }

    }

    //对hash值做处理

    public int hash(int v,int length){

        return v&(length-1);//相似于取余运算

    }

    //get

    public V get(K key){

        int hash=hash(key.hashCode(),table.length);

        V value=null;

        //遍历数组中链表找到值

        if(table[hash]!=null){

            Node temp=table[hash];

            while(temp!=null){

                if(temp.key.equals(key)){

                    value=(V)temp.value;

                    break;

                }else {

                    temp=temp.next;

                }

            }

        }

        return value;

    }

    //重写toString

    public String toString(){

        StringBuilder sb=new StringBuilder("{");

        for(int i=0;i<table.length;i++){

            Node temp=table[i];

            while(temp!=null){

                sb.append(temp.key+";"+temp.value+",");

                temp=temp.next;

            }

        }

        sb.setCharAt(sb.length()-1,']');

        return sb.toString();

    }

    public static void main(String[] args) {

        NewHashMap<Integer,String> hashMap= new NewHashMap<>();

        hashMap.put(53,"1");

        hashMap.put(69,"2");

        hashMap.put(85,"3");

        hashMap.put(2,"a");

        System.out.println(hashMap);

        System.out.println(hashMap.get(53));

    }

}

本人很菜，请多指教。