HashMap源码阅读记录

• 先说说1.7
• 在1.8的优化
• 讲一下put方法，插入的流程
• • 扩容的过程 resize

先说说1.7

1.7的时候主要存在几个问题

• key的hash值计算方式很复杂
• 在扩容的时候，因为使用的是尾插法，所以在多线程对这个变量进行操作的时候会产生一个环，导致死循环
• 最大的问题就是hash冲突问题，当一个桶里元素过多的时候，就相当于一个很长的链表，查询的时候需要从头到尾遍历一遍，时间复杂度是O（n）。

在1.8的优化

• hash计算方式，是通过key的hashcode的高16位与hashcode进行异或运算

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

• 使用了尾插法，解决了死循环的问题
• 计算初始容量的方式发生改变，1.7的时候是通过对1进行左移运算，直到找到比入参容量大的一个2的n次幂的数。1.8的时候，用了一种更优雅的方式，就是通过5个移位运算，得到一个低位全是1的值，最后得到一个初始容量。

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

• 最重要的就是使用了数组+链表+红黑树。在数组长度大于64并且链表的长度大于8的时候会转换成一个红黑树。这样他的查询效率得到提升，以前是O(n),红黑树是O(logn)

讲一下put方法，插入的流程

1. 首先通过key的hashcode来计算hash值
2. 这个时候看map是否为空，如果为空的话就会先进行一次resize扩容，这时候他的初始容量大小是16
3. 通过hash值和hashmap长度-1进行与运算得到桶的索引下标
4. 找到桶的位置后，观察这个桶的头节点是否为空，如果是空的话就直接放进去，因为hashmapkey是不允许相同的，所以，如果不为空就检查头节点的key是否与入参的key相同，如果相同的话就直接覆盖value，如果不同就遍历这个链表，如果发现相同的key也进行覆盖，否则通过尾插法插入到链表的最后。
5. 当链表的长度大于8并且数组的长度大于64的时候，会转变为红黑树

扩容的过程 resize