Клавиши таблицы Java Hash. Преобразование строковых ключей в ключи int

Question

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

Однако я не знаю, как работает преобразование из строкового ключа в ключ int. Это код, который я взял из своего учебника:

public int hashVal(String key, int tableSize) 
{ 
    int hashKey= 0; 
    int temp = 0; 
    for(int i=0;i<key.length();i++) 
    { 
     temp = 37*temp+(int)key.charAt(i); 
    } 
    temp%=tableSize; 
    if (temp<0) 
    { 
     temp+=tableSize; 
    } 
    hashKey=temp; 
    return hashKey; 
} 

Объяснение или простой код были бы очень оценены.

Answer 1

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

Итак, для строки мы используем все символы в строке для вычисления значения хэша. Аналогично для объекта рекомендуется использовать все значимые поля в объекте при вычислении хеш-значения.

Java, аналогичным образом использует вариацию вашего учебника.

Вопрос: Почему в вашем учебнике используется 37? [Java аналогичным образом использует вариацию вашего учебного кода с 31 как постоянное значение]

Ответ: Использование простых чисел, по-видимому, приводит к лучшему распределению хэш-значений по всей таблице.

Answer 2

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

Предлагаю две ревизии: используйте 37 * (int)key.charAt(i) + hash и избавьтесь от переменной темпа.

Это, таким образом, становится:

public static int hashVal(String s, int max) { 
    int hash = 0; 
    for(Char c : s.toCharArray()) 
     hash = Math.abs((hash + 37*(int)c) % max); 
    return hash; 
}