本文代码及测试示例，运行环境基于JDK 1.8 

HashMap hash()

为什么要有HashMap的hash()方法，难道不能直接使用KV中K原有的hash值吗？

在HashMap的put、get操作时为什么不能直接使用K中原有的hash值。

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

从上面的代码可以看到key的hash值的计算方法。

key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。

h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。

为什么要这么干呢？ 这个与HashMap中table下标的计算有关。

n = table.length;
index = （n-1） & hash;

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0。 

假设table.length=2^4=16。 

由上图可以看到，只有hash值的低4位参与了运算，这样做很容易产生碰撞。

设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

HashMap tableSizeFor()

tableSizeFor() 源码：

    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 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;
    }

这个方法被调用的地方：

    public HashMap(int initialCapacity, float loadFactor) {
        /**省略此处代码**/
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

由此可以看到，当在实例化HashMap实例时，如果给定了initialCapacity，由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。 

下面分析这个算法： 

首先，为什么要对cap做减1操作

int n = cap - 1; 

这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。 

下面看看这几个无符号右移操作： 

如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。 

这里只讨论n不等于0的情况。 

第一次右移

n |= n >>> 1;

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。 

第二次右移

n |= n >>> 2;

注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。 

第三次右移

n |= n >>> 4;

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。 

以此类推 

注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY 。 

举一个例子说明下吧。 

这个算法着实牛逼啊！

写了一个简单测试示例：

	public static void TestTableSize() {
		int num = 20;
		for(int i=0; i<=num; i++) {
			System.out.println("TestTableSize - " + i + " : " + tableSizeFor(i));
		}
	}

	public static final int tableSizeFor(int cap) {
		final int MAXIMUM_CAPACITY = 1 << 30;
        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;
    }

运行结果：

TestTableSize - 0 : 1
TestTableSize - 1 : 1
TestTableSize - 2 : 2
TestTableSize - 3 : 4
TestTableSize - 4 : 4
TestTableSize - 5 : 8
TestTableSize - 6 : 8
TestTableSize - 7 : 8
TestTableSize - 8 : 8
TestTableSize - 9 : 16
TestTableSize - 10 : 16
TestTableSize - 11 : 16
TestTableSize - 12 : 16
TestTableSize - 13 : 16
TestTableSize - 14 : 16
TestTableSize - 15 : 16
TestTableSize - 16 : 16
TestTableSize - 17 : 32
TestTableSize - 18 : 32
TestTableSize - 19 : 32
TestTableSize - 20 : 32

注意，得到的这个capacity却被赋值给了threshold。

this.threshold = tableSizeFor(initialCapacity);

开始以为这个是个Bug，感觉应该这么写：

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。 

但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算，put方法的具体实现请看这篇博文。

参考资料

1. Java HashMap工作原理及实现 

2. Java7的HashMap初始化变化 

3. java HashMap

Java list 用法及排序和遍历