Niezależny od zamówienia algorytm skrótu

Question

Obecnie pracuję nad biblioteką kolekcji dla mojego niestandardowego języka programowania. Mam już kilka typów danych (Kolekcja, Lista, Mapa, Zestaw) i implementacje dla nich (zmienne i niezmienne), ale dotychczas brakowało mi hashCode i equals. Chociaż nie są one problemem dla list, ponieważ są one uporządkowanymi kolekcjami, odgrywają szczególną rolę dla zestawów i map. Dwa zestawy są uważane za równe, jeśli mają ten sam rozmiar i te same elementy, a kolejność, w jakiej zestawy je zachowują, nie powinna mieć wpływu na ich równość. Z powodu równości-hashCode-kontrakt implementacja hashCode musi również odzwierciedlać to zachowanie, co oznacza, że ​​dwa zestawy z tymi samymi elementami, ale z inną kolejnością, powinny mieć ten sam kod skrótu. (To samo dotyczy Maps, które są technicznie Zestaw klucz-wartość-parach)

przykładu (Pseudokod):

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 

Jak zaimplementować całkiem dobry algorytm mieszania dla których hashCode s w powyższym przykładzie zwraca tę samą wartość?

Answer 1

Sam JDK proponuje następujące rozwiązanie tego problemu. Umowa interfejsu java.util.Set określa:

Powoduje zwrócenie wartości skrótu dla tego zestawu. Kod skrótu zestawu jest zdefiniowany jako suma kodów skrótu elementów w zestawie, gdzie kod skrótu elementu zerowego jest zdefiniowany jako zero. Zapewnia to, że s1.equals (s2) implikuje, że s1.hashCode() == s2.hashCode() dla dowolnych dwóch zestawów s1 i s2, zgodnie z wymaganiami generalnej umowy Object.hashCode().

Alternatywą dla wykorzystania sumy kodów hash wpisów jest użycie na przykład operatora ^ (XOR).

język Scala używa zamawiania wersji niezmienny algorytmu na Murmurhash (por prywatnej scala.util.hashing.MurmurHash3 klasy) w celu wdrożenia metody hashCode (lub ##) jego immutable sets i podobnych zbiorów.

Answer 2

Oto pseudokod do ewentualnej realizacji:

String hashCode = null; 
for(element : elements){ 
    hashCode = xor(hashCode, getHashCode(element)); 
} 
return hashCode; 

Funkcja xor powinien zwrócić ciąg znaków, który jest tak długo, jak najdłużej z dwoma argumentami. Będzie XOR bity w każdym, aż dojdzie do końca jednego z argumentów. Następnie pobiera pozostałe bity z dłuższego łańcucha i dołącza je.

Ta implementacja będzie oznaczać, że hashCode zestawu będzie tak długi, jak hashCode jego najdłuższego elementu. Ponieważ wyszukujesz bity, na końcu hashcode będzie taki sam niezależnie od kolejności twoich elementów. Jednak, podobnie jak w przypadku każdej implementacji mieszania, będzie możliwość kolizji.

Answer 3

Możesz obliczyć sumę kontrolną, sortując swoją kolekcję w kolejności alfabetycznej.

Nie jest próbka C# - Mam nadzieję, że można go przetłumaczyć w Javie :)

static String GetHash(List<String> 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("-", ""); 
    } 
}