HashMap详解

一、HashMap

hashmap在元素size超过负载因子对应数的时候就会扩容，但是其实还有一种情况也会扩容，那就是链表上Node数量大于等于8且tab数组长度小于64的时候的时候。
HashMap的结构是哈希表，底层维护了一个Node数组(Jdk 8之后，之前是HashMap.Entry数组)，它是集合框架里非常常用的集合类，和ArrayList一样，使用非常频繁，HashMap的初始容量是16，加载因子是0.75，当在一个位桶发生哈希冲突(也叫哈希碰撞)的时候，添加的元素会依次存放在该位置的最后一个元素后面(形成链表)，链表数量大于8且HashMap元素大小小于64时，这条链表就会转成就会转成红黑树，注意一定两个条件都满足才会转成红黑树，不要忽略了64这个数，平时很多博客说链表大于8就转红黑树大概是因为在工程上链表大于8了基本上HashMap存储的元素大于64，否则说明这个HashMap的hash函数设计的不好，基本上算出来的值都是同一个，也就是说产生了哈希碰撞。而实际上HashMap的hash函数是已经高度优化了的，所以某条链表节点数大于8而总节点数小于64发生的概率极低，当然要知道这个逻辑。

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;
}

1.1 treeifyBin方法

如图所示，TREEIFY_THRESHOLD值是8，它的意思是超过一条链上的Node数量大于等于8就会转成红黑树来存储元素而不是链表，然后会执行treeifyBin(tab, hash);方法，我们看看这个方法的实现：

/**
    * Replaces all linked nodes in bin at index for given hash unless
    * table is too small, in which case resizes instead.
    */
   final void treeifyBin(Node<K,V>[] tab, int hash) {
       int n, index; Node<K,V> e;
       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
           resize();
       else if ((e = tab[index = (n - 1) & hash]) != null) {
           TreeNode<K,V> hd = null, tl = null;
           do {
               TreeNode<K,V> p = replacementTreeNode(e, null);
               if (tl == null)
                   hd = p;
               else {
                   p.prev = tl;
                   tl.next = p;
               }
               tl = p;
           } while ((e = e.next) != null);
           if ((tab[index] = hd) != null)
               hd.treeify(tab);
       }
   }

看注释，意思大概就是，把链表转换为红黑树，除非数组太小，在hashmap的实现里，是table小于64时，不转为红黑树。MIN_TREEIFY_CAPACITY是最小转为红黑树的tab大小，是64，如果满足这个条件同时链表长度大于8就执行resize()方法对数组进行扩容。

HashMap是容器类，存储的是键值对，jdk 1.8之前底层是数组和链表结合在一起使用也就是链表散列。HashMap通过key的 hashCode 经过扰动函数处理后得到hash值，然后通过(n - 1) & hash判断当前元素存放的位置(n是数组的长度，HashMap默认为16，加载因子是0.75)，如果当前位置存在元素，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不同就通过拉链法解决冲突。put()方法相关源码如下：

1.2 putVal方法

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()/*resize方法生成一个指定容量大小的Node数组*/).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//1,tab[i]位置没有node对象，就直接把元素放在此位置
            tab[i] = newNode(hash, key, value, null);
        else {//2，不为空的情况下，在这里判断是否覆盖还是通过拉链法放到别处(判断是同一个对象就覆盖)
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//3,
                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;
}

1.3 扰动函数

是HashMap的hash方法，使用hash方法也就是扰动函数时为了防止一些实现比较差的hashCode()方法，也就是说，扰动函数可以减少碰撞。

//jdk 11.0.1(估计还是和jdk 8一样，因为最新的eclipse支持，jdk 11.0.1所以我直接下载的最新版本)

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//jdk 1.7的hash方法
static final int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}

相比之下，JDk 11.0.1的方法性能要好一些，jdk 7的hash方法扰动了4次。

1.4 拉链法

拉链法就是将链表和数组结合，也就是说创建一个链表数组，数组每一个格是一个链表，若遇到哈希冲突，则将冲突的值加到链表中即可。
jdk 1.7:

jdk 1.8之后

1.5 HashMap类的成员变量

private static final long serialVersionUID = 3624988207631812

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

transient Set<Map.Entry<K,V>> entrySet;

transient int modCount;

int threshold;

final float loadFactor;

jdk 1.8及以后put方法
HashMap只提供了普通方法用于添加元素，putVal()方法是在put方法调用的时候调用的，没有给用户调用。putVal方法添加元素的过程如下：

如果定位到的位置没有元素就直接插入
如果定位到的数组位置有元素就和要插入的元素的key作比较，如果相同就直接覆盖(key不能重复，重复就覆盖)，再判断p是不是一个树节点，如果是调用 e = e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);将元素插入。如果不是就遍历链表插入。

1.6 Jdk 8 putVal方法的源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //tab未初始化就扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(n - 1) & hash是确定元素位于哪个桶中，桶为空，就生成新的节点放入桶中(此时，这//个节点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //如果桶中已存在
        else {
            Node<K,V> e; K k;
            //如果桶中第一个元素(数组中的节点)hash值与要传入的值的hash值相等且key相等，
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将第一个元素赋值给e,用e来记录
                e = p;
            //hash值不相等，即key不相等；为红黑树节点
            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);
                        //节点数量达到阈值，转化为红黑树(并不一定就会转成红黑树，)，Node数组要大于等于 MIN_TREEIFY_CAPACITY(64)//才可以
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        //跳出循环
                        break;
                    }
                    //判断链表中节点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //相等，跳出循环
                        break;
                    //用于遍历桶中的链表，与前面的 e = p.next结合，可以遍历链表
                    p = e;
                }
            }
            //表示在桶中找到key值、hash值与插入元素相等的节点
            if (e != null) { // existing mapping for key
                //记录e的value
                V oldValue = e.value;
                //onlyIfAbsent值为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值替换
                    e.value = value;
                //返回后回调
                afterNodeAccess(e);
                //返回旧值
                return oldValue;
            }
        }
        //结构性修改
        ++modCount;
        //满足实际容量大小大于阈值扩容条件
        if (++size > threshold)
            resize();
        //插入后回调
        afterNodeInsertion(evict);
        return null;
}

jdk1.7 put方法
put方法的分析：

如果定位到的数组位置没有元素就直接插入
如果定位到的数组位置有元素，遍历以这个元素为头节点的链表，依次和插入的key比较，如果key相同就直接覆盖，不同就采用头插法插入元素

1.7 jdk 1.7get方法

get方法分析：

get方法返回对应键值对的value，传入key，通过key得到hash值，hash值和key传入getNode()方法中得到一个Node类型的变量，为空返回null，不为空说明hash表中有这个元素，返回这个元素对应的value(e.value)。

getNode()方法，

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //传入的key的hash值与数组元素的hash(其实也可以是元素中key的hash值，因为hash只与key有关)，并且 (k = first.key) == //key 和 (key != null && key.equals(k))两个条件有一个为真，那么说明这个我们传入的key就是first这个元素的key，我们就是//想得到它的value值。此时返回Node，在上面的get()方法中返回这个Node对象的 value。
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //该桶不止一个元素，也就是有链表或者红黑树
            if ((e = first.next) != null) {
                //在红黑树中用get()方法，
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //在链表中调用get()方法，遍历，找到就返回
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}

1.8 getTreeNode方法

我们看看从红黑树中查找的方法实现

return ((TreeNode<K,V>)first).getTreeNode(hash, key);这里一个getTreeNode对象，也就是红黑树中节点对象，这里把Node类型的first强转为了TreeNode类型。

getTree方法

final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
}

// TreeNode中的find()方法，官方注释是通过这个方法找到那个元素,返回TreeNode，官方注释：
/**
 * Finds the node starting at root p with the given hash and key.
 * The kc argument caches comparableClassFor(key) upon first use
 * comparing keys.
 */
意思是通过传入的hash和key找到这个元素(红黑树TreeNode类型)。
 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
}

1.9 resize方法

resize方法分析：

这个方法用于进行扩容，会伴随着一次重新的hash分配，并且会遍历hash表中所有的元素，非常耗时。在编写程序时，尽量避免resize。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //超过最大值就不再扩充了
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //没有超过最大值，扩充为原来两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //计算新的resize上限，是为ft，还是Integer得最大值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //把每个桶都移到新的桶中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //原索引 + oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //原索引放到bucket中
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //原索引 + oldCap放到bucket中
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}

以下内容学习自以下博客

HashMap

下面以知识点的形式对HashMap进行解析

1，容量和 size 分别指什么？
答：容量并不是指 HashMap 所能存储的键值对数量，而是其内部的 table 数组的大小，而 size 是指目前已存储的键值对的数量。table 是一个 Entry 数组。 table 的每一个节点都连着一个链表或者红黑树。
2,初始容量可以随意设置吗？
答：可以，但是 HashMap 内部会你设置的 initialCapacity 转换为大于等于它的最小的2的n次方。比如 20 转为 32，32 转为 32等。如果不设置，则为默认值16。需要注意的是，在 Java 8的源码中，并没有在构造方法直接新建数组。而是先将处理后的容量值赋给 threshold，在第一次存储键值对时再根据这个值创建数组。
3，HashMap为什么要将容量转换为2的n次方？
答：这是为了提高取余的效率，存储键值对时，通过hash函数对key(键)求出key的hash值后，需要对数组的容量进行取余，余数即为key-value对在数组中的index(索引)。我们知道对于计算机而言，二进制计算的效率远远高于取余操作(%)。而容量如果是2的n次方的话，hash值对其取余就等同于hash值和容量值减1进行按位与操(&)作:

//capacity为2的n次方的话，下面两个操作结果相同
hash & (capacity - 1)
值等于
hash % capacity

原因：如果一个数是2的n次方，那它的二进制就是从右往左n位都是0，第n+1位是1。2的3次方二进制是1000,2的5次方二进制是100000，这个数的倍数也满足从右往左n为0，取余的时候抛弃倍数，就等同于将n+1位及其往左的所有位都置0，剩下的n位就代表余数。也就是说，一个数对2的n次方取余，就是要取这个数二进制的最低n位。2的n次方减1的结果就是n个1，进行与操作后得到了最低n位。

*4，HashMap的初始容量为多少？可以自己设置吗？
答：HashMap的初始容量为16，也就是不指定容量的情况下默认为16，可以自己设置，但HashMap内部会根据我们设置的initCapacity转换为大于等于它的最小的2的n次方。比如20默认转换为32,32转换为32。如何转换看问题3。

5，如何将一个数转换为大于等于它的最小的2的n次方呢？
答：如下代码所示，这是HashMap的源码：

我们先看代码的运行过程，如果我们在实例化HashMap对象的时候，在构造函数传入一个int值，也就是我们想自己设置容量的大小，此时会调用1处的构造函数，然后又调用了2处的构造函数，这个函数有两个参数，前面的代码是一些提高代码健壮性的代码，我们暂时不看，我们看到最后一行代码：
this.threshold = tableSizeFor(initialCapacity);
threshold是int类型，所以tableSizeFor应该返回的也是int型，我们看tableSizeFor的源码：

static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

我们分析一下这两行代码，tableSizeFor函数会返回一个数，这个int类型的数是大于等于它的最小的数并且是2的n次方。
numberOfLeadingZeros函数的代码：

public static int numberOfLeadingZeros(int i) {
        // HD, Count leading 0's
        if (i <= 0)
            return i == 0 ? 32 : 0;
        int n = 31;
        if (i >= 1 << 16) { n -= 16; i >>>= 16; }
        if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
        if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
        if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
        return n - (i >>> 1);
}

6，hash值是怎么计算的？
答：hash函数的源码:

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

可以看到，函数没有直接返回hashcode的返回值，而是进行了一些处理。我们通过hash函数得到的值要和Node数组容量进行按位与操作，我们已经知道这个操作的结果只与hash值的低n位有关，如果低n位时固定的或者集中在几个值，那么按位与的结果会很多相同，这就做”哈希碰撞”或”哈希冲突”，由于hashCode()函数可以重写，重写的时候可能写了一个性能不好的hashCode()函数，导致”哈希碰撞”产生。
为了尽量避免这种情况发生，HashMap的做法是先将hash值向右移，再进行异或操作，这样就使得高位的值和低位的值融合成一个新的值，这样可以保证后面的按位与操作受每一个二进制位的影响。

7，扩容后元素如何进行移动
答：为了防止元素增多后，链表越来越长，HashMap 会在元素个数达到阈值后进行扩容，新的容量为旧容量的2倍。容量变化后，每个元素用 hash 值取余的结果也会随之变化，需要在数组中重新排列。以前同一条链表上的元素，扩容后可能存在不同的链表上。

在 Java 7 中，重新排列实现得简单粗暴，直接用 hash 根据新容量算出下标，然后设置到新数组中，即相当于将元素重新put 了一次。但在 Java 8中，作者发现没必要重新插入，因为重新计算后，新的下标只可能有两种情况，要么是原来的值，要么是原来的值加旧容量。比如容量为16的数组扩容到32，下标为1的元素重新计算后，下标只可能为1或17。

这个怎么理解呢？重提一下之前的一句话，一个数对2的 n 次方取余，就是要取这个数二进制的最低 n 位。当容量为16时，取余是取最后4位的值，而扩容到32后，取余变成取最后5位的值。这里增加的1位如果为0，那么余数就没变，如果为1，那么余数就增加了16。如何取增加的这一位的值呢？直
接和16进行与操作即可。16的二进制是10000，与操作后如果结果为0，即表示高位为0，否则为1。

根据这个原理，我们只需要将原来的链表分成两条新链放到对应的位置即可，下面是具体步骤：

遍历旧数组，如果元素的 next 为空，直接取余后放到新数组；
如果元素后面连了一个链表，那么新建两条链表，暂且成为 hi 链和 lo 链；
遍历链表，计算每个元素的 hash 值和旧容量与操作的结果，结果为0则将其放入 lo 链末端，不为0放入 hi 链末端；
将两条链的 head 放到新数组中，其中 loHead 放到原来的位置，hiHead 放到原来的下标加上旧容量处；
如果是红黑树，进行和上面类似的操作，只是将两条链表换成两棵树。

if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null) 
            newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode) //红黑树类似
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
            //新建两条链表
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                if ((e.hash & oldCap) == 0) { //结果为0，表示下标没变，放入 lo 链
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                }
                else { //结果为0，表示下标要加上旧容量，放入 hi 链
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
            } while ((e = next) != null);
            if (loTail != null) { //lo 链放在原来的下标处
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) { //hi 链放在原来的下标 加旧容量处
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

1	if ((e.hash & oldCap) == 0)

这里是一个利用位运算代替常规运算的高效点：利用哈希值与旧的容量，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位。
还没理解，，，

增加元素
往表中添加一个元素，

public V put(K key, V value) {
    //先根据key，取得hash值。 再调用上一节的方法插入节点
    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);
}

这个hash函数也称为扰动函数，它的目的是为了让得出来的hash值更加均衡，与n-1作与运算(也就是计算元素在table表中的位置)后的值更加分散，减小哈希冲突。

以下内容来源于转载：
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。即，碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）
9，删除元素
以key为条件删除元素

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}

如果key对应的value存在，则删除这个键值对。并返回value。如果不存在返回null。
10,HashMap与Hashtable的区别

a,与之相比HashTable是线程安全的，且不允许key、value是null。
b,HashTable默认容量是11。
c,HashTable是直接使用key的hashCode(key.hashCode())作为hash值，不像HashMap内部使用- d,static final int hash(Object key)扰动函数对key的hashCode进行扰动后作为hash值。
HashTable取哈希桶下标是直接用模运算%.（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算）
扩容时，新容量是原来的2倍+1。int newCapacity = (oldCapacity << 1) + 1;
Hashtable是Dictionary的子类同时也实现了Map接口，HashMap是Map接口的一个实现类；

腾讯云：https://hexoblog-1257580711.cos-website.ap-guangzhou.myqcloud.com