Gewichtete Hash-Kombination

Question

Dies ist eine leichte Variation, wie zwei Hashes zu kombinieren, in dem ich möchte, dass der resultierende Hash mehr durch eine der Eingaben beeinflusst wird.

Für die in etwa symmetrischen Fall haben wir Algorithmen wie boost :: hash_combine:

template <class T> 
inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

ich für eine gewichtete Version suchen, vielleicht die Schnittstelle ähneln würde:

uint64_t weighted_hash_combine(uint64_t hashA, uint16 weightA, uint64_t hashB, uint16 weightB); 

Die Prämisse dass die Wahrscheinlichkeit, dass ein Bit im Ausgangs-Hash durch Änderungen in einem der Eingangs-Hashes beeinflusst wird, eine Funktion des Verhältnisses von Gewicht A zu Gewicht B ist.

Dies würde mir ermöglichen, einen Tree Hashing-Algorithmus für unsymmetrische Bäume zu verbessern. Ein einfacherer Weg zum Hasen eines Baumes ist abgedeckt here, im Wesentlichen eine Breite zuerst Traversal schiebt jeden Hash (Knoten) in einen akkumulierten Wert. Das Problem dabei ist, dass der letzte Knoten, der in den kombinierten Hash gemischt wird, einen größeren Einfluss auf das Ergebnis haben wird als der erste.

Wenn eine angemessen gewichtete Hash-Kombination verfügbar ist, kann ich die Kombination basierend auf der Anzahl der Knoten, die zu jedem Hash beigetragen haben, verzerren und hoffentlich die Fairness der Hash-Funktion verbessern.

Bisher habe ich kommen mit:

uint64_t weighted_hash_combine(uint64_t hashA, uint16 weightA, uint64_t hashB, uint16 weightB) 
{ 
    if (weightA > weightB) 
    { 
    return weighted_hash_combine(hashB,weightB,hashA,weightA); 
    } 
    uint64_t ratio = weightA/weightB; 
    uint64_t combined = hashA; 
    for (uint64_t i = 0; i < ratio; i++) 
    { 
    hash_combine(combined, hashB); 
    } 
    return combined; 
}  

Diese eher ist allerdings in numerischer Raffinesse fehlt, so hoffe ich, die Gemeinschaft erinnern kann/erfinden eine bessere Lösung. Das High-Level-Ziel besteht darin, einen Gleichheitstest zwischen den Bäumen kurzzuschließen, wenn die (Größen- oder) Hashwerte unterschiedlich sind, da sie sich oft nur in einem oder zwei Blättern unterscheiden und es keine gute Möglichkeit gibt, dies zu schätzen.

Answer 1

Hashes funktionieren nicht so. Wenn Sie Hashes richtig kombinieren, eine Änderung in entweder Hash wird garantiert, den kombinierten Hash zu ändern, und in der Tat, indem Sie entweder Hash ändern, können Sie den Wert des kombinierten Hash vollständig bestimmen.

Die am häufigsten verwendeten Mischungen sind Variationen:

h = h1*P2 + h2*P1 

wobei P1 und P2 verschiedene ungerade Primzahlen sind (oder 1). Dies würde Mod 2^32 oder Mod 2^64 abhängig von der Wortgröße ausgeführt werden, aber in jedem Fall könnten Sie h einen beliebigen Wert machen, indem Sie entweder h1 oder h2 wählen, und das wird nicht weggehen, egal wie viele andere Hashes mischen wir so ein.