有效的方法来避免整数溢出？

我正在研究一个获取字符串作为输入的散列函数。有效的方法来避免整数溢出？

现在我正在做一个循环，并在散列（一个int变量）中乘以一个值，然后将当前字符的ASCII码添加到混合中。

hash = hash * seed + string[i]

但有时，如果字符串是足够大的，存在一个整数溢出那里，我能做些什么来避免它，同时保持相同的哈希结构呢？也许在循环内部包含一些操作？

来源

2010-05-04 Jonathan

为什么你需要避免溢出？散列函数的唯一关键特征是对于任何给定的数据，散列函数会给出一致的结果。当然，避免碰撞很好，但并不重要。 – torak 2010-05-04 19:07:49

如果hash *种子导致整数溢出，并且string [i]是正数，那么不管怎么样，都不会导致溢出。你的意思是你想通过模运算符将散列值限制在最大值？ – bobDevil 2010-05-04 19:09:09

@torak：有符号的整数溢出会导致C中的未定义行为，这意味着正确的程序必须注意避免它。 – caf 2010-05-05 00:09:01

为什么不使用long来存储结果？然后，您可以申请技术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);

否则，你将不得不手动乘以散列和种子成两个值，添加字符串[我]溢出，然后^这两个值。

哈希是隐含有损的，所以只要让溢出位去就行了，除非有特定的原因需要它们，比如匹配现有的算法。

来源

2010-05-04 19:17:20 drawnonward

像这样的散列函数应该会溢出。你必须声明“哈希”无符号。如果你真的需要一个int而不是简单地使用hash & 0x7fffffff。查看Fowler-Noll-Vo algorithm，您会在那里找到指向源代码的链接。

来源

2010-05-04 19:28:31

对您的问题有许多可能的解释，正如评论所述，您可能需要澄清。

然而，唯一合理的解释是您想要将散列值限制在指定范围内。假设，这时如果范围是0到HASH_TABLE_SIZE - 1，则：

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

，或者如果表的大小是2的幂，使用口罩：

#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

有效的方法来避免整数溢出？

回答

相关问题