### 问题

Android环境下的HashMap类中，扩容后重新哈希的代码中，计算index不是像put中的那样使用hash & newCapacity - 1，而是使用hash & oldCapacity得到hightBit,再用hightBit | j得到index。二者的结果相同，但是计算步骤上反而是后者多了一步或运算。这样写的好处在哪里？

private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
}

for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}


### 解答

Android这么玩，是基于一个事实：HashMap的长度是2的整数次幂。

HashMap每次扩容，也是长度翻倍：

• int newCapacity = oldCapacity * 2;

        10100101 11000100 00110101
&	00000000 00000000 00001111    //掩码=16-1
----------------------------------
00000000 00000000 00000101    //高位全部归零，只保留末四位


        10100101 11000100 00110101
&	00000000 00000000 00011111    //掩码=32-1
----------------------------------
00000000 00000000 00010101    //只是第5位变化了


    /**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}


Android搞了一个嫁接：

int highBit = e.hash & oldCapacity;


        10100101 11000100 00110101
&	00000000 00000000 00010000    //掩码=16
----------------------------------
00000000 00000000 00010000    //highBit只保留第5位


highBit把第5位单独切出来，而代表原来的后4位散列值。嫁接到一起（用“|”或操作完成），正好是新的5位散列值。

newTable[j | highBit] = e;


50%的概率是不需要搬的。

                if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}