为什么哈希函数返回 size_t，它是如何使用的？
我了解哈希表的数学基础。我在下面有一个哈希函数（我在某处找到的）：
/* Fowler / Noll / Vo (FNV) Hash */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
size_t myhash(const string &s, int length)
{
size_t hash = InitialFNV;
for(size_t i = 0; i < length; i++)
{
//XOR the lower 8 bits
hash = hash ^ (s[i]);
//Multiply by the multiple
hash = hash * FNVMultiple;
}
return hash;
}
- 为什么它返回
size_t？ - 如何用它来写一篇
store()函数放置一个 哈希表中的字符串？ - 这如何适用于数组 字符数？
- 关于#3，是否合适替换
for循环和while循环 以'\0'字符终止？
仅供参考，我正在为第二次工作面试做准备，这就是我问这个问题的原因。
I understand the mathematical basis for hash tables. I have a hash function (that I found somewhere) below:
/* Fowler / Noll / Vo (FNV) Hash */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
size_t myhash(const string &s, int length)
{
size_t hash = InitialFNV;
for(size_t i = 0; i < length; i++)
{
//XOR the lower 8 bits
hash = hash ^ (s[i]);
//Multiply by the multiple
hash = hash * FNVMultiple;
}
return hash;
}
- Why does this return a
size_t? - How would one use this to write a
store()function which places a
string in a hash table? - How can this be adapted for an array
of characters? - In regards to #3, would it be appropriate to replace
theforloop with awhileloop that
terminates at the'\0'character?
FYI, I am studying up for a second job interview, and that's why I'm asking.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
它返回
size_t，因为这是本机整数（也是最快的）。为什么选择其他东西？“桌子”？哪张桌子？如果您指的是哈希表，那么您可以使用返回值来选择一个随机存储桶来放入对象。（提示：想想“余数”。）
它不是已经适合数组了吗？
如果它是一个以 null 结尾的字符串，为什么不呢？
It returns
size_tbecause that's the native integer (also fastest). Why choose anything else?"The table"? Which table? If you mean a hashtable, then you can use the return value to choose a random bucket to put the object in. (Hint: Think "remainder".)
Isn't it already adapted for an array?
If it's a null-terminated string, why not?
它不一定是
size_t，但它可能应该是无符号整数类型，因此 mod 是明确定义的。通常的方法是使用哈希函数将“key”数据转换为数组索引。因此，您可以对数组的大小进行取模，以获得一个从 0 到 SIZE-1 的整数，您可以将其用作索引。您还需要一个“冲突解决策略”，因为除非哈希产生完美的结果，否则某些不同的键对将哈希为相同的值。
它似乎已经如此适应。
如果字符串以NUL结尾，则可以搜索空值。但是编写的函数传递了一个长度作为参数。最简单的方法是保留工作函数，并使用 strlen() 的结果调用它。
诗。
const string &s表示 C++，不是 C。这在编译时可能很重要。It doesn't have to be
size_t, but it should probably be an unsigned integer type so mod is well-defined.The usual way is to use the hash function to transform the 'key' data into an array index. So you mod by the size of the array to get an integer from 0 to SIZE-1 that you can use as an index. You'll also need a "collision resolution strategy" because unless the hash yields perfect results, some pairs of keys which are different will hash to the same value.
It appears already to be so adapted.
If the string ends in NUL, you can search for the null. But the function as written is passed a length as argument. Simplest to leave the working function alone, and call it with the result of strlen().
Ps. the
const string &smeans C++, not C. This may be important when compiling.string保留它自己的长度，您不需要传入它。这是 C++，而不是 C - C 中没有引用。不需要strlen或类似的东西that，或NULL终止符，或任何此类。这意味着用查找\0的 while 循环替换它将会是 Bad™，因为不能保证std::string甚至有一个，更不用说将其作为它是终结者。stringholds it's own length, you don't need it to be passed in. That's C++, not C- no references in C. There's no need forstrlenor anything like that, orNULLterminators, or anysuch. That means that replacing it with a while loop looking for\0would be Bad™, as there's no guarantee thatstd::stringeven has one, let alone has it as it's terminator.