Was ist Falttechnik in hashing und wie es zu implementieren?

Folgenden die Antworten von Tony und Sumeet, ich habe etwas mehr Forschung auf Ziffer Falten und beschlossen, die Technik erläutert von Robert Lafore in seinen Datenstrukturen Buch.

Angenommen, Sie möchten hash-10-Ziffer Maschine zahlen. Wenn die array-Größe ist 1,000 Sie einteilen würde die 10-stellige Nummer, die in drei Gruppen von drei Ziffern und einer Gruppe von einem-stelligen. Im Beispiel in Frage, die Maschinen-Nummer ist 424-124-9675, so würden Sie berechnen einen Wert key von 424 + 124 + 967 + 5 = 1520. Sie können die % Betreiber zu trimmen solchen Summen, so der höchste index ist 999. In diesem Fall 1520 % 1000 = 520.

Wenn die array-Größe ist 100 würden Sie brauchen, um zu brechen, die 10-stellige Schlüssel in fünf zweistellige zahlen:
42 + 41 + 24 + 96 + 75 = 278, und 278 % 100 = 78.

Es ist einfacher, sich vorzustellen, wie das funktioniert, wenn die array-Größe ist ein Vielfaches von 10.
Aber für die besten Ergebnisse sollte es sein, eine Primzahl.

Hier ist der Java code der Ziffer Falt-Technik, die ich umgesetzt:

public class DigitFolder {
    public static void main(String[] args) {
        int hashVal = hashFunc(424124967);
        System.out.println(hashVal);
    }
    public static int hashFunc(int key) {
        int arraySize = 1021;
        int keyDigitCount = getDigitCount(key);
        int groupSize = getDigitCount(arraySize);
        int groupSum = 0;
        String keyString = Integer.toString(key);
        int i;
        for (i = 0; i < keyString.length(); i += groupSize) {
            if (i + groupSize <= keyString.length()) {
                String group = keyString.substring(i, i + groupSize);
                groupSum += Integer.parseInt(group);
            }
        }
        //There is no remaining part if count is divisible by groupsize.
        if (keyDigitCount % groupSize != 0) {
            String remainingPart = 
                   keyString.substring(i - groupSize, keyString.length());
            groupSum += Integer.parseInt(remainingPart);
        }
        return groupSum % arraySize;
    }
    public static int getDigitCount(int n) {
        int numDigits = 1;
        while (n > 9) {
            n /= 10;
            numDigits++;
        }
        return numDigits;
    }
}

Fand ich die Gruppe macht Methode hier. Aber es macht Gruppen von rechts nach Links. Also benutzte ich String#subString() Methode, um Links zu rechten Gruppen.

InformationsquelleAutor Yogesh Umesh Vaity