HashMap稍微详细的理解

此文章用来记录hashmap的一些特点（在学习中的所了解的，如有不足，请指正）

什么是hash表

概念

先来一段百度百科的的解释

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

所谓的hash表在我看来嘛就是映射嘛，以前嘛要查找一个数或者一个值嘛是通过遍历的形式，这样的话就会有一个问题，那就是太浪费时间了，时间效率非常低，也不能非常低嘛，时间复杂度是O(n)。于是呢，人们为了更快的找到需要查找的值呢就想到了一种办法，将存储的位置与存储的值对应起来，这样查找的效率不就高了很多。但是怎么转换呢，聪明的人类想到了一种办法，利用一种函数映射的形式来解决，这个映射用的函数就叫做hash函数，这个表呢就叫hash散列表，但是呢这是有问题的。那就是

hash表冲突

很好理解嘛，不同的值可能经过hash函数生成同样的索引，这样的话就有冲突了，怎么解决？请看

hash表冲突的解决

我所了解的常用的

直接寻址，也叫开放地址法，就是这个不能放我不放了，我放到下一个去，要是下一个还有就继续往后直到找到可以插入的位置，要是都没有，那就考虑一下扩容呗
hash再散列，就是用别的hash算法再算一遍
拉链法，这个方法就是hashmap中用到的方法。不是有冲突嘛，统统拿来，统统放这，一个别想跑。其实就是利用链表，冲突了就追加节点（不是同一个的话才追加）
建立公共溢出区，就是冲突了嘛，没坑了，那就走吧，不要呆在这里了

以上就是我所了解的，估计也是常用的吧，不然我也不会了解

HashMap

map的意思嘛，就是映射，才不是地图。Java中的HashMap就是利用hash表加链表实现的K,V形式的数据结构，和python中的字典是一样的。hashmap中的hash冲突的解决利用的是拉链法。1.7之前的拉链是只有链表，而在1.8增加了一个红黑树结构，这是因为，当链表长度太长的时候查找效率比较低。所以在hash桶数据的容量大于等于64以及hash桶内的元素数量大于8时就会转换为红黑树。有人说是大于等于8，大于64的时候，今天我们进入源码一探究竟，先来看个静态常量

static final int MIN_TREEIFY_CAPACITY = 64;

树化:treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {

    int n, index; Node<K,V> e;

//    如果说table 为null或者说容量小于64就扩容，不执行树化

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

    }

}

上面的就是进行树化的操作了，那么怎么才能树化呢

扩容：resize()方法

先准备一个重要的方法，resize()方法

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;//判断老表是否为null为null的话长度就是0

    int oldThr = threshold; // 保存原来的老阈值

    int newCap, newThr = 0; //先将新表的长度 阈值设置为0

    if (oldCap > 0) {

    //如果说老表的容量大于0且容量大于等于最大容量（MAXIMUM_CAPACITY = 1 << 30）

    //就将阈值设为Integer.MAX_VALUE,然后直接返回也就是不再扩容了，仅仅将阈值增大就行了

        if (oldCap >= MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return oldTab;

        }

         //如果说老容量乘以2小鱼最大容量以及大于等于默认的容量（ DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16）

        // 就将原来的阈值也扩充为两倍 就是说这里没啥意外容量就定下来了，也是一般的扩容情况

        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

            newThr = oldThr << 1; // double threshold

    }

    //如果说老表的容量小于等于0，但是老阈值大于0，就将新的容量设置为老阈值

    else if (oldThr > 0) // initial capacity was placed in threshold

        newCap = oldThr;

    //如果老表的容量以及老阈值都不大于0，就执行初始操作，将新表的容量设置为16，计算新表的阈值

    else {               // zero initial threshold signifies using defaults

        newCap = DEFAULT_INITIAL_CAPACITY;

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

    //如果说得出的新表阈值等于0的话就用新表的容量乘以负载因子，然后如果说新表的容量小于最大值以及新的阈值小于最大值，就将新阈值设为所求，否则就是Integer.MAX_VALUE

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

           MAX_VALUE       (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循环

        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;

                //如果说e是treeNode节点，也就是说，这个hash桶里边的节点已经树化过了

                else if (e instanceof TreeNode)

                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                //下面这个else的意思是如果有下一个节点而且没有树化，也是说是链表形式的至少有两个节点

                else { // preserve order

                    //这里就是将链表分成两种一种是高位链表一种是低位链表，至于什么是高低位链表，咱们往下看

                    //loHead低位头节点

                    //loTail低位尾节点

                    Node<K,V> loHead = null, loTail = null;

                    //hiHead高位头节点

                    //hiTail低位尾节点

                    Node<K,V> hiHead = null, hiTail = null;

                    //next节点

                    Node<K,V> next;

                    //开始do..While循环，因为肯定有next节点嘛，不然也到不了这里

                    do {

                        //保存一下next节点

                        next = e.next;

                        //注意这个与的 是与原来的容量进行比较的没有进行减一哈，减一是求索引用的。

                        //这里的意思举个例子来说就是比如原来的容量就是16吧，因为这里是位运算嘛，转换成二进制就是10000

                        //因为这里是等于0 的情况嘛，所以就假设e.hash二进制为1011001111吧，索引算出来就是1111

                        //运算开始 因不足用0补齐嘛

                        //1011001111

                        //     10000

                        //----------

                        //0000000000

                        //嗯 就是这种情况，因为原来容量二进制是5位也就是说如果hash值第五位是0，那么就扩容以后不会有任何变化

                        //因为扩容是变为原来的2倍，也就是左移一位变为100000。

                        //那么减1以后就是11111，刨去后边的4个1，两个最高位都是1也就是相同的，可以直接运算

                        //如果说此时元素的hash值在这个最高位是0的话，那么算出的索引与原来是一样的，这也就是低位索引

                        //这里只是将低位放在一起

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

                            //如果尾节点为空就初始化（说明头节点也没值）

                            if (loTail == null)

                                //这里的头节点指示头所在的位置，以后追加就是用为节点了，高位链表一样如此

                                loHead = e;

                            else

                                //让尾节点的next指向e，

                                loTail.next = e;

                            //然后尾节点向后移一位

                            //这里写成loTail=loTail.next我感觉比较好理解一些

                            loTail = e;

                        }

                        //如果说不是0的话，说明hash值的高位是1，经过运算后就是11111就是原来的索引加上2^4

                        //就是原来的表的长度，所以高位链表只需要原来的索引加上原来的表的长度就是新的索引

                        //这里只是将高位放到一起

                        else {

                            if (hiTail == null)

                                hiHead = e;

                            else

                                hiTail.next = e;

                            hiTail = e;

                        }

                    } while ((e = next) != null);

                    //循环结束后，如果说低位链表不为空的话就说明执行了分高低位的工作，而且有低位的存在

                    //然后只需要将hash桶的节点指向低位链表的头节点，而且因为是低位链表嘛，索引跟原来的一样

                    if (loTail != null) {

                        //这里将为节点的next设置为null,因为这再遍历的时候尾节点的next与尾节点指向同一个位置

                        //因为已经遍历完了嘛，next也就没有值了，所以就清空。高位链表类似

                        loTail.next = null;

                        newTab[j] = loHead;

                    }

                    //这里判断高位链表是否为空，空的就说明没有高位链表嘛

                    //不空的话就将原来的索引加上老表的容量，至于为什么，上面已经解释过

                    if (hiTail != null) {

                        hiTail.next = null;

                        newTab[j + oldCap] = hiHead;

                    }

                }

            }

        }

    }

    //至此返回新的链表

    return newTab;

}

你以为到这里就结束了？no，no，no，还有一个重要的方法，那就是如果是红黑树的话，怎么进行操作呢，就是这个红黑树节点里边的split(this, newTab, j, oldCap)方法了

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index,

                 int bit//这个bit什么意思呢，我猜是老表的容量，上面传过来的oldCap

                ) {

    TreeNode<K,V> b = this;

    // Relink into lo and hi lists, preserving order

    //开头雷击，梦回链表

    //这怎么和链表的操作差不多呢，也是分成高低位

    //其实注释上面也写了嘛

    //将树箱中的节点拆分为较高和较低的树箱，如果现在太小，则取消树化。

    //为什么红黑树的节点也可以这样呢，因为

    /**

     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

        TreeNode<K,V> parent;  // red-black tree links

        TreeNode<K,V> left;

        TreeNode<K,V> right;

        TreeNode<K,V> prev;

        // needed to unlink next upon deletion

        TreeNode(int hash, K key, V val, Node<K,V> next) {

            super(hash, key, val, next);

        }

    */

    //所以有个成员变量是next，那不就跟链表一样了

    TreeNode<K,V> loHead = null, loTail = null;

    TreeNode<K,V> hiHead = null, hiTail = null;

    //这个lc吧 low count：低位的数量

    //hc呢 high count：高位的数量

    int lc = 0, hc = 0;

    //显而易见，这里遍历treeNode

    //这里为什么不用while循环呢，是不用在外面声明变量嘛

    for (TreeNode<K,V> e = b, next; e != null; e = next) {

        next = (TreeNode<K,V>)e.next;

        e.next = null;

        //这里高低位一分，对应的count++就不展开细说了

        if ((e.hash & bit) == 0) {

            if ((e.prev = loTail) == null)

                loHead = e;

            else

                loTail.next = e;

            loTail = e;

            ++lc;

        }

        else {

            if ((e.prev = hiTail) == null)

                hiHead = e;

            else

                hiTail.next = e;

            hiTail = e;

            ++hc;

        }

    }

    if (loHead != null) {

        if (lc <= UNTREEIFY_THRESHOLD)

            //如果说数量小于等于UNTREEIFY_THRESHOLD=6，就弄成链表

            tab[index] = loHead.untreeify(map);

        else {

            tab[index] = loHead;

            //如果不小于6且高位链表不为null就树化

            //为啥需要高位链表不为空呢，

            /**

            这里个人理解，高位链表如果为空，说明旧数组下的红黑树中的元素在新数组中仍然全部在同一个位置，

            且先后顺序没有改变，也就是注释中的已经树化了，没有必要再次树化；而当高位节点不为空，

            说明原链表元素被拆分了，且位红黑树节点个数大于6，不满足转链表条件，需要重新树化。

            此处来自https://blog.csdn.net/hengwu1817/article/details/107095871/

            */

            //下面的高位链表也是如此

            if (hiHead != null) // (else is already treeified)

                loHead.treeify(tab);

        }

    }

    if (hiHead != null) {

        if (hc <= UNTREEIFY_THRESHOLD)

            tab[index + bit] = hiHead.untreeify(map);

        else {

            tab[index + bit] = hiHead;

            if (loHead != null)

                hiHead.treeify(tab);

        }

    }

}

插入数据 put

调用put(k,v)方法实际上调用的是putVal方法

public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);

}

所以只需要分析putVal方法即可

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,//是否不存在才插入

               boolean evict//文档给的是创建表的模式，我的理解是可读可写

              ) {

    Node<K,V>[] tab;

    Node<K,V> p; //p是table[i]所在的头

    int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length;//如果说原来的表不存在或者为空就执行resize()方法，上面已经进入看了一下

    //如果说原来的表的位置等于空的话就直接放进去 不存在冲突

    if ((p = tab[i = (n - 1) & hash]) == null)

        tab[i] = newNode(hash, key, value, null);

    else {

        //这里才是重点 到这里说明发生冲突

        Node<K,V> e;//e表示要要插入的节点

        K k;

        //这个判断是看原来的老的hash值跟我传进来的hash值是否相同并且key也相同 或者说key不为空并且相同

        //也就是判断一下是不是相同的key 是的话就将p赋值给e

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

                    //如果说大于等于8-1也就是7的话就树化 因为要插入元素了嘛，所以插入以后就等于8了

                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                        treeifyBin(tab, hash);

                    break;

                }

                //这里key相同的话就中断

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    break;

                p = e;

            }

        }

        //找到了要插入的节点后 如果e不为null 说明key是一样的 只需要替换一下值就好了

        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.7的hashmap的死循环问题以及本篇文章的1.8的死循环数据覆盖问题，以后再总结

巴特西