Sollte Gleichheit gleiche Hashwerte implizieren?

Question

Ich arbeite gerade an einem Graph-Datentyp, und in diesem Kontext habe ich viel über semantische Probleme bezüglich Identität und Gleichheit nachgedacht.

Meine Situation ist jetzt das folgende. Ich habe einen Vertex Typ:

final class Vertex<T>: Hashable { 

    static func ==(lhs: Vertex, rhs: Vertex) -> Bool { 
    return lhs === rhs 
    } 

    var value: T 

    var hashValue: Int { 
    return ObjectIdentifier(self).hashValue 
    } 

} 

Wie Sie Gleichheit von Identität bestimmt wird, sehen. Ich habe dies aus Gründen getan, die für den Graph-Datentyp spezifisch sind, aber was im Grunde genommen darauf hinausläuft, ist die Tatsache, dass Scheitelpunkte anhand ihrer Identität betrachtet und daher nur dann als gleich angesehen werden, wenn sie identisch sind (identischer) Scheitelpunkt .

Jetzt wird der Hash-Wert auch durch die Identität bestimmt (unter Verwendung der ObjectIdentifier). Dies schien der einfachste Weg zu sein, einen Hash-Wert zu erhalten, und schien auch gut mit dem Konzept der Gleichheit für diesen Typ übereinzustimmen.

Aber das hat mir denken ...
Wäre es semantisch „falsch“ (oder unlogisch, wenn man so will) durch den Hash-Wert zu bestimmen, sagen wir mal, die value Eigenschaft (wenn T-Hashable angepasst).
In diesem Fall könnten zwei Vertex s konsistent gleiche Hash-Werte haben (nicht nur für einen Aufruf des Programms), ohne als gleich angesehen zu werden. Und das scheint nicht richtig zu sein.

Also wiederum: Ist es vernünftig zu sagen, dass die Gleichheit der Instanzen Gleichheit ihrer Hash-Werte implizieren sollte?

Answer 1

Aus der Dokumentation für Hashable:

„A Hashwert, der bereitgestellt durch eine Art HashValue Eigenschaft, eine ganze Zahl, die gleich für beliebige zwei Instanzen, die in gleicher Weise vergleichen ist Das heißt, ein für die zwei Fälle. und b des gleichen Typs, wenn a == b dann a.hashValue == b.hashValue. Das Gegenteil ist nicht wahr: Zwei Instanzen mit gleichen Hash-Werten sind nicht notwendigerweise gleich. "

Mit anderen Worten, wenn == kehrt true, hashValue müssen den gleichen Wert für beide Objekte zurück.

Answer 2

Die Anforderungen für Hashing sind, dass, wenn zwei Werte a und b die gleichen sind, dann a.hashvalue == b.hashvalue. Das bedeutet jedoch nicht, dass das Gegenteil der Fall ist. Wenn zwei Hash-Werte identisch sind, ist es möglich, dass die Hash-Elemente nicht identisch sind. Also wenn Sie das sagen

• "Gleichheit der Instanzen sollte Gleichheit ihrer Hash-Werte implizieren?" Das ist eigentlich eine Voraussetzung.
• "zwei Vertexe könnten konsistent gleiche Hash-Werte haben (nicht nur für einen Aufruf des Programms), ohne als gleich betrachtet zu werden. Und das scheint nicht richtig" - tatsächlich ist dies möglich.