为什么 BKDFHash 不关心超出范围的问题？

Question

unsigned int BKDRHash(const std::string& str){
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
    hash = (hash * seed) + str[i];
}

return hash;}

为什么上面代码中hash超出unsigned int的范围就不用关心了？我已经看到几个示例代码对溢出问题没有任何作用。为什么它仍然有效？当值 hash 超出 unsigned int 的范围时会发生什么？

Answer 1

之所以有效，是因为根据标准 unsigned 整数类型实际上不会发生溢出：

3.9.1 Fundamental types [basic.fundamental]

Unsigned integers shall obey the laws of arithmetic modulo 2ⁿ where n is the number of bits in the value representation of that particular size of integer.⁴⁸

This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.

例如：如果 unsigned int 算术结果 x 否则会超过 UINT_MAX，结果正好是：

x % (UINT_MAX+1)

从而在 0...UINT_MAX

内给您留下结果

为什么 BKDFHash 不关心超出范围的问题？

Why BKDFHash doesn't care about out of range issue?

c++

hash

hashcode