HashMap中哈希值的计算方法和扩容机制
HashMap中使用的计算哈希值的方法的剖析
/*** 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);
}我们查看put的源码会发现put的底层是一个putVal方法，里面的hash值算法如上
1.key.hashCode();返回散列值也就是hashcode。假设随便生成的一个值。
2.n表示数组初始化的长度是16
3.&(按位与运算):运算规则:相同的二进制数位上，都是1的时候，结果为1，否则为零。
4.^(按位异或运算):运算规则:相同的二进制数位上，数字相同，结果为0，不同为1。
hashCode的底层就是调用的c++的native方法
简单的对hash方法的解析就是：高16 bit 不变，低16 bit 和高16 bit 做了一个异或(得到的 hashcode 转化为32位二进制，前16位和后16位低，16 bit和高16 bit做了一个异或。
HashMap的扩容机制
扩容机制
当HashMap中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16x0.75=12(这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为2x16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
补充:
当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。
HashMap的扩容是什么
进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的(n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量”这个位置。怎么理解呢?例如我们从16扩展为32时，具体的变化如下所示:
在原来长度的集合情况下，我们就发现了，在同一块数组空间下是有可能出现链表情况的，当我们进行扩容之后，在进行计算就会发现，原先在一个链表之内的数据最后可能会出现在原来的位置和旧位置+旧数组容量，所以扩容之后在一个链表上的数据的索引位置要么是原来索引，要么是原来索引+旧数组的容量。
事实上我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。如下图：
正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。