介绍

HashMap是一个存储键值对的一个数据结构，它集合了数组、链表和红黑树等多种数据结构。HashMap常用的就是get和put两种操作。
下面是一个miniHashMap的实现，先对于HashMap有一个基本的结构认识，再去研究JDK1.7和1.8HashMap的源码。

初始化

HashMap初始化时，需要两个重要的参数initialCapacity容量和loadFactroy负载因子。在初始化HashMap时，建议设置initialCapacity，防止因为map容量太大，造成多次rehash(扩容)而影响性能。
默认加载因子为0.75，这是在时间和空间成本上寻求一种折衷。

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认容量16
    static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
    //容量
    private int initialCapacity;

    //负载因子
    private float loadFactor;

    //元素表
    private Node[] table;
    //元素数量
    private int size;

    public MyHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("初始化容量异常");
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("初始化加载因子异常");
        }
        this.initialCapacity = initialCapacity;
        this.loadFactor = loadFactor;
        table = new Node[initialCapacity];
    }

Node节点

Node节点是HashMap中存储数据一个节点，它被实现成一个Node对象，并存放于数组中。

class Node {
        private int hash;//哈希码
        private K key;
        private V value;
        private Node next;//下一个哈希重合的对象

        public Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }


        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

hash函数

hash函数也称为扰动函数。在初始化时我们生成了一个元素表用于存放Node节点的一个table。通过计算key的值最大可能的均匀把Node节点分配到table上，为了尽大可能的分散元素，必须用到这个hash函数

private int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

key.hashCode产生的是一个-2³²到2³²范围中的一个数，通过与自己无符号右移异或，产生一个扰动的参数。

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

put方法

put方法实质就是通过key值，进行hash计算出数组下标，并对该数组下标的元素进行判断，插入或者更新value值。注意的是这里出现位置冲突时，使用了头插法。

 public V put(K k, V v) {
        V oldValue = null;
        if (size >= initialCapacity * loadFactor) {//默认超过容量的75%，扩容
            resize();
        }
        int hashcode = hash(k);//通过hash函数得到的扰乱值
        int index = hashcode & (initialCapacity - 1); //计算该元素在数组的位置
        if (table[index] == null) {//如果节点为空，插入数据
            table[index] = new Node<>(hashcode, k, v, null);
            size++;
        } else {
            Node nextNode = table[index];//获取该节点的数据
            while (nextNode != null) {//通过循环判断是否是最后一个节点
                if (nextNode.hash == hashcode && (k == nextNode.getKey()) || k.equals(nextNode.getKey())) {//如果hashcode和equals全部相等，覆盖这个值
                    oldValue = nextNode.getValue();
                    nextNode.value = v;
                    return oldValue;//返回修改后的值
                }
                nextNode = nextNode.next;//如果不相等继续循环
            }
	    //如果插入的节点不在数组中，但是index相等，直接插入原有节点的子节点中
            //头插法，最后进的元素在头部
            table[index].next = new Node<>(hashcode, k, v, nextNode);
            size++;
        }
        return oldValue;
    }

get方法

get方法实质是通过计算key值在元素表中的位置，获取value值。
当出现位置冲突时，使用key的hashcode数组和equals方法进行验证。

 public V get(K k) {
        int hashCode = hash(k);
        int index = hash(k) & (initialCapacity - 1);//获取数组下标
        if (table[index] == null) {
            return null;
        } else {
            Node node = table[index];
            while (node != null) {
		//查找到hashcode或者是key值相等的节点
                if (node.hash == hashCode && (k == node.getKey() || k.equals(node.getKey()))) {
                    return node.value;
                } else {
                    node = node.next;
                }
            }
        }
        return null;
    }

扩容方法

新生成一个长度为原来的2倍的元素表和一个能存储所有元素的链表。
并再用put方法，把链表中的元素重新put到新的元素表。
这里的扩容方法时间复杂度为n^2，

 private void resize() {
	//产生新的元素表，长度为原来的2倍
        int newSize = initialCapacity << 1;
        Node[] newTable = new Node[newSize];
        initialCapacity = newSize;
	//进行扩容
        reHash(newTable);
    }

    private void reHash(Node[] newTable) {
	//生成一个链表
        List> entryList = new ArrayList<>();
        for (Node node : table) {
	    //对旧元素表的元素进行读取
            if (node != null) {
                entryList.add(node);
                while (node.next != null) {
                    entryList.add(node.next);
                    node = node.next;
                }
            }
        }
        table = newTable;
        size = 0;
        for (Node node : entryList) {
	    //重新进行put操作
            put(node.getKey(), node.getValue());
        }
    }

关于hashcode和equals方法

hashCode主要用于提升查询效率提高哈希表性能，来确定在散列结构中对象的存储地址
重写equals()必须重写hashCode()
哈希存储结构中，添加元素重复性校验的标准就是先检查hashCode值，后判断equals()
两个对象equals()相等，hashcode()必定相等
两个对象hashcode()不等，equals()必定也不等
两个对象hashcode()相等，对象不一定相等，需要通过equals()进一步判断。

如果传入HashMap一个自定义对象作为key值，必须要重写该对象的hashcode和equals方法，并且符合上面的规则。

为什么hashmap推荐使用String作为key?
因为String对象hashcode和equals方法完全符合上面的规则。
而且，String中缓存有个hash变量，它可以缓存hashCode，避免重复计算hashCode。例如，你有一个 student1对象作为map的key值，你第二次使用student1作为key值放入map中时，会再次计算student1的hashCode。

总结

实现hashmap最重要的是减少元素冲突，在JDK源码中，可以看到用到了大量的位运算，目的就是提高性能。使用hashmap的时候必须初始化容量和重写key对象的hashcode和equals方法。本次手写的miniHashMap仅实现了主要的功能，在线程安全方面和数据性能方面有明显的不足。