HashMap中有意思的方法！

关于HashMap的源码，网上文章多如沙海，本文只关注其中几个有意思的地方！

JDK版本： 1.8.0_151

知识点盘点

1.  的二进制表示，只有最高位是1，其余的都是0，而 则全部二进制位都是1，如下图所示

 

2.  Java中的位运算符：

• &： 位与操作，全1则1，有0则0
• | ： 位或操作， 有1则1，全0则0
• ^:    异或操作，相同则1，不同则0
• >> : 右移，如果这个数是正数，则高位补0，如果是负数，则高位补1
• >>>: 无符号右移，无论正负，高位补0
• <<: 左移，不分正负，低位补0

3.  一点儿结论：

• 一个任意的int值a对 进行&操作，即 a & （），结果等同于 a%。就是取模值；
• 一个任意的int值a对进行&操作，即 a &  ，结果如果是0，那么 a %  = a % （*2），如果不是0，那么 a % （*2）=  a %   +   

 

HashMap中的方法

1. 取hash的方法

// put之前，先对key进行取hash操作
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 扰动函数，尽量避免hash碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

  从取hash的方法中，可以看出如果key是null，则直接返回0，所以map允许存null，
  如果key不是null，则就取key的hashCode与hashCode >>> 16的 异或操作值。称这个函数为扰动函数。

2. tableSizeFor（int cap） 根据传入值获取大于此值的最小的2的m次方。

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

首先  n |= n >>> 1 相当于 n = n | n >>> 1 。 首先n值的最高位肯定是1，右移1位，做位或操作的结果是，第1，2高位是1；然后右移2位，做位或操作的结果是，第1，2，3，4位是1，右移4位，同理，前8位一定是1, 最终理论上所有位上都会变成1， 最终在加上1，则是大于这个n值的最小2的m次方；（关于最大值校验，则不再叙述）如图

3.  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()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
...
}

我们关注在(n - 1) & hash这个操作上，首先n是tab.length(),也就是hashMap中的“哈希桶”的数量，这个值一定是2的m次方，hash值与（n-1）进行&操作后的结果就是 hash%n ，也就是这个key应该在的桶的索引。

 

4. resize（）方法，2倍扩容方案

final Node<K,V>[] resize() {
   ...
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 清空原来的桶的node，此时原来的Node值已经赋给了e
                oldTab[j] = null;
                // 如果只有这一个值，那么直接进行和put方法中相同的hash操作即可。
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树，则进行红黑树的rehash操作，流程和下面的链表一样。
                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;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
...
}

我们只关注标注中有意思的部分，key的hash对oldCap进行 & 操作，结果是啥呢？ 因为oldCap是2的m次方，所以它的二进制表示中，只有最高位是1， 所以 hash & oldCap的结果不是0就是 。而对这两种结果，有一下特点，如图：

如果不对之处，请大家指出，谢谢！！