·

搜索了一下,https://cloud.tencent.com/developer/article/1622192。

这个时候看文档/源码比较好,你可以按照文中的方法看你下你使用的 Java 中是如何实现的。

3.2 的问题很简单啊,既然它是哈希计算的,那么任何东西都可能映射到同一个位置吧。

a 和 b 在哈希表的同一个位置不代表它们的哈希值一样,只能说明它们的哈希值会映射到同一个位置,这个和映射算法以及 set 内部桶的数量都是有关系的。

Replies
7

哈希表中的位置是上面红框的if语句确定的吗?我的理解,如果hash值不同,那应该在哈希表中的位置也肯定不同啊?

而且为甚什么我增加了一个断点,第二个dog对象就跑到lucy下面去了,不增加这个断点就跟lucy没关系?

红框里是根据对象的哈希值确定对象的插入位置,可以看出使用的是常规的取余算法。

你对哈希表的理解是错误的,哈希表一般使用数组来存放对象,这个数组一定是有限的,一般大小为math,会随着已有元素的数量增加而动态扩展,扩展时机和定义的 load factor 有关。在你截图里可以看到三个元素的时候 set 内部的数组大小是 16。而哈希值一般是计算得到一个 64 位的整数。

64 位的哈希值如何确定为 0~15 的数组索引?也就是将 "lucky" 放到 13 的位置是怎么确定下来的?答案是取余。i = (n - 1) & hash

那么另一个自然的问题是,哈希值分别为 13 和 29 的两个对象,就会映射到哈希表内部数组的同一个位置。数组一个位置只能放置一个元素,怎么处理?

处理方法可以划分为开放定址法和拉链法。哈希表内部数据结构没重整时,开放定址法的元素只能标记删除,所以通用的哈希表实现一般采用第二种方法,也就是在数组的每个元素处放入一个链表,所有映射到同一位置的对象都放到链表里去。

这里讨论的 set 正是这种情况,在这种情况下,哈希值不同的对象有可能在同一个链表中。这是第一个问题的答案。

第二个问题涉及到默认的哈希值是如何实现的。就从上一回复中的网页来讨论吧,根据该网页,OpenJDK 8 中,默认的 hashCode 实现是基于线程状态的数字。不知道你用的是什么版本,但如果这是跟程序状态有关的一个数字,在 release 状态下和 debug 状态下某个对象的哈希值不同是完全可能的,这完全是 jvm 实现的问题。

你可以多运行尝试几次,说不定每次新对象的位置都不同呢?

看不懂了,我再学学吧 joy

谢谢

你去学习一下数据结构,先对哈希表有个概念 joy

路漫漫其修远兮 sweat_smile

加油 +1