package com.jl.testmap;

/**

 *  自定义一个HashMap

 * @author JiangLai

 *

 */

public class MyHashMap<K,V> {

    Node<K,V>[] table;//位桶数组

    int size;//存放键值对的个数

    public MyHashMap() {

        table = new Node[16];//长度一般定义为2的整数次幂

    }

    public void put(K key,V value) {

        //定义新的节点对象

        Node newNode = new Node();

        newNode.hash = myHash(key.hashCode(), table.length);

        newNode.key = key;

        newNode.value = value;

        newNode.next = null;

        Node temp = table[newNode.hash];

        Node itorLast  = null;//正在遍历的最后一个元素

        if(temp==null) {

            //此处数组元素为空，则直接将新节点放入

            table[newNode.hash] = newNode;

            size++;

        }else {

            //此处数组元素 不为空，则遍历整个链表

            while (temp!=null) {

                //判断key是否重复，相同则替换，

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

                    temp.value = value;//只是覆盖value即可，其他的值不变。（hash，key，next）

                    break;

                }else {//如果不重复，则遍历下一个

                    itorLast = temp;

                    temp = temp.next;

                }

            }

            if(itorLast!=null) {

                itorLast.next = newNode;

                size++;

            }

        }

    }

    public V get(K key) {

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

        Object value = null;

        if(table[hash] != null) {

            Node<K,V> temp = table[hash];

            while (temp!=null) {

                if(temp.key.equals(key)) {//如果相等，则返回对应的值

                    value = temp.value;

                    break;

                }else {

                    temp = temp.next;

                }

            }

        }

        return (V)value;

    }

    //计算Hash值

    public int myHash(int v,int length) {

        //二者作用一样

//        System.out.println(v&(length-1));//直接位运算，效率高.

//        System.out.println(v%(length-1));//取余运算，效率低.

        return v&(length-1);

    }

    @Override

    public String toString() {

        //{10:aa,20:bb}

        StringBuilder sb = new StringBuilder("{");

        //遍历数组

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

            Node<K,V> temp = table[i];//当前元素

            //遍历链表

            while (temp!=null) {

                //当前元素的key和value

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

                //当前元素的下一个元素

                temp = temp.next;

            }

        }

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

        return sb.toString();

    }

    public static void main(String[] args) {

        MyHashMap<Integer,String> map01 = new MyHashMap<>();

        map01.put(10, "001");

        map01.put(20, "002");

        System.out.println(map01);

        System.out.println(map01.get(10));

    }

}

package com.jl.testmap;

/**

 * 用于TestHashMap中

 * @author JinagLai

 */

public class Node<K,V> {

     int hash;//HashCode

     K key;//键

     V value;//值

     Node<K,V> next;//下一个节点

}