引言
这两天有个学弟问过我这个问题&＃xff1a;对象的 hashCode 到底是怎么实现的&＃xff1f;
在深挖之前&＃xff0c;我可能只能说&＃xff1a;如果没有被重载&＃xff0c;代表的是对象的地址通过某种 hash 算法计算后在 hash 表中的位置。
回答后&＃xff0c;仔细一想&＃xff0c;不对呀&＃xff0c;这个 hash 值具体是怎么计算的&＃xff0c;我终究还是没有答到点上&＃xff0c;而是绕开话题&＃xff0c;回答了含义。
脑壳一热&＃xff0c;忽然想起去年虐我的阿里面试题&＃xff0c;hashCode 是怎么得到的呢&＃xff1f;
一、问题定义
hashCode 真的只是通过地址计算的吗&＃xff1f;如果对象地址变化了&＃xff0c;比如经历的 GC&＃xff0c;hashCode 是不是也跟着变了呢&＃xff1f;如果此时刚好在进行锁升级&＃xff0c;对于 hashCode 的计算会有影响吗&＃xff1f;多线程的情况下会不会生成一样的 hashCode 呢&＃xff1f;具体通过什么样的 hash 算法得到的呢&＃xff1f;相比之下&＃xff0c;我真的是太皮毛了&＃xff5e;
首先看下一个简单的实现类&＃xff0c;这里先别使用 lombok 注解&＃xff0c;原因后文会解释&＃xff1a;
public class Student {
private int no;
private String name;
public void setNo(int no) {
this.no &＃61; no;
}
public void setName(String name) {
this.name &＃61; name;
}
public static void main(String[] args) {
Student student1&＃61;new Student();
student1.setName("张三");
student1.setNo(12);
System.out.println(student1.hashCode());
}
}
多次运行后&＃xff0c;可以大胆假设 hashCode 的计算是稳定的。只要对象的引用不变&＃xff0c;每次运行都是相同的结果&＃xff0c;所以网上说使用随机数计算的回答&＃xff0c;这个先打一个问号。..
大家可能印象比较深刻&＃xff0c;当你打开源码时&＃xff0c;会发现 native 修饰的方法会挡住你的去路。C&＃43;&＃43; 实现的方法难道就该让我们止步了吗&＃xff1f;这次打算死磕到底。
二、源码揭秘
2.1 Object.hashCode () 注释解读
简单归纳一下 JDK 团队的注释&＃xff1a;
hashCode 表示对象在 hash 表中的位置&＃xff0c;对于同一个对象来说&＃xff0c;多次调用&＃xff0c;返回相同的 hashCode。
如果 Object.equal () 相等&＃xff0c;Object.hashCode () 也必然相等。重写时也建议保证此特性。
如果 Object.equal () 相等&＃xff0c;这并不要求 Object.hashCode () 也返回不同值。如果真出现这种情况&＃xff0c;最好优化代码&＃xff0c;充分利用 hash 表的性能。
2.2 hashCode 生成源码
下面是 C&＃43;&＃43; 对应的实现&＃xff0c;这里拷贝一下网上其他大佬发的 hashCode 实现核心源码&＃xff1a;
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value &＃61; 0 ;
if (hashCode &＃61;&＃61; 0) {
// This form uses an unguarded global Park-Miller RNG, // so it&＃39;s possible for two threads to race and generate the same RNG. // On MP system we&＃39;ll have lots of RW access to a global, so the // mechanism induces lots of coherency traffic. value &＃61; os::random() ;
} else
if (hashCode &＃61;&＃61; 1) {
// This variation has the property of being stable (idempotent) // between STW operations. This can be useful in some of the 1-0 // synchronization schemes. intptr_t addrBits &＃61; intptr_t(obj) >> 3 ;
value &＃61; addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode &＃61;&＃61; 2) {
value &＃61; 1 ; // for sensitivity testing } else
if (hashCode &＃61;&＃61; 3) {
value &＃61; &＃43;&＃43;GVars.hcSequence ;
} else
if (hashCode &＃61;&＃61; 4) {
value &＃61; intptr_t(obj) ;
} else {
// Marsaglia&＃39;s xor-shift scheme with thread-specific state // This is probably the best overall implementation -- we&＃39;ll // likely make this the default in future releases. unsigned t &＃61; Self->_hashStateX ;
t ^&＃61; (t <<11) ;
Self->_hashStateX &＃61; Self->_hashStateY ;
Self->_hashStateY &＃61; Self->_hashStateZ ;
Self->_hashStateZ &＃61; Self->_hashStateW ;
unsigned v &＃61; Self->_hashStateW ;
v &＃61; (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW &＃61; v ;
value &＃61; v ;
}
value &&＃61; markOopDesc::hash_mask;
if (value &＃61;&＃61; 0) value &＃61; 0xBAD ;
assert (value !&＃61; markOopDesc::no_hash, "invariant") ;
TEVENT (hashCode: GENERATE) ;
return value;
}
源码中的 hashCode 其实就是 JVM 启动的一个参数&＃xff0c;每一个分支对应一个生成策略。通过 -XX:hashCode&＃xff0c;可以任意切换 hashCode 的生成策略。
首先解释一下入参 oop obj 就是对象的逻辑地址。所以与地址相关的生成策略有两条&＃xff0c;在 hashCode 等于 1 或 4 的时候。
其他情况&＃xff1a;
hashCode&＃61;&＃61;0&＃xff1a;简单地返回随机数&＃xff0c;与对象的内存地址没有联系。然而根据随机数生成并全局地读写在多处理器下并不占优势。
hashCode&＃61;&＃61;2&＃xff1a;始终返回完全相同的标识&＃xff0c;即 hashCode&＃61;1。这可用于测试依赖对象标识的代码。
hashcode&＃61;&＃61;3&＃xff1a;从零开始计算哈希代码值。它看起来不是线程安全的&＃xff0c;因此多个线程可以生成具有相同哈希代码的对象。
hashCode>&＃61;5(默认)&＃xff1a;在 jdk1.8 中&＃xff0c;这是默认的 hashCode 生成算法&＃xff0c;支持多线程生成。使用了 Marsaglia 的 xor-shift 算法产生伪随机数。
可以知道&＃xff0c;hashCode 为 5 就是我们程序调用时的默认策略。其他的几个分支我的理解也只能到这里&＃xff0c;如果有大佬了解的更细&＃xff0c;可以在评论指出。这里先不管 Marsaglia 大佬是谁&＃xff0c;为什么是伪随机数呢&＃xff1f;
关于真随机数的生成&＃xff0c;这里可能要牵扯到随机数生成的物理知识。Intel810RNG 的原理大概是&＃xff1a;利用热噪声 (是由导体中电子的热震动引起的) 放大后&＃xff0c;影响一个由电压控制的振荡器&＃xff0c;通过另一个高频振荡器来收集数据... ...
我们实际应用的基本上都是通过数学公式产生的伪随机数。严格意义上讲&＃xff0c;伪随机数不是完全随机的&＃xff0c;但是真随机生成比较困难&＃xff0c;所以只要能通过一定的随机数统计检测&＃xff0c;就可以当作真随机数来使用。
有点离题了&＃xff0c;下面来谈谈这个 xor-shift 算法&＃xff5e;
Marsaglia 的 xor-shift 策略&＃xff0c;支持多线程执行的状态&＃xff0c;这可能是最好的整体实现 &＃xff0c;这种方式生成随机数执行起来很快。简单来说&＃xff0c;看起来就是一个移位寄存器&＃xff0c;每次移入的位由寄存器中若干位取异或生成。每次新生成的位看起来是随机的。如果要深究&＃xff0c;可能会扯很多数学公式&＃xff0c;这里就不探讨了(毕竟数学太深奥了&＃xff0c;菜是原罪)。
从维基百科上粘的基本实现&＃xff1a;
uint32_t xor128(void) {
static uint32_t x &＃61; 123456789;
static uint32_t y &＃61; 362436069;
static uint32_t z &＃61; 521288629;
static uint32_t w &＃61; 88675123;
uint32_t t;
t &＃61; x ^ (x <<11);
x &＃61; y; y &＃61; z; z &＃61; w;
return w &＃61; w ^ (w>> 19) ^ (t ^ (t>> 8));
}
这里面的入参还是需要好好打磨的&＃xff0c;才能通过随机数的严苛测试&＃xff5e;
拓展阅读&＃xff1a;zhihu.com/question/2795
论文地址&＃xff1a;jstatsoft.org/v08/i14/p
2.3 从局部到全局
了解了 hashCode 是怎么产生的&＃xff0c;再看看上层&＃xff0c;获取前需要做哪些准备&＃xff1f;具体代码比较长&＃xff0c;就不贴出了&＃xff0c;简单概括。
如果处于偏向锁状态&＃xff0c;就需要先撤销偏向锁。然后确保当前线程执行路径不在 safe point 上&＃xff0c;并且是 java 线程&＃xff0c;未阻塞状态。读取稳定的对象头&＃xff0c;防止对象继续锁升级&＃xff0c;如果是&＃xff0c;就需要等待升级完。等到对象状态稳定了&＃xff0c;从对象头中取出 hash&＃xff0c;如果不存在&＃xff0c;则执行上文代码&＃xff0c;计算 hashCode。如果对象处于轻量级锁状态&＃xff0c;并且当前线程持有&＃xff0c;就从 线程的栈里取对象头。当升级为重量级锁时&＃xff0c;就执行上文代码&＃xff0c;计算 hashCode。
因此&＃xff0c;hashCode 只会被计算一遍&＃xff0c;之后就存在对象头中。
拓展阅读&＃xff1a;zhihu.com/question/2997
至此&＃xff0c;jdk 原生 hashCode 的生成过程梳理完了。
三、String、Lombok 对 hashCode 的实现
3.1 Lombok 实现 hashCode
如果把实体类换成 Lombok 实现&＃xff0c;又会怎么样呢&＃xff1f;
&＃64;Data
public class Student {
private int no;
private String name;
public static void main(String[] args) {
Student student1&＃61;new Student();
student1.setName("张三");
student1.setNo(12);
System.out.println(student1.hashCode());
Map map&＃61;new HashMap<>();
map.put(student1,"student1");
student1.setName("111");
System.out.println(student1.hashCode());
System.out.println(map.get(student1));
}
}
输出&＃xff1a;
779078
52846
null
可以神奇地看到&＃xff0c;hashCode 明显被修改了&＃xff0c;并且 hashMap 也取不到值&＃xff0c;这是怎么回事&＃xff1f;
原来&＃xff0c;Lombok 的 &＃64;Data 注解相当于 5 个注解&＃xff1a;
相当于重写了 hashCode&＃xff0c;只要属性发生变化&＃xff0c;再次输出时&＃xff0c;hashCode 就会不同。
如果将代码反编译后&＃xff0c;不难发现。
public class Student {
private int no;
private String name;
public int hashCode() {
int PRIME &＃61; true;
int result &＃61; 1;
int result &＃61; result * 59 &＃43; this.getNo();
Object $name &＃61; this.getName();
result &＃61; result * 59 &＃43; ($name &＃61;&＃61; null ? 43 : $name.hashCode());
return result;
}
}
3.2 String 实现 hashCode
public int hashCode() {
int h &＃61; hash;
if (h &＃61;&＃61; 0 && value.length > 0) {
char val[] &＃61; value;
for (int i &＃61; 0; i h &＃61; 31 * h &＃43; val[i];
}
hash &＃61; h;
}
return h;
}
可以看出&＃xff0c;相同的字符串调用 hashCode () 方法&＃xff0c;得到的值是一样的&＃xff0c;与内存地址、进程、机器无关。代码似乎很简单&＃xff0c;但是一定要归纳出来他的实现过程。
注&＃xff1a;n 为字符串长度。
如果字符串相等&＃xff0c;hashCode 必然一样&＃xff1b;如果 hashCode 一样&＃xff0c;字符串不一定相等&＃xff0c;因为计算时可能发生溢出。
为什么计算时选择 31&＃xff1f;
31 是个奇质数&＃xff0c;不大不小&＃xff0c;一般质数非常适合 hash 计算&＃xff0c;偶数相当于移位运算&＃xff0c;容易溢出&＃xff0c;数据信息丢失。如果太小&＃xff0c;则产生的哈希值区间小&＃xff1b;太大则容易溢出&＃xff0c;数据信息丢失。
31 * i &＃61;&＃61; (i <<5) - i。非常易于维护&＃xff0c;将移位代替乘除&＃xff0c;会有性能的提升&＃xff0c;并且 JVM 执行时能够自动优化成这个样子。
通过实验计算&＃xff0c;选用 31 后出现 hash 冲的概率相比于其他数字要小。
拓展阅读&＃xff1a;segmentfault.com/a/1190
最后
底层源码还是很深奥的&＃xff0c;知识都是互通的。最后物理&＃xff0c;数学都融合在一起哈哈&＃xff0c;还是很微妙的&＃xff5e;
文章如有错误&＃xff0c;欢迎指出&＃xff5e;
卑微求在看&＃xff0c;祝大佬们头发越来越茂密哈 ~
参考文章&＃xff1a;
blog.csdn.net/weixin_30zhihu.com/question/2997segmentfault.com/a/1190it1352.com/958039.htmlzhihu.com/question/2795
京公网安备 11010802041100号