Что такое технология складывания в хешировании и как ее реализовать?

Question

Я услышал на семинаре структур данных, что мы можем разбить ключ на группы цифр, а затем добавить группы. Это гарантирует, что все цифры вносят хэш-код. Количество цифр в группе соответствует размеру массива.

Например, у меня есть номер машины: 424-124-9675, как мне сделать хеш-функцию, используя технику Складывания?

Answer 1

После ответов от Tony и Sumeet, я сделал еще несколько исследований по складыванию цифр и решил применить технику, описанную Робертом Лафоу в своей книге Data Structures.

Например, предположим, что вы хотите присвоить 10-значные номера машин. Если размер массива равен 1,000, вы разделите 10-значное число на три группы из трех цифр и одну группу из одной цифры. В приведенном ниже примере номер машины равен 424-124-9675, поэтому вы вычислили значение ключа 424 + 124 + 967 + 5 = 1520. Вы можете использовать оператор % для обрезки таких сумм, поэтому самый высокий индекс - 999. В этом случае 1520 % 1000 = 520.

Если размер массива 100, вам нужно будет сломать ключ 10-значный в пять двузначных чисел: 42 + 41 + 24 + 96 + 75 = 278 и 278 % 100 = 78.

Легче представить, как это работает, когда размер массива кратен 10. Однако для достижения наилучших результатов это должно быть простое число.

Вот код Java техники цифр откидной я реализовал:

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

Я нашел группу метода here решений. Но это делает группы право налево. Итак, я использовал метод String#subString(), чтобы сделать группы слева направо.

Answer 2

Дано 424-124-9675, вы сами решаете, где хотите разбить его на группы. Например:

• каждые 3 цифры слева направо: хэш = 424 + 124 + 967 + 5

• каждые 3 цифры от правой: хэш = 675 + 249 + 241 + 4

• где черточки: хэш = 424 + 124 + 9675

Это очень слабый способ хэширования, хотя - очень коллизия склонная.

Answer 3

Существует 2 типа методов складывания Fold shift и Fold boundary.

Fold Сдвиг

Вы делите ключ в части, размер которого соответствует размеру требуемого адреса. Детали просто добавляются, чтобы получить требуемый адрес.

Ключ: 123456789 и размер требуемого адреса - 3 цифры.

123 + 456 + 789 = 1368. Чтобы уменьшить размер до 3, удаляются либо 1, либо 8, соответственно, клавиша будет 368 или 136 соответственно.

Fold Boundary

Вы снова разделить ключ на части, размер которого соответствует размеру требуемых address.but теперь вы ходатайствующих складывание, за исключением средней части, если его там.

Ключа: 123456789 и размер требуемого адреса 3 цифра

321 (складной применяется) + 456 + 987 (складной применяется) = тысяча семьсот шестьдесят-четырь (выбросить 1 или 4)