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

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

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

hash = hash * seed + string[i]

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

источник

2010-05-04 Jonathan

Зачем вам нужно, чтобы избежать переполнение? Единственной важной особенностью хэш-функции является то, что для любых данных хеш-функция дает согласованный результат. Конечно, предотвращение столкновений приятно, но не критично. – torak

Если hash * seed вызывает целочисленное переполнение, а строка [i] положительна, нет никакого способа, чтобы это не вызвало переполнение, независимо от того, каким образом вы пытаетесь это сделать. Вы хотите ограничить хэш до максимального значения с помощью оператора modulo? – bobDevil

@torak: Подписанное целочисленное переполнение вызывает неопределенное поведение в C, а это означает, что правильные программы должны позаботиться о том, чтобы избежать этого. – caf

Почему бы не использовать длинные сроки, чтобы сохранить результат? Затем можно применить методы such as this one для обнаружения переполнения

источник

2010-05-04 19:06:42 DVK

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

int32_t hash, seed; 
int64_t temporary; 

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

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

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

источник

2010-05-04 19:17:20 drawnonward

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

источник

2010-05-04 19:28:31

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

Единственная разумная интерпретация, однако, заключается в том, что вы хотите ограничить хэш-значение указанным диапазоном. Если предположить, что, то, если диапазон был 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 ;

источник

2010-05-04 19:28:47 Clifford

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

ответ

Смежные вопросы