相关文章
java源码分析之HashMap（一）
java源码分析之HashMap（二）
https://blog.csdn.net/q5706503/article/details/84076261
https://blog.csdn.net/q5706503/article/details/85114159
前两篇我们分析了HashMap中的一些主要方法和它的一些实现方式，但是并没有分析为什么要用这种方式的实现，比如：为什么JDK8的HashMap扩容要使用双倍扩容？为什么最大容量要设置成2的整数幂？俗话说，知其然还要知其所以然，本篇就重点从设计思想上分析HashMap的实现，直面大师们的内心世界。
为什么hash算法得到的结果可以做到散列均匀分布？
首先看一下HashMap的putVal方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 代码省略
}
第一个参数hash是调用HashMap的hash()方法得到的，
我们看一下这个方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码叫做“扰动函数”
大家都知道上面代码里的key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。
理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组，内存是放不下的。你想，HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。结合我们前两篇文章的分析，取模的运算是使用位运算h & (length-1)来实现的。
顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为2的整数幂用二级制表示一定是100···这种形式，因此2的整数幂减1一定是11111····这种形式， 这样（数组长度-1）正好相当于一个“低位掩码”， “与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零，只保留末四位
但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比蛋疼。
这时候“扰动函数”的价值就体现出来了，说到这里大家应该猜出来了。看下面这个图
扰动函数示例
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
由此我们可以得出结论：
hash()方法是对hashcode又一次进行了散列，增加值的随机性。
但是读到这里，我们依然没有看到key.hashCode()方法是如何做到散列的。我们追踪key的hashCode方法：
public native int hashCode();
这是个native的方法,我们看一下这个native方法的实现：
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value = 0 ;
if (hashCode == 0) {
// 根据Park-Miller伪随机数生成器生成的随机数
value = os::random() ;
} else
if (hashCode == 1) {
// 此类方案将对象的内存地址，做移位运算后与一个随机数进行异或得到结果
intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode == 2) {
value = 1 ; // 返回固定的1
} else
if (hashCode == 3) {
value = ++GVars.hcSequence ; // 返回一个自增序列的当前值
} else
if (hashCode == 4) {
value = cast_from_oop<intptr_t>(obj) ; // 对象地址
} else {
// 通过和当前线程有关的一个随机数+三个确定值
unsigned t = Self->_hashStateX ;
t ^= (t << 11) ;
Self->_hashStateX = Self->_hashStateY ;
Self->_hashStateY = Self->_hashStateZ ;
Self->_hashStateZ = Self->_hashStateW ;
unsigned v = Self->_hashStateW ;
v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW = v ;
value = v ;
}
value &= markOopDesc::hash_mask;
if (value == 0) value = 0xBAD ;
assert (value != markOopDesc::no_hash, "invariant") ;
TEVENT (hashCode: GENERATE) ;
return value;
}
java8默认是通过和当前线程有关的一个随机数+三个确定值，运用Marsaglia’s xorshift scheme随机数算法得到的一个随机数。
具体源码分析可以参考：
https://fangjian0423.github.io/2016/03/12/java-Object-method/
从以上的分析我们可以得出如下结论：
hashCode（）方法通过随机数+内存地址进行一系列操作得到一个随机值作为hashcode,这个随机值是均匀的
HashMap()的hash()方法将hashcode和hashcode右移16位后进行异或运算，进一步增加随机性。
equals方法和hashcode的关系是什么？
这一点又是一个长篇大论，下面直接说结论：
1.若重写了equals(Object obj)方法，则有必要重写hashCode()方法。
2.若两个对象equals(Object obj)返回true，则hashCode（）有必要也返回相同的int数。
3.若两个对象equals(Object obj)返回false，则hashCode（）不一定返回不同的int数。
4.若两个对象hashCode（）返回相同int数，则equals（Object obj）不一定返回true。
5.若两个对象hashCode（）返回不同int数，则equals（Object obj）一定返回false。
6.同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题。
具体的分析可以参考下面的文章：
HashMap 的容量不是2的整数幂有什么问题么？
我们再看看刚刚说的那个根据hash计算下标的方法：
tab[(n - 1) & hash]；
其中 n 是数组的长度。其实该算法的结果和模运算的结果是相同的。但是，对于现代的处理器来说，除法和求余数（模运算）是最慢的动作。
上面情况下和模运算相同
a % b == (b-1) & a ,当b是2的指数时，等式成立。
我们说 & 与运算的定义：与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0；
当 n 为 16 时， 与运算 101010100101001001101 时，也就是
1111 & 101010100101001001000 结果：1000 = 8
1111 & 101000101101001001001 结果：1001 = 9
1111 & 101010101101101001010 结果： 1010 = 10
1111 & 101100100111001101100 结果： 1100 = 12
可以看到，当 n 为 2 的幂次方的时候，减一之后就会得到 1111···· 的数字，这个数字正好可以掩码。并且得到的结果取决于 hash 值。因为 hash 值是1，那么最终的结果也是1 ，hash 值是0，最终的结果也是0。
我们说，hash 算法的目的是为了让hash值均匀的分布在桶中那么，如何做到呢？试想一下，如果不使用 2 的幂次方作为数组的长度会怎么样？
假设我们的数组长度是10，还是上面的公式：
1010 & 101010100101001001000 结果：1000 = 8
1010 & 101000101101001001001 结果：1000 = 8
1010 & 101010101101101001010 结果： 1010 = 10
1010 & 101100100111001101100 结果： 1000 = 8
看到结果我们惊呆了，这种散列结果，会导致这些不同的key值几乎全部进入到相同的插槽中，形成链表，性能急剧下降。
所以说，我们一定要保证 & 中的二进制位全为 1，才能最大限度的利用 hash 值，并更好的散列，只有全是1 ，才能有更多的散列结果。如果是 1010，有的散列结果是永远都不会出现的，比如 0111，0101，1111，1110…，只要 & 之前的数有 0， 对应的 1 肯定就不会出现（因为只有都是1才会为1）。大大限制了散列的范围。
网友评论