顺序无关的哈希算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我目前正在为我的自定义编程语言开发一个集合库。我已经有几种数据类型（Collection，List，Map，Set）和它们的实现（可变和不可变），但是到目前为止我缺少的是hashCodeand

equals。尽管这些对于列表来说是没有问题的，因为它们是有序的集合，但是它们对于集合和地图起着特殊的作用。如果两个Set具有相同的大小和相同的元素，则认为它们是相等的，并且Sets维护它们的顺序不应在其相等性上有所不同。由于equals-

hashCode-

contract，hashCode实现还必须反映此行为，这意味着具有相同元素但顺序不同的两个集合应具有相同的哈希码。（地图也适用，从技术上讲，这是一组键值对）

（伪代码）：

let set1: Set<String> = [ "a", "b", "c" ]
let set2: Set<String> = [ "b", "c", "a" ]
set1 == set2       // should return true
set1.hashCode == set2.hashCode // should also return true

如何hashCode在上例中的s返回相同值的情况下，实现一种合理的算法" title="哈希算法">哈希算法？

回答：

JDK本身针对此问题提出了以下解决方案。java.util.Set接口的协定规定：

返回此集合的哈希码值。集合的哈希码定义为集合中元素的哈希码之和，其中空元素的哈希码定义为零。这可以确保s1.equals（s2）暗示了Object.hashCode（）的一般合同要求的任意两个s1和s2集的s1.hashCode（）==

s2.hashCode（）。

使用条目的哈希码总和的替代方法是使用^（XOR）运算符。

Scala语言使用Murmurhash算法的不变序版本（请参阅私有scala.util.hashing.MurmurHash3类）来实现其不可变集和类似集合的hashCode（或##）方法。

以上是 顺序无关的哈希算法 的全部内容， 来源链接： utcz.com/qa/399816.html

回到顶部