结构分析

hashMap在jdk1.7的时候是单纯的链表加数组的结构，那为什么要用链表加数组的结构来组成hashMap呢？这跟效率有关系。

数组的优缺点

1.优点：数组是一个内存连续的空间，直接可以用数组下标来访问数组中的某个值，时间复杂度是1。
2.缺点：数组在插入或者扩容的时候效率低下，因为数组在创建的时候需要把长度固定下来，一旦需要插入或者扩容就需要复制元素往后移动，产生了很多其他操作。
展开：容器API中的实现是ArrayList，就是用数组实现的容器，扩容时会扩大1.5倍。
生产过程中主要对于对应位置插入不频繁，创建之前能够直接确定大小的，不存在扩容的时候最适合使用。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 原大小加上原大小的一半就是扩大1.5倍，>> 这个符号是位运算符，右移一位表示除2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 得到新的数组大小后，会将原数组元素复制到新的数组原素中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

链表的优缺点

1.优点：可以不用连续的空间存储，物理上不连续，逻辑上连续，C节点将插入AB节点两个位置当中时只需要将A指向B的next指向C，再将C的next指向B，这样一个节点就能插入成功，不像数组那样还需要移动元素和扩容
2.缺点：在访问某个对象时需要遍历之前的元素才能找到该值，在新增元素的时候需要循环遍历至尾节点才能做插入操作，如果元素过多，遍历时间会过长，导致效率低下，但是可以通过双链表的形式来化解这个问题，这个做法就是空间换时间的典型，双链表会有双指针，空间会占用更多，但是找到插入的地方也会更快。
生产环境中对于插入操作频繁，较少存在读取值的时候适合
容器API实现的双链表结构是LinkedList，里面用一个静态内部类Node节点来存储对象，每次调用一次add方法都会新生成一个Node对象。

private static class Node<E> {
        E item;//存放的对象
        Node<E> next;//后驱指针
        Node<E> prev;//前驱指针

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

数组和链表的结合

HashMap通过数组和链表的结合来提高存放对象和获取的对象的效率。
数组的体现：HashMap通过属性table来存储数组对象

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     * 英文的大致意思是创建HashMap时不会默认初始话该属性，是一个懒加载，
     * 使用HashMap的时候才会初始化该属性，而该属性的大小可能是0，除了0
     * 以外都是2^n(2的n次幂)，有很多同学会有疑问为什么一定要2^n，其实都是
     * 为了一个，就是效率，2^n最大的好处就是可以与位运算结合来运算，位运算
     * 在计算机中速度最快。
     * K表示的是key，用hashCode计算得出
     * V表示的是存入的对象
     */
    transient ![Node<K,V>\[\] table](https://img-blog.csdnimg.cn/20201123150517435.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDg2Nzcy,size_16,color_FFFFFF,t_70#pic_center)
;

链表的体现：每一个table中的Node对象都是一条链表的体现，并且都是头节点

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
          在这里插入图片描述
      return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

下面是自己画的一个简图
在这里插入图片描述

1.7 与 1.8 的改进

1.7时HashMap使用的纯数组加链表的结构，而1.8中做了优化，链表长度在超过TREEIFY_THRESHOLD属性值时链表的结构会变为红黑树的结构，TREEIFY_THRESHOLD指的是链表达到一定长度时转还为红黑树的阈值，默认为8，因为在链表过长时效率很低，使用红黑树可以提升存放和获取对象的效率。
还有一个改动是插入对象的时候1.7采用的是头插法，1.8使用的是尾插法。这是在使用1.7jdk的使用者大量在java社区反应的，后来官方在1.8的时候修改了这个bug。使用者发现程序在运行时经常cpu100%占用，使用java工具发现程序一直运行在hashMap的某一个方法中，并且无法结束。导致这样的问题是因为node节点以链表构成的结构出现环形链表，导致在获取下一个元素时永远会在环形链表中，只有当node节点的next属性为空时才会停下，所以cpu才会100%占用。
导致环形链表的原因是头插法并且在多线程的环境中触发，一开始业务逻辑并不会存在多线程，并且HashMap本身就是线程不安全的，之后因为业务逻辑升级，存在了多线程的情况，就会导致这个问题。多线程时需要使用CurrentHashMap，使用的是分段锁，可以保证线程安全。1.8时官方将尾插法替代了1.7的头插法，修复了此bug，在多线程环境中不会再有环形链表的问题。

为什么HashMap的属性table数组的大小一定是2^n?

看完源码自己认为最重要的原因就是通过位运算提高存取对象的效率。

HashMap中位运算的应用

HashMap的源码看完真的会感叹什么才是真正的鬼才？

1.HashMap的初始化。

一般我们创建HashMap的时候不会传入大小，如果不传入的话默认的大小为16(2^4)；
看以下源码如果我们传入一个数字，就会重载调用第二个构造方法，然后对于一些特殊值进行判断，小于0或者大于MAXIMUM_CAPACITY（1 << 30，很大的一个数字，一般的业务逻辑肯定不会超过这个数字），最后构造器会进入tableSizeFor方法来获取table的长度。
tableSizeFor这个方法很有意思，这个方法的返回值必然是大于或者等于该值最小的2^ n的数。大概在做的事情就是将传入的值每次位运算向右移动2^n,n从0开始，n依次增加，一共移动31次，为毛移动31次，因为传入的是int值，总共就只有32位，并且第一位是符号位，负数为1，正数为0，这又跟原码反码补码的知识扯上了，不懂的同学可以查查相关的知识。
这样做的目的就是让最高位为1以后的所有低位都变为1，不明白的同学可以试着算一下，最后你会得到一个全是1的一个二进制数字，而这样的数字必等于2^n-1。
两个细节的地方：
（1）.刚进tableSizeFor这个方法时，会先减去1，再进行运算，这样的目的主要是为了当传入的值刚好为2^n，如果没有减1操作，就会导致方法出错。比如说传入16时，16的二进制是10000，最后会得出11111这个二进制，十进制就是31，最后会加1操作变为32，比原来大了一倍，所以需要减1操作。
（2）.算出值的最后会加1操作，因为最后算出的是2^n-1的一个数字，所以最后要加1操作才能得到正确的值

public HashMap(int initialCapacity) {
		//重载去调用对应参数的构造方法
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

/**
*initialCapacity 初始化大小 默认16
*loadFactor加载因子 默认0.75
*/
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

2.求hashCode值

当需要往HashMap中放入对象的时候，会通过传入的key得到相应的hashCode方法，调用的是Object的hashCode方法，最后会调用native的hashCode的底层算法。其中有(h = key.hashCode()) ^ (h >>> 16)这样一段代码，官方为了照顾开发者自己重写的hashCode很简单，不具有散列性，所以这里帮你的hashCode值进行强行散列，得到hashCode后再与hashCode的高16位进行位的异或运算，这样做的目的是为了hashMap存放值的时候更加散列，更加随机，而异或运算是最趋向去随机的位运算，且运算和或运算都会使值趋向0或1，并且用高16位来运算，所以采用异或运算来增强散，这个跟我们平常说的搅屎棍差不多意思，哈哈哈哈。

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

4.取模运算

在上一步求出散列的hashCode值后，如果hashMap未初始化，就会在putVal中初始化。初始化完成后会进行取模运算，p = tab[i = (n - 1) & hash]这段代码就是取模运算，这个运算的最终含义就是容量大小的减去1的值与hashCode进行且运算，得到容量大小减1的二进制长度相当的hashCode的低位，这样说有点太抽象了，举个例子：比如说当前hashMap的table数组的长度为16，那么减1之后的二进制就是1111，与hashCode进行且运算，只会得到hashCode的低4位，不会有其他值。这样就完成了取模运算，这个值永远小于16，就是放入桶table的下标值。
补充：在hashMap扩容的时候，也会用这样的操作重新放置对象，只是细节方法实现略有不同。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

hashMap中位运算的总结：总的来说用位运算速度最快，所以hashMap中的值都多多少少跟2^n有关，都是为了去满足位运算，充分发挥位运算的速度。

hashMap的扩容

loadFactor属性，默认值0.75，指的如果当前table数组（默认数组长度为16）中头节点已沾满75%，也就是12个值，这时候会去检查是否扩容。因为如果发现求出的table数组下标不存在node时，就不会触发扩容，只有当满足table数组的头节点超过75%，并且table数组下标已经存在头节点时，才会触发扩容。