Hash aus 2 Integern

Hi,

ich habe 2 integer (signed).

Die Frage ist, ob dieser Hash kollisionsfrei ist?

int z = 29;
int t = -29456;
(static_cast<int64_t>(t) << (std::numeric_limits<int>::digits + 1)) ^ z;

Negative Zahlen werden ja als 2er Kompiment dargestellt.

Da nicht klar ist, wie groß int ist, kann die Frage nicht allgemein beantwortet werden. Wenn int z.B. ebenfalls 64 bit lang ist und du einen 64-bit-Wert << 64 rechnest, ist das Ergebnis undefiniert. Und UB ist toll, oder?

boost::hash_combine()

Dann benutze ich statt int den Type "int32_t".

Der ist garantiert 32-Bit groß.

boost::hash_combine() sieht mir zu schwergewichtig aus. Ich brauche eine schnelle Operation.

Dein Ergebnis ist dann immer noch undefiniert, weil left-shiften von negativen Werten undefiniert ist.

Du müsstest also in uint64_t casten.

Wenn du zwei n Bit breite Werte hast, kannst du die natürlich immer kollisionsfrei in einer 2*n Bit breiten Variablen speichern. Aber der Punkt eines Hashes ist doch, dass man den gerade klein hält und vor allem auch möglichst alle Bits darin irgendwie verwurstet. Bei dir hängt die eine Seite der neuen Variablen dann aber nur von einem Input ab.

boost::hash_combine() sieht mir zu schwergewichtig aus

Hast du das gemessen oder glaubst du nur? Wozu willst du das überhaupt benutzen?

Ethon

Verwendet boost.combine nicht sogar das Java-übliche Hashing ala

hash = value1;
hash = hash * 31 + value2;

Egal. Nimm halt einfach den FNV-Hash abgewandelt dafür her:

std::uint64_t hash(std::uint32_t a, std::uint32_t b) {
    std::uint64_t h = 14695981039346656037LL;
    h = (h ^ a) * 1099511628211LL;
    h = (h ^ b) * 1099511628211LL;
    return h;
}

Ist mir auch nicht 100% klar, welche Anforderungen du an den Hash stellst.

std::uint64_t hash = (a << 32) | b;

würde es wohl für die meisten Einsatzzwecke auch tun.