接上文 经典面试题之HashMap(一)
三 不考虑内存限制，HashMap可以无限存储数据吗？
不可以，HashMap是有最大容量上限的。我们还是来看下源码注释：
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;
很明显，如果构造函数传入的值大于MAXIMUM_CAPACITY ，那么替换成该数 MAXIMUM_CAPACITY 是 1 << 30 即 2的30次方。
为什么是1 << 30？ 1 <<31 不行吗？
注意看这个值是int 类型的。我们知道int 的极限最大值 Integer.MAX_VALUE 是2的31次方减1，即2147483647，如果 1 << 30 改为 1 << 31 ，由于int是有符号数，这个值将为 -2147483648，而且hashMap的容量都是2的整数次幂，也就只能是2的30次方了。然而这并不是HashMap的最大容量。
来看下HashMap的构造函数
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
上面代码中有一句
if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
如果我要存的数目大于 MAXIMUM_CAPACITY，你还把我的容量缩小成 MAXIMUM_CAPACITY？其实不是的，在resize()方法中有一句
if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; }
在这里我们可以看到其实 hashmap的“最大容量“是Integer.MAX_VALUE;
threshold=capacity*loadFactor threshold 表示当HashMap的size大于threshold时会执行resize操作。size就是HashMap中实际存在的键值对数量。
思考题：如果到达了HashMap的容量上限，再继续添加元素，会怎样？
其实你可以计算一下，当HashMap到达容量上限后占用的内存大小，已经很大了，所以一般情况下是内存溢出，我们在日常使用时，一般情况下不会把那么大的数据全部放到一个HashMap中。然而如果不考虑内存溢出的情况，就是你有一个超大的内存，那这个时候会怎样？
四 如何确定哈希桶数组索引位置？
我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用下面的代码来计算该对象应该保存在table数组的哪个索引处。
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 return h & (length-1); //第三步 取模运算 }
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
注意 h& (length-1) 当且仅当length(即capacity)是2的整倍数的时候才等于 h % length ,从这个角度也说明了capacity为什么一定要用2的整次幂。
数组长度-1 正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
五 了解HashMap的hash函数吗？
我们先来说说hash算法的一般实现：
- 大数变小数-->取模
- 让结果的规律性不明显--> 异或、改变原始数据、移位
- 碰撞是存在的，主要是看解决碰撞的方案
java中常用的hashCode算法
- Object类的hashCode。返回对象的经过处理后的内存地址。由于每个对象的内存地址都不一样，所以哈希码也不一样，这是个native方法。取决于JVM的内部设计，一般是某种C地址的偏移。
- String 类的hashCode,根据String类包含的字符串的内容，根据一种特殊的算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
- Integer 等包装类，返回的哈希码就是Integer对象里所包含的那个整数的值，例如 Integer i1 = new Integer(100), i1.hashCode() 的值就是 100。由此可见，两个一样大小的Integer对象，返回的哈希码也一样。
- int、char这样的基础类，它们不需要hashCode,如果需要存储时，将进行自动装箱操作，计算方法同上。
我们来看下HashMap中的hash算法是如何实现的：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
hash(Object key)的作用就是重新计算hash值。
HashMap中为什么不直接用key.hashCode()获取哈希值，而是使用(h = key.hashCode()) ^ (h >>> 16)？
我们通过上文了解了HashMap如何计算出数组索引位置，但其实有一个问题，就是即使我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比蛋疼。
这时候“扰动函数”的价值就体现出来了
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。（JDK 7做了4次右移，估计是边际效应的原因，JDK8就只做了一次右移）
总结 ：(h = key.hashCode()) ^ (h >>> 16)这样写有点类似重写了hashCode，确保得出的数足够的随机，因为进行hash计算的时候 确保它的数足够的分散，以便于计算数组下标的时候存放的值足够分散。
