java是一个hashCode()方法,它为每个不同的对象返回不同的值,这是最有效的方法吗? 2 月,1 周 Questions & Answers 1570 我知道为每个对象返回相同的值是低效的,但是为不同的实例返回不同的值是最有效的方法吗 如果每个对象都获得不同的hashCode值,那么这不就是将它们存储在ArrayList中吗
# 1 楼答案 不,实际上不是 假设您的对象将被存储到HashMap(或Set…不重要,为了简单起见,我们将在这里使用HashMap),您希望hashCode方法以尽可能均匀地分布对象的方式返回结果 Hashcode对于不相等的对象应该是唯一的,尽管您不能保证这始终是真的。 另一方面,如果a.equals(b)为真,则a.hashCode() == b.hashCode()。这被称为Object Contract 除此之外,还有性能问题。每次两个不同的对象具有相同的哈希代码时,它们都被映射到哈希映射中的相同位置(也称为碰撞)。这意味着HashMap实现必须处理这种冲突,这比简单地存储和检索条目要复杂得多 还有很多算法依赖于值在地图上均匀分布的事实,当碰撞次数增加时,性能会迅速恶化(一些算法假设一个完美的哈希函数,这意味着不会发生碰撞,没有两个不同的值映射到地图上的同一位置) 很好的例子是概率算法和数据结构,比如Bloom Filters(用一个现在似乎很流行的例子)
# 2 楼答案 HashMap类的主要数据结构如下: Entry[] table; 需要注意的是,Entry类(这是一个实现Map.Entry的静态包保护类)实际上是一个链表样式的结构 当您尝试放置一个元素时,首先计算键的哈希代码,然后将其转换为一个桶号。“bucket”是上述数组的索引 一旦找到了bucket,就会在bucket内部进行线性搜索,以找到确切的密钥(如果你不相信我,请查看HashMap代码)。如果找到,则替换该值。如果不是,则将密钥/值对附加到该存储桶的末尾 因此,hashcode()值不必是唯一的,但是,它们越是唯一且分布越均匀,就越有可能在存储桶中均匀分布该值。如果hashcode()方法为所有实例返回相同的值,那么它们最终都会在同一个bucket中,因此会将get()方法呈现为一个长线性搜索,生成O(N) 值的分布越大,桶就越小,因此线性搜索组件就越小。唯一的值将产生常数时间查找O(1)
# 1 楼答案
不,实际上不是
假设您的对象将被存储到HashMap(或Set…不重要,为了简单起见,我们将在这里使用HashMap),您希望hashCode方法以尽可能均匀地分布对象的方式返回结果
Hashcode对于不相等的对象应该是唯一的,尽管您不能保证这始终是真的。 另一方面,如果
a.equals(b)
为真,则a.hashCode() == b.hashCode()
。这被称为Object Contract除此之外,还有性能问题。每次两个不同的对象具有相同的哈希代码时,它们都被映射到哈希映射中的相同位置(也称为碰撞)。这意味着HashMap实现必须处理这种冲突,这比简单地存储和检索条目要复杂得多
还有很多算法依赖于值在地图上均匀分布的事实,当碰撞次数增加时,性能会迅速恶化(一些算法假设一个完美的哈希函数,这意味着不会发生碰撞,没有两个不同的值映射到地图上的同一位置)
很好的例子是概率算法和数据结构,比如Bloom Filters(用一个现在似乎很流行的例子)
# 2 楼答案
HashMap类的主要数据结构如下:
需要注意的是,Entry类(这是一个实现Map.Entry的静态包保护类)实际上是一个链表样式的结构
当您尝试放置一个元素时,首先计算键的哈希代码,然后将其转换为一个桶号。“bucket”是上述数组的索引
一旦找到了bucket,就会在bucket内部进行线性搜索,以找到确切的密钥(如果你不相信我,请查看HashMap代码)。如果找到,则替换该值。如果不是,则将密钥/值对附加到该存储桶的末尾
因此,hashcode()值不必是唯一的,但是,它们越是唯一且分布越均匀,就越有可能在存储桶中均匀分布该值。如果hashcode()方法为所有实例返回相同的值,那么它们最终都会在同一个bucket中,因此会将get()方法呈现为一个长线性搜索,生成O(N)
值的分布越大,桶就越小,因此线性搜索组件就越小。唯一的值将产生常数时间查找O(1)