自定义hashMap

public class MyHashMap<K,V> {
    //map的底层就是node数组，每个元素都是node，如果这个元素位置有hash冲突，则这个node变为链表
    private Node<K,V>[] table;
    /**
     * 数组的初始大小
     */
    private final int DEFAULT_INITIAL_CAPACITY=1<<4;//16  每次扩容就左移一位就行了

    private int size=0;//表示table中实际存的元素个数

    /**
     * 负载因子：减少生成链表的机会，因为table一旦存满则必会增加生成链表的机会
     * 所以在table还没有存满时就要扩容
     */
    private static final float DEFAULT_FACTOR=0.75f;
    /**
     * 阈值:  数据容量✖负载因子
     */
    private int threshold;

    public MyHashMap(){
        this.table = new Node[DEFAULT_INITIAL_CAPACITY];
        threshold = (int) (table.length*DEFAULT_FACTOR);
    }

    public int size(){
        return this.size;
    }


    /**
     * 根据键取值
     */
    public V get(K k){
        //1.根据k得到数组下标
        int index = index(table.length, k);
        //2.根据下标取Node
        Node<K, V> node = table[index];
        //3.Node == null,说明map中没有这个key，返回null
        if (node==null){
            return null;
        }
        //4.Node != null
        //  (1)这个Node的next为空，说明这不是链表，只是唯一的一个节点，直接取这个节点的v返回
        if ( node.getNext() ==null ){
            return node.getV();
        }
        //  (2)这个Node中next不为空，说明这是个链表(这个链表中的node的k不同，但是生成的hash值相同
                    //循环这个链表，比较每个node中的k是不是我要的这个k
        else {
            Node<K,V> next = node.next;
            while (next!=null){
                if (node.getK().equals(k)){
                    return node.getV();
                }
                next=next.next;
            }
        }
        return null;
    }

    public void put(K k,V v){
        //1.先计算k的索引
        int index = index(table.length, k);
        //2.取出这个索引位置的node
        Node<K, V> node = table[index];
        //3.判断node==null?
        //true表示没有冲突，直接存进数组
        if (node==null){
            table[index] = new Node<>(hash(k),k,v,null);
            size++;
            return;
        }
        //false冲突
        //k与node的k相同，则要覆盖v
        if (node.getK().equals(k)){
            node.setV(v);
            return;
        }
        //如果k不同，则表示只是hash相同，hash冲突，按链表存进去
        Node<K,V> newNode = new Node<>();
        newNode.setV(v);
        newNode.setK(k);
        newNode.setNext(node);
        table[index] = newNode;
        size++;
        System.out.println("元素个数："+size+",负载阈值："+threshold+",node数组的容量："+table.length);
        if (size>threshold){
            resize();   //扩容，这个数组，要将数组中的数据移到新数组中
        }
    }

    private void resize(){
        //容量为2的幂次
        Node[] tableOle = table;
        Node[] tableNew = new Node[tableOle.length<<1];
        for (int i = 0; i < tableOle.length; i++) {
            if (tableOle[i]!=null){
                //原来结点的hash值对新数组计算一次下标
                int newIndex = index(tableNew.length, tableOle[i].hash);
                tableNew[newIndex] = tableOle[i];
            }
        }
        table = tableNew;
        threshold = (int) (tableNew.length*DEFAULT_FACTOR);
    }

    /**
     *  利用hash()来完成对key生成hashcode的操作
     *  Object中原有hashCode()已经生成了hash值。哈希碰撞几率更高
     *  解决方案：1.先用key.hashCode()  2.hashcode()是32位整数，将高16位和低16位混洗
     */
    static final int hash(Object key){
        int h = key.hashCode();
        return (key == null) ? 0 : (h ^ (h >> 16));
    }

    /**
     *  计算Node[]数组中的索引
     *  n:表示Node[]数组的长度，通常是2的幂   -1之后的二进制全为1
     */
    static int index(int n,Object key){
        //hash(key)%n;
        return (n-1)&hash(key); //等同于求余数，此余数是key再数组中的索引
    }

    class Node<K,V>{
        int hash;   //此node计算出来的哈希值
        K k;        //键
        V v;        //值
        Node<K,V> next; //哈希冲突情况下，生成链表则next指向下一个元素，没有就是null

        public Node() {
        }

        public Node(int hash, K k, V v, Node<K, V> next) {
            this.hash = hash;
            this.k = k;
            this.v = v;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "hash=" + hash +
                    ", k=" + k +
                    ", v=" + v +
                    ", next=" + next +
                    '}';
        }

        public int getHash() {
            return hash;
        }

        public void setHash(int hash) {
            this.hash = hash;
        }

        public K getK() {
            return k;
        }

        public void setK(K k) {
            this.k = k;
        }

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }

        public Node<K, V> getNext() {
            return next;
        }

        public void setNext(Node<K, V> next) {
            this.next = next;
        }
    }
}