我们在这篇文章中HashMap源码解析(JDK1.8)对HashMap进行了学习，在此基础上，继续总结HashMap的扩展问题，加深理解。

1.为什么capacity总是2的幂次方？

/**
     * HashMap 的table数组默认初始容量为 16，必须为 2 的 n 次方 
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

capacity默认为2的4次方，当我们初始化时传入的capacity不是2的次方会发生什么呢？

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的次方的cap，最终转化为了大于cap的最接近的2的次方值，比如

3—>4
20—>32
100—128

HashMap中存储数据table的index是由key的Hash值决定的.在HashMap存储数据时,我们期望数据能均匀分布,以防止哈希冲突.自然而然我们就会想到去用%取余的操作来实现我们这一构想，取余操作会存在于每次hash计算包括扩容时的重新hash。这里要了解到一个知识：

取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作.

再来看看table的index的计算规则：

index = e.hash & (newCap - 1)
等价于:
index = e.hash % newCap

采用二进制位操作&,相对于%,能够极大地提高运算效率,这就是cap的值被要求为2幂次的原因.

2.哈希碰撞和红黑树

上文中讲到，HashMap是通过计算key的hashCode来找到记录的存储位置的，由于hash函数不会太完美的原因，势必要造成多个记录的key的hashCode一样的情况，完美情况下，我们希望每一个数组位置上仅有一个记录，但是很多情况下一个数组位置上会落入多个记录，也就是哈希冲突。

2059840-8386849414328b14.png

哈希碰撞会对 hashMap 的性能带来灾难性的影响。如果多个 hashCode() 的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的 key 都映射到同一个桶中，这样 hashmap 就退化成了一个链表——查找时间从 O(1) 到 O(n)。
JDK1.8HashMap 的红黑树是这样解决的：HashMap在链表的长度大于8的时候就会将链表转换为红黑树这种数据结构，红黑树的查询效率高达O(lgN)，也就是说，复杂度降了一个数量级。如果哈希值相等，HashMap 希望 key 值最好是实现了 Comparable 接口的，这样它可以按照顺序来进行插入。这对 HashMap 的 key 来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，性能也是很堪忧的。

3.RESIZE扩容优化

在JDK1.7中扩容时，会将所有的元素重新计算hash散列到新的table数组位置，如图

jdk1.7扩容例图.png

JDK1.8对此做了一些优化：

因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：

ceb6e6ac-d93b-11e4-98e7-c5a5a07da8c4.png

因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

519be432-d93c-11e4-85bb-dff0a03af9d3.png

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;
        }
        // 没超过最大值，就扩充为原来的2倍
        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上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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;
}

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

4.hashCode()和equals()

hashCode() 是干嘛的？什么时候重写 equals() 方法啊？
总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？这就是Object.equals方法了。
但是，如果每增加一个元素就检查一 次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。
Java采用了哈希表的原理。哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以 直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了；不相同，也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。所以这里存在一个冲突解决的问题（很少出现）。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

所以，Java对于eqauls方法和hashCode方法是这样规定的：

1、如果两个对象相等，那么它们的hashCode值一定要相等；
2、如果两个对象的hashCode相等，它们并不一定相等(在同一个链表上)。