与顺序无关的哈希算法
我目前正在为自定义编程语言开发一个集合库。 我已经有了几种数据类型(Collection,List,Map,Set)和它们的实现(可变和不可变),但到目前为止我所缺少的是hashCode
和equals
。 虽然列表没有问题,因为它们是有序集合,但它们对集合和地图起着特殊的作用。 如果两个集合具有相同的大小和相同的元素,则它们被认为是相等的,并且集合维护它们的顺序不应该在它们的相等性上有所不同。 由于equals-hashCode-contract, hashCode
实现也必须反映这种行为,这意味着具有相同元素但排序不同的两个集应该具有相同的哈希码。 (这同样适用于地图,这在技术上是一组键值对)
示例 (伪代码):
let set1: Set = [ "a", "b", "c" ] let set2: Set = [ "b", "c", "a" ] set1 == set2 // should return true set1.hashCode == set2.hashCode // should also return true
我如何实现一个相当好的哈希算法,上面例子中的hashCode
s返回相同的值?
JDK本身提出了以下解决此问题的方法。 java.util.Set接口的契约声明:
返回此set的哈希码值。 集合的哈希码被定义为集合中元素的哈希码的总和,其中空元素的哈希码被定义为零。 这确保了s1.equals(s2)暗示对于任何两个集合s1和s2的s1.hashCode()== s2.hashCode(),如Object.hashCode()的常规协定所要求的那样。
使用条目的哈希码的总和的替代方案是使用例如^
(XOR)运算符。
Scala语言使用Murmurhash算法的排序不变版本(参见私有scala.util.hashing.MurmurHash3
类)来实现其不可变集和类似集合的hashCode
(或##
)方法。
您可以按字母顺序计算对集合进行排序的哈希值。
有C#样本 – 我希望你能用Java翻译它:)
static String GetHash(List l) { using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create()) { return BitConverter.ToString(md5.ComputeHash(l.OrderBy(p => p).SelectMany(s => System.Text.Encoding.ASCII.GetBytes(s + (char)0)).ToArray())).Replace("-", ""); } }
这是可能实现的伪代码:
String hashCode = null; for(element : elements){ hashCode = xor(hashCode, getHashCode(element)); } return hashCode;
xor
函数应该返回一个与两个参数中最长的字符串一样长的字符串。 它将对每个中的位进行异或,直到它到达其中一个参数的末尾。 然后它将从较长的字符串中取出剩余的位并将其追加。
此实现意味着集合的hashCode将与其最长元素的hashCode一样长。 因为您正在对位进行异或,所以无论元素的顺序如何,哈希码都将是相同的。 但是,与任何哈希实现一样,将有可能发生冲突。
- Tomcat没有向Web应用程序的上下文添加尾部斜杠
- 将映射的不同值导出到另一个ObservableList的ObservableList中?
- 为什么在Java(高+低)/ 2错误但(高+低)>>> 1不是?
- 什么是Groovy / Grails / Hibernate / JBoss / Jade非常简单?
- 如何让Hibernate Tools用toString,equals和hashcode生成POJO?
- 当我有一个类的集合时,内存中存储了多少个静态final属性的副本
- “Spring事务”和“Hibernate事务”之间有什么区别
- JPQL:查询多个列时,哪种对象包含结果列表?
- 如何调整包含svg图像的按钮