HashMap 1.8与1.7不同
4.4 1.8 hash方法
作者：牛客7380095号
链接：https://www.nowcoder.com/discuss/151172?source_id=profile_create&channel=-2
来源：牛客网
Java 8中的散列值优化函数
image
只做一次16位右位移异或
key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值
理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int范围大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组，内存是放不下的.HashMap扩容之前的数组初始大小才16,所以这个散列值是不能直接拿来用的.
用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标
源码中模运算就是把散列值和数组长度做一个"与"操作，
image
这也正好解释了为什么HashMap的数组长度要取2的整次幂
因为这样（数组长度-1）正好相当于一个“低位掩码”
“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问
以初始长度16为例，16-1=15
2进制表示是00000000 00000000 00001111
和某散列值做“与”操作如下，结果就是截取了最低的四位值
image
但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重
这时候“扰动函数”的价值就体现出来了
image
右位移16位，正好是32位一半，自己的高半区和低半区做异或，就是为了混合原始hashCode的高位和低位，以此来加大低位的随机性
而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
index的运算规则是
e.hash & (newCap - 1)
newCap是2的幂,所以newCap - 1的高位全0
若e.hash值只用自身的hashcode,index只会和e.hash的低位做&操作.这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会带来哈希冲突的风险
所以在计算key的hashCode时,用其自身hashCode与其低16位做异或操作
这也就让高位参与到index的计算中来了,即降低了哈希冲突的风险又不会带来太大的性能问题
三、为何HashMap的数组长度一定是2的次幂？
我们来继续看上面提到的resize方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
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);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
HashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。
在这里插入图片描述
还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀
在这里插入图片描述
我们看到，上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
在这里插入图片描述
如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。
get方法：
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
可以看出，get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。
四、重写equals方法需同时重写hashCode方法
最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值，通过idCard来确定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出，从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
}
}
实际输出结果：null
https://www.cnblogs.com/vi3nty/p/10642456.html
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
五、JDK1.8中HashMap的性能优化
假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？
JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
关于这方面的探讨我们以后的文章再做说明。
