//自定义一个HashMap
public class SxtHashMap<K,V> {

    Node2 [] table; //位桶数组。bucket array
    int size;       //存放键值对的个数
    public SxtHashMap(){
        table = new Node2[16];  //长度一般定义为2的整数次幂
    }

    public void put(K key,V value){
        Node2 newNode = new Node2();
        newNode.hash = myHash(key.hashCode(),table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next=null;

        boolean keyRepeat = false;
        Node2 temp = table[newNode.hash];
        Node2 iterLast = null;//存放正在遍历的元素
        if(temp == null){
            //元素数组为空，直接将新节点放进去
            table[newNode.hash] = newNode;
            size++;
        }else {
            //此处元素不为空，则遍历链表
            while (temp !=null){
                //判断key，如果重复，则覆盖
                if(temp.key.equals(key)){
                    temp.value = value;
                    keyRepeat = true;
                    break;
                }else {
                    //不重复，则temp=temp.next(遍历下一个)
                    iterLast = temp;
                    temp = temp.next;
                }
            }
            if (!keyRepeat){//如果没有发生重复，则添加到链表最后
                iterLast.next = newNode;
                size++;
            }
        }
    }

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


    public int myHash(int v, int length){
        return v&(length-1);
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("{");
        for (int i = 0; i < table.length; i++) {
            Node2 temp = table[i];
            while (temp!=null){
                stringBuilder.append("["+temp.key+":"+temp.value+"]"+",");
                temp = temp.next;
            }
        }
        stringBuilder.setCharAt(stringBuilder.length()-1,'}');
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        SxtHashMap <Integer,String>m = new SxtHashMap<>();
        m.put(1,"a");
        m.put(2,"b");
        m.put(3,"c");
        m.put(3,"123");
        for (int i = 0; i < 40; i++) {
            m.put(i,Character.toString((char) ('a'+i)));
        }
        m.put(23,"123");
        System.out.println(m);
        System.out.println(m.get(1));
    }

}

//用于SxtHashMap
public class Node2 <K,V>{

    int hash;
    K key;
    V value;
    Node2 next;

}