Эффективный способ избежать целочисленного переполнения при умножении?

Question

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

Прямо сейчас я делаю цикл и внутри хеша (переменная int) умножается на значение, а затем код ASCII для текущего символа добавляется в микс.

hash = hash * seed + string[i]

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

Answer 1

Существует несколько возможных толкований вашего вопроса, и, как отмечено в комментариях, вам, возможно, потребуется уточнить.

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

hash = (hash * seed + string[i]) % HASH_TABLE_SIZE ;

или, если размер таблицы равен степени двух, используйте маску:

#define HASH_TABLE_SIZE (0x01<<8)  // 2^8 (256) table
#define HASH_MODULO_MASK (HASH_TABLE_SIZE - 1)
...
hash = (hash * seed + string[i]) & HASH_MODULO_MASK ;

Answer 2

Хеш-функции, подобные этой, должны переполняться. Вы должны объявить "хэш" без знака. Если вам действительно нужен int, тогда просто используйте hash & 0x7fffffff. Просмотрите алгоритм Fowler-Noll-Vo , там вы найдете ссылки на исходный код.

Answer 3

Если у вас есть доступ к более крупному типу данных, вы можете сделать что-то вроде этого:

int32_t hash, seed;
int64_t temporary;

temporary = hash * seed + string[i];
hash = ( temporary >> 32 ) ^ ( temporary & 0xFFFFFFFF );

В противном случае вам придется вручную умножить хеш и заполнить на два значения, добавить строку [i] с переполнением, затем ^ два значения.

Хэши неявно с потерями, поэтому хорошо бы просто допустить, чтобы биты переполнения ушли, если только для этого нет особой причины, например, соответствия существующего алгоритма.

Answer 4

Почему бы не использовать долго, чтобы сохранить результат? Затем вы можете применить методы , такие как этот , чтобы обнаружить переполнение