Gute Hash-Funktion für eine Liste von 2-D-Positionen?

Question

Ich habe eine Reihe von Objekten, deren einziger unterschiedlicher interner Zustand eine Liste fester Länge (oder was auch immer) von 2-D-Positionen (2 Ganzzahlen) ist. Das heißt, sie haben alle die gleiche Anzahl von Elementen mit (potenziell) unterschiedlichen 2-d-Werten.

Ich werde ständig neue Instanzen mit allen vorher existierenden vergleichen, daher ist es sehr wichtig, dass ich eine gute Hashing-Funktion schreibe, um die Anzahl der Vergleiche zu minimieren.

Was würden Sie mir empfehlen, um sie zu haschen?

Answer 1

Der Sinn der Wahl von 31 als Primzahl besteht darin, dass man mit einer Bitverschiebung und einer Subtraktion multiplizieren kann.

Nehmen wir an, dass es sich um eine Punktklasse handelt:

class Point {
    public final int x;
    public final int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;
        hash = ((hash + x) << 5) - (hash + x);
        hash = ((hash + y) << 5) - (hash + y);
        return hash;
    }
}

Der Sinn der Wahl von 31 als Primzahl besteht darin, dass man mit einer Bitverschiebung und einer einzigen Subtraktionsoperation multiplizieren kann. Beachten Sie, dass eine Bitverschiebung um 5 der Multiplikation mit 32 entspricht, und die Subtraktion entspricht der Multiplikation mit 31. Diese beiden Operationen sind viel effizienter als eine einzige, echte Multiplikation.

Und Ihr Ziel ist dann:

class TheObject
{
    private final java.util.List<Point> points;

    public TheObject(List<Point> points)
    {
        this.points = points;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;int tmp = 0;
        for (Point p : points)
        {
            tmp = (hash + p.hashCode());
            hash = (tmp << 5) - tmp;
        }
        return hash;
    }
}

Answer 2

Wie wäre es mit einer Art binärem Suchbaum?

Um den Vergleich in Pseudocode auszudrücken:

position1 > position2 := 
   (position1.x > position2.x) || 
   ((position1.x == position2.x) && (position1.y > position2.y))

list1.x > list2.x := {
    for (i in 0...n) 
        if (list1[i] > list2[i]) return true;
        else if (list1[i] > list2[i]) return false;
    return false;
}

where n ist natürlich die Länge der Listen.

Ich bin kein großer Java-Profi und kenne mich mit der Standardbibliothek nicht wirklich aus, aber ich nehme an, Sie könnten den Baum einfach selbst schreiben. Implementieren Sie eine getID-Methode, die versucht, diese Liste zu finden oder sie anderweitig einzufügen, und dazu eine eindeutige ID, die Sie durch einfaches Inkrementieren eines Zählers erhalten können.

Auf diese Weise erhalten Sie eine ID (anstelle eines Hash), die keinerlei Kollisionen aufweist. Im schlimmsten Fall ist der Vergleich von 2 Listen O(n) Somit ist eine Suche/Einfügung O(n) * O(log(m)) (unter der Annahme, dass der Baum ausgeglichen ist), wobei m ist die Gesamtzahl aller Listen.

Die Ermittlung einer ID ist also im schlimmsten Fall teurer als Hashing, aber wie gesagt, das Ergebnis ist garantiert eindeutig.

Über den Durchschnitt kann ich wenig sagen, da Sie keine Zahlen nennen. Eigentlich bin ich überrascht, dass Sie keinen direkten Vergleich machen wollen, da ich davon ausgehe, dass die Wahrscheinlichkeit, dass 2 Positionen gleich sind, weniger als 1 % beträgt, so dass ein Listenvergleich etwa O(1) ist, da die Wahrscheinlichkeit, dass Sie 5 Einträge vergleichen müssen, wirklich gering ist.

Es ist auch nicht klar, ob die Listen veränderbar sind oder nicht, denn wenn sie unveränderbar sind, sollten die Kosten kaum ins Gewicht fallen.

Answer 3

Je nach der Größe der Ganzzahlen sollten Sie die erste Koordinate mit der maximal möglichen Koordinate multiplizieren und die zweite addieren. Wenn beispielsweise X und Y positiv sind und eine Grenze von 256 haben, können Sie X*256+Y für Ihre Hash-Funktion verwenden. Wenn X und Y auch negativ sein können, sollten Sie sie zuerst ausgleichen, damit sie nicht negativ sind. Wenn die Multiplikation von X mit dem Maximalwert den Integer-Wert übersteigt, sollten Sie einen Multi-Int-Hash-Wert oder vielleicht mod oder bitweise und das Ergebnis mit UINT_MAX verwenden.