2021年4月22日

为什么重写 equals 时必须重写 hashCode

1 equals 的作用

equals() 方法,用于判断两个对象是否相等。

未重写 equals 方法时,使用 Object 类的 equals,等效于 ==,即判断两个对象是否为同一个对象(内存地址相同)。

当我们需要比较两个对象的内容是否相等时,要重写 equals 方法。例如 String 类中的 equals:

2 hashCode 的作用

hashCode() 的作用是获取哈希码,也称为散列码;它实际上是返回一个 int 整数。这个哈希码的作用是确定该对象在哈希表中的索引位置。

未重写 hashCode 时,使用 Object 类的 hashCode。它是一个本地方法,通常是将对象的内存地址转换为一个整数后返回。

3 为什么重写 equals 时必须重写 hashCode

hashCode 的协议中有这样的规定:

  1. 两个相同的对象,hashCode 必然相同;
  2. 两个不同的对象,hashCode 有可能相同(绝大多数时候都是不同的)。

因此,重写 equals 之后,必须重写 hashCode(而不能继续使用默认实现),以确保符合协议的要求。

4 加餐:hash 碰撞

4.1 什么是 hash 碰撞

如果不同的输入得到了同一个哈希值,就发生了“hash 碰撞”(collision)。

某些场景下,发生 hash 碰撞是很危险的。例如,很多网络服务会使用哈希函数产生 token,来标识用户的身份和权限。一旦产生 hash 碰撞,系统会把原本不同的两个用户当成同一个用户,造成安全隐患。

4.2 HashMap 中的 hash 碰撞

HashMap 中也存在 hash 碰撞,这是 by design 的,正常情况下不会有问题。

HashMap 在添加元素的时候,根据元素的 hash 值,把它放到相应的桶中。当发生 hash 碰撞时,即这个桶里已经存放了其他不同的元素,新元素会插入到原来元素的后面。也就是说,HashMap 的桶里,存放的是一个链表(当存放元素的个数超过阈值时,链表会变成树)。

详见 HashMap.putVal() 方法。

4.3 哈希洪水攻击

HashMap 把元素尽可能散列到不同的桶中,使得每个桶中尽可能均匀分布少量元素,这样一来,查询效率非常高。

由于不同的元素有可能产生相同的 hash 值(而且概率较大),如果有人故意造出大量具有相同 hash 值的元素,塞给 HashMap,那么 HashMap 永远只会使用一个桶,查询效率将由 O(1) 退化成 O(n) 或 O(logn)。

这样的操作就叫洪水攻击。

 


ref:

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注


*