Наилучшая строковая хэш-функция для этого примера

Question

У меня есть ключ с типом AcccAA, где A- [A ... Z] (заглавные буквы), а c - [1..9]. У меня 1500 сегментов. Теперь моя температура хэш-функция

int HashFunc(string key){ 
    int Adress = ((key[0] + key[1] + key[2] + key[3] + key[4] + key[5]) - 339) * 14; 
    return Adress; 
} 

и Excel показывают много столкновений в центре (от 400 до 900)

Пожалуйста скажите мне хэш-функцию, чтобы быть более равномерно.

Answer 1

Обычный способ построения хэш-функции в этом случае оценить некоторый многочлен с простыми коэффициентами, как этот:

int address = key[0] + 
       31 * key[1] + 
       137 * key[2] + 
       1571 * key[3] + 
       11047 * key[4] + 
       77813 * key[5]; 
return address % kNumBuckets; 

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

Для более сложной, но, возможно, лучшей хэш-функции рассмотрите возможность использования строковой хеш-функции, такой как the shift-add-XOR hash, которая также получает хорошую дисперсию, но менее интуитивно понятна.

Надеюсь, это поможет!

Answer 2

Один из способов построить гарантированный бесстолкновительную номер (который не сделает ваш хэш-таблицу столкновений бесплатно, конечно), до тех пор, как возможные ключи подходят интегральный тип (например int):

int number = (key[0] - 'A') + 26 * (
       (key[1] - '0') + 10 * (
       (key[2] - '0') + 10 * (
       (key[3] - '0') + 10 * (
       (key[4] - 'A') + 26 * (
        (key[5] - 'A') 
      ))))); 

Это работает с 26 * 10 * 10 * 10 * 26 * 26 = 17576000, который вписывается в штрафную int.

И, наконец, просто hash это целое число.