Qu'est-ce que la technique de pliage dans le hachage et comment l'implémenter?

Suite aux réponses de Tony et Sumeet, j'ai fait quelques recherches supplémentaires sur le pliage des chiffres et j'ai décidé de mettre en œuvre la technique expliquée par Robert Lafore dans son livre Data Structures.

Par exemple, supposons que vous souhaitiez hacher des numéros de machine à 10 chiffres. Si la taille du tableau est 1,000, vous diviserez le nombre à 10 chiffres en trois groupes de trois chiffres et un groupe d'un chiffre. Dans notre exemple en question, le numéro de machine est 424-124-9675, donc vous calculeriez une valeur clé de 424 + 124 + 967 + 5 = 1520. Vous pouvez utiliser l' %opérateur pour couper ces sommes afin que l'indice le plus élevé soit 999. Dans ce cas 1520 % 1000 = 520,.

Si la taille du tableau est 100, vous devrez diviser la clé à 10 chiffres en cinq nombres à deux chiffres:, 42 + 41 + 24 + 96 + 75 = 278et 278 % 100 = 78.

Il est plus facile d'imaginer comment cela fonctionne lorsque la taille du tableau est un multiple de 10. Cependant, pour de meilleurs résultats, il doit être un nombre premier.

Voici le code Java de la technique de pliage des chiffres que j'ai implémentée:

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;
    }
}

J'ai trouvé la méthode de création de groupe ici . Mais cela fait des groupes de droite à gauche. Donc, j'ai utilisé une String#subString()méthode pour créer des groupes de gauche à droite.