Алгоритм свертывания цифр для хэш-таблицы - PullRequest
Новая
       25

Алгоритм свертывания цифр для хэш-таблицы

0 голосов
/ 26 ноября 2018

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

int Hash(char* key, int keyLength, int tableSize)
{
     int i = 0;
     int hashValue= 0;

     for(i=0; i<keyLenth; i++)
        hashValue += key[i];

     return hashValue % tableSize;
}

Замените каждый элемент строки кодом ASCII (0-127) и добавьте эти значения отдельно.

введите описание изображения здесь

Но есть одна проблема.Если размер хеш-таблицы равен 12289, а максимальная длина строки составляет 10 цифр, хеш-функция возвращает 10X127 = 1270, она возвращает только адрес в диапазоне от 0 до 1270, поэтому адрес в диапазоне от 1271 до 12288 вообще не используется,

Размер хеш-таблицы 12289 составляет 11000000000001 в двоичном формате.Это всего 14 бит.С другой стороны, максимальное значение адреса 1270 составляет 10011110110, поэтому используются только 11 битов.Этот факт показывает, что три бита никогда не используются.Таким образом, каждый раз, когда цикл функции Hash повторяется, мы перемещаем hashValue на 3 бита влево и добавляем следующий код ASCII.Это теоретически сможет хэшировать все адреса.

Мой вопрос: зачем мне сдвигать 3 бита влево?Есть ли причина, по которой я не должен сдвигать его вправо?

1 Ответ

0 голосов
/ 26 ноября 2018
  1. Я не уверен, что вы скопировали свой код или просто набросали его, но в настоящее время ваш код - это не хэш-код, а просто функция передачи последнего кода ASCII.Я предполагаю, что вы имели в виду XOR значений?
  2. Не совсем ясно, какова ваша предложенная функция, поэтому вы должны уточнить, однако, если вы просто XOR для текстовых данных, вы не делаете оченьхорошая хеш-функция.Предположим, ваши данные оказались только четными цифрами?И есть другие вырождения в ASCII.Я предполагаю, что hashValue ^ = key [i]
  3. Вы не должны сдвигаться вправо (или в этом отношении влево), потому что вы теряете биты.Предположим, вы XOR на 7 правильных битов hashValue и сдвиг вправо.Ваше хеш-значение содержит только 4 правильных бита только что добавленного вами значения!Это займет немного больше времени, если вы переместитесь влево, но то же самое верно.Вы отбрасываете биты на одном конце своего хеш-значения.Вы должны проверить на хорошую хэш-функцию.Википедия - ваш друг (https://en.wikipedia.org/wiki/Hash_function)
  4. Добавление немного лучше, чем вырожденное значение, но все равно создает неравномерный хэш (середина в большинстве данных будет более заполненной, чем концы).
...