当前位置:天才代写 > tutorial > JAVA 教程 > Java理论与实践:哈希

Java理论与实践:哈希

2017-11-11 08:00 星期六 所属: JAVA 教程 浏览:511

副标题#e#

每个Java工具都有hashCode()和 equals()要领。很多类忽略(Override)这 些要领的缺省实施,以在工具实例之间提供更深条理的语义可比性。在Java理念 和实践这一部门,Java开拓人员Brian Goetz向您先容在建设Java类以有效和准 确界说hashCode()和equals()时应遵循的法则和指南。您可以在接头论坛与作者 和其它读者一同探讨您对本文的观点。(您还可以点击本文顶部或底部的接头进 入论坛。)

固然Java语言不直接支持关联数组 — 可以利用任何工具作为一个索引的数 组 — 但在根Object类中利用hashCode()要领明晰暗示期望遍及利用HashMap(及 其前辈Hashtable)。抱负环境下基于散列的容器提供有效插入和有效检索;直接 在工具模式中支持散列可以促进基于散列的容器的开拓和利用。

界说工具的相等性

Object类有两种要领来揣度工具的标识:equals()和hashCode()。一般来说 ,假如您忽略了个中一种,您必需同时忽略这两种,因为两者之间有必需维持的 至关重要的干系。非凡环境是按照equals() 要领,假如两个工具是相等的,它 们必需有沟通的hashCode()值(尽量这凡是不是真的)。

特定类的equals()的语义在Implementer的左侧界说;界说对特定类来说 equals()意味着什么是其设计事情的一部门。Object提供的缺省实施简朴引用下 面等式:

public boolean equals(Object obj) { return (this == obj); }

在这种缺省实施环境下,只有它们引用真正同一个工具时这两个引用才是相 等的。同样,Object提供的hashCode()的缺省实施通过将工具的内存地点对映于 一个整数值来生成。由于在某些架构上,地点空间大于int值的范畴,两个差异 的工具有沟通的hashCode()是大概的。假如您忽略了hashCode(),您仍旧可以使 用System.identityHashCode()要领来接入这类缺省值。

忽略 equals() — 简朴实例

缺省环境下,equals()和hashCode()基于标识的实施是公道的,但对付某些 类来说,它们但愿放宽等式的界说。譬喻,Integer类界说equals() 与下面雷同 :

public boolean equals(Object obj) {
return (obj instanceof Integer
&& intvalue() == ((Integer) obj).intvalue());
}

在这个界说中,只有在包括沟通的整数值的环境下这两个Integer工具是相等 的。团结将不行修改的Integer,这使得利用Integer作为HashMap中的要害字是 切实可行的。这种基于值的Equal要领可以由Java类库中的所有原始封装类利用 ,如Integer、Float、Character和Boolean以及String(假如两个String工具包 含沟通顺序的字符,那它们是相等的)。由于这些类都是不行修改的而且可以实 施hashCode()和equals(),它们都可以做为很好的散列要害字。

为什么忽略 equals()和hashCode()?

假如Integer不忽略equals() 和 hashCode()环境又将如何?假如我们从未在 HashMap或其它基于散列的荟萃中利用Integer作为要害字的话,什么也不会产生 。可是,假如我们在HashMap中利用这类Integer工具作为要害字,我们将不可以或许 靠得住地检索相关的值,除非我们在get()挪用中利用与put()挪用中极其雷同的 Integer实例。这要求确保在我们的整个措施中,只能利用对应于特定整数值的 Integer工具的一个实例。不消说,这种要领极不利便并且错误几回。

Object的interface contract要求假如按照 equals()两个工具是相等的,那 么它们必需有沟通的hashCode()值。当其识别本领整个包括在equals()中时,为 什么我们的根工具类需要hashCode()?hashCode()要领纯粹用于提高效率。Java 平台设计人员估量到了典范Java应用措施中基于散列的荟萃类(Collection Class)的重要性–如Hashtable、HashMap和HashSet,而且利用equals()与很多 工具举办较量在计较方面很是昂贵。使所有Java工具都可以或许支持 hashCode()并 团结利用基于散列的荟萃,可以实现有效的存储和检索。

实施equals()和hashCode()的需求

实施equals()和 hashCode()有一些限制,Object文件中罗列出了这些限制。 出格是equals()要领必需显示以部属性:

Symmetry:两个引用,a和 b,a.equals(b) if and only if b.equals(a)

Reflexivity:所有非空引用, a.equals(a)

Transitivity:If a.equals(b) and b.equals(c), then a.equals(c)

Consistency with hashCode():两个相等的工具必需有沟通的hashCode()值

Object的类型中并没有明晰要求equals()和 hashCode() 必需一致 — 它们 的功效在随后的挪用中将是沟通的,假设“不改变工具相等性较量中利用的任何 信息。”这听起来象“计较的功效将不改变,除非实际环境如此。”这一恍惚声 明凡是表明为相等性和散列值计较应是工具的可确定性成果,而不是其它。


#p#副标题#e#

工具相等性意味着什么?

#p#分页标题#e#

人们很容易满意Object类类型对equals() 和 hashCode() 的要求。抉择是否 和如何忽略equals()除了判定以外,还要求其它。在简朴的不行修值类中,如 Integer(事实上是险些所有不行修改的类),选择相当明明 — 相等性应基于基 本工具状态的相等性。在Integer环境下,工具的独一状态是根基的整数值。

对付可修改工具来说,谜底并不老是如此清楚。equals() 和hashCode() 是 否应基于工具的标识(象缺省实施)或工具的状态(象Integer和String)?没有简 单的谜底 — 它取决于类的打算利用。对付象List和Map这样的容器来说,人们 对此争论不已。Java类库中的大大都类,包罗容器类,错误呈此刻按照工具状态 来提供equals()和hashCode()实施。

假如工具的hashCode()值可以基于其状态举办变动,那么当利用这类工具作 为基于散列的荟萃中的要害字时我们必需留意,确保当它们用于作为散列要害字 时,我们并不答允变动它们的状态。所有基于散列的荟萃假设,当工具的散列值 用于作为荟萃中的要害字时它不会改变。假如当要害字在荟萃中时它的散列代码 被变动,那么将发生一些不行预测和容易夹杂的功效。实践进程中这凡是不是问 题 — 我们并不常常利用象List这样的可修改工具做为HashMap中的要害字。

一个简朴的可修改类的例子是Point,它按照状态来界说equals()和 hashCode()。假如两个Point 工具引用沟通的(x, y)座标,Point的散列值来历 于x和y座标值的IEEE 754-bit暗示,那么它们是相等的。

对付较量巨大的类来说,equals()和hashCode()的行为大概甚至受到 superclass或interface的影响。譬喻,List接口要求假如而且只有另一个工具 是List,并且它们有沟通顺序的沟通的Elements(由Element上的Object.equals () 界说),List工具便是另一个工具。hashCode()的需求更非凡–list的 hashCode()值必需切合以下计较:

hashCode = 1;
Iterator i = list.iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}

不只仅散列值取决于list的内容,并且还划定了团结各个Element的散列值的 非凡算法。(String类划定雷同的算法用于计较String的散列值。)

编写本身的equals()和hashCode()要领

忽略缺省的equals()要领较量简朴,但假如不违阻挡称(Symmetry)或通报 性(Transitivity)需求,忽略已经忽略的equals() 要领极其棘手。当忽略 equals()时,您应该老是在equals()中包罗一些Javadoc注释,以辅佐那些但愿 可以或许正确扩展您的类的用户。

作为一个简朴的例子,思量以下类:

class A {
final B someNonNullField;
C someOtherField;
int someNonStateField;
}

我们应如何编写该类的equals()的要领?这种要领合用于很多环境:

public boolean equals(Object other) {
// Not strictly necessary, but often a good optimization
if (this == other)
return true;
if (!(other instanceof A))
return false;
A otherA = (A) other;
return
(someNonNullField.equals(otherA.someNonNullField))
&& ((someOtherField == null)
? otherA.someOtherField == null
: someOtherField.equals(otherA.someOtherField)));
}

此刻我们界说了equals(),我们必需以统一的要领来界说hashCode()。一种 统一但并不老是有效的界说hashCode()的要领如下:

public int hashCode() { return 0; }

这种要领将生成大量的条目并显著低落HashMaps的机能,但它切合类型。一 个更公道的hashCode()实施应该是这样:

public int hashCode() {
int hash = 1;
hash = hash * 31 + someNonNullField.hashCode();
hash = hash * 31
+ (someOtherField == null ? 0 : someOtherField.hashCode());
return hash;
}

留意:这两种实施都低落了类状态字段的equals()或hashCode()要领必然比 例的计较本领。按照您利用的类,您大概但愿低落superclass的equals()或 hashCode()成果一部门计较本领。对付原始字段来说,在相关的封装类中有 helper成果,可以辅佐建设散列值,如Float.floatToIntBits。

编写一个完美的equals()要领是不现实的。凡是,当扩展一个自身忽略了 equals()的instantiable类时,忽略equals()是不切实际的,并且编写将被忽略 的equals()要领(如在抽象类中)差异于为详细类编写equals()要领。关于实例以 及说明的更具体信息请参阅Effective Java Programming Language Guide, Item 7 (参考资料) 。

#p#副标题#e#

有待改造?

将散列法构建到Java类库的根工具类中是一种很是明智的设计折衷要领 — 它使利用基于散列的容器变得如此简朴和高效。可是,人们对Java类库中的散列 算法和工具相等性的要领和实施提出了很多品评。java.util中基于散列的容器 很是利便和轻便易用,但大概不合用于需要很是高机能的应用措施。固然个中大 部门将不会改变,但当您设计严重依赖于基于散列的容器效率的应用措施时必需 思量这些因素,它们包罗:

太小的散列范畴。利用int而不是long作为hashCode()的返回范例增加了散列 斗嘴的几率。

#p#分页标题#e#

糟糕的散列值分派。短strings和小型integers的散列值是它们本身的小整数 ,靠近于其它“相近”工具的散列值。一个循规导矩(Well-behaved)的散列函 数将在该散列范畴内更匀称地分派散列值。

无界说的散列操纵。固然某些类,如String和List,界说了将其Element的散 列值团结到一个散列值中利用的散列算法,但语言类型不界说将多个工具的散列 值团结到新散列值中的任何核准的要领。我们在前面编写本身的equals()和 hashCode()要领中接头的List、String或实例类A利用的诀窍都很简朴,但算术 上还远远不足完美。类库不提供任何散列算法的利便实施,它可以简化更先进的 hashCode()实施的建设。

当扩展已经忽略了equals()的 instantiable类时很难编写equals()。当扩展 已经忽略了equals()的 instantiable类时,界说equals()的“显而易见的”方 式都不能满意equals()要领的对称或通报性需求。这意味着当忽略equals()时, 您必需相识您正在扩展的类的布局和实施具体信息,甚至需要袒露根基类中的机 密字段,它违反了面向工具的设计的原则。

竣事语

通过统必然义equals()和hashCode(),您可以晋升类作为基于散列的荟萃中 的要害字的利用性。有两种要领来界说工具的相等性和散列值:基于标识,它是 Object提供的缺省要领;基于状态,它要求忽略equals()和hashCode()。当工具 的状态变动时假如工具的散列值产生变革,确信当状态作为散列要害字利用时您 不答允更变动其状态。

 

    关键字:

[contact-form-7 id="17097" title="form2"]天才代写-代写联系方式