HashMap相关专题

前置知识：异或运算

异或运算介绍
异或有什么神奇之处（应用）？
（1）快速比较两个值
（2）我们可以使用异或来使某些特定的位翻转，因为不管是0或者是1与1做异或将得到原值的相反值；
（3）我们使用异或来判断一个二进制数中1的数量是奇数还是偶数
（4）校验和恢复
（5）经典题目：不使用其他空间，交换两个值
（6）最最常出现的面试题：一个整型数组里除了N个数字之外，其他的数字都出现了两次，找出这N个数字；

HashMap详解

必读：参考文章

HashMap的长度为什么是2的幂次方

推荐阅读
今天在看面试指南里的HashMap，看到HashMap长度为什么是2的幂次方时没太读懂，特别是最后一段为什么一定要
是2的幂次方这个等式才成立，这里也没有明说
经过一番查证才搞明白，原来是因为2的幂次方的二进制表示只有一个1，其余都是0。例如，2的幂次方的二进制表示为：1, 10, 100, 1000，等等。现在考虑 length - 1，它的二进制表示就是 length 的二进制表示中的所有1。例如，如果 length 是 8，那么 length - 1 的二进制表示就是 7 的二进制表示为 111。因此，hash & (length-1) 实际上就是保留 hash 的二进制表示中的低位，忽略掉高位（因为低位们就是余数）。这样就能保证取模运算 hash % length 的效果和位运算 hash & (length-1) 是一样的，但是位运算的速度更快。
举例：
hash=1235，length=8
1235%8=3
1235=0100 1101 0011，7=0111
0100 1101 0011 & 0111 = 0011（3）