关于HashSet添加数据在table表中位置的问题,以及对象的hash值计算是按地址值计算吗的问题
6月10号在Java交流频道请教了一个问题,感谢@库米豪斯巴达锅铲祖师 和@HD Superman 的回复.
这里详细把问题描述一下,希望能够讨论一下.
1. 运行情况
1.1 代码
ja
红框里是根据对象的哈希值确定对象的插入位置,可以看出使用的是常规的取余算法。
你对哈希表的理解是错误的,哈希表一般使用数组来存放对象,这个数组一定是有限的,一般大小为,会随着已有元素的数量增加而动态扩展,扩展时机和定义的 load factor 有关。在你截图里可以看到三个元素的时候 set 内部的数组大小是 16。而哈希值一般是计算得到一个 64 位的整数。
64 位的哈希值如何确定为 0~15 的数组索引?也就是将 "lucky" 放到 13 的位置是怎么确定下来的?答案是取余。i = (n - 1) & hash
。
那么另一个自然的问题是,哈希值分别为 13 和 29 的两个对象,就会映射到哈希表内部数组的同一个位置。数组一个位置只能放置一个元素,怎么处理?
处理方法可以划分为开放定址法和拉链法。哈希表内部数据结构没重整时,开放定址法的元素只能标记删除,所以通用的哈希表实现一般采用第二种方法,也就是在数组的每个元素处放入一个链表,所有映射到同一位置的对象都放到链表里去。
这里讨论的 set 正是这种情况,在这种情况下,哈希值不同的对象有可能在同一个链表中。这是第一个问题的答案。
第二个问题涉及到默认的哈希值是如何实现的。就从上一回复中的网页来讨论吧,根据该网页,OpenJDK 8 中,默认的 hashCode
实现是基于线程状态的数字。不知道你用的是什么版本,但如果这是跟程序状态有关的一个数字,在 release 状态下和 debug 状态下某个对象的哈希值不同是完全可能的,这完全是 jvm 实现的问题。
你可以多运行尝试几次,说不定每次新对象的位置都不同呢?