c - 了解哈希表

Question

我了解到一些哈希表使用“桶”，这是一个“条目”的链表。

HashTable
  -size    //total possible buckets to use
  -count   // total buckets in use
  -buckets //linked list of entries

Entry
  -key   //key identifier
  -value // the object you are storing for reference
  -next  //the next entry

为了通过索引获取桶，您必须调用:

myBucket = someHashTable[hashIntValue]

然后，您可以迭代条目的链接列表，直到找到您要查找的条目或为空。

哈希函数是否总是返回 NUMBER % HashTable.size？那样的话，你保持在限制范围内？哈希函数应该是这样工作的吗？

Answer 1

从数学上讲，哈希函数通常被定义为从要存储在哈希表中的元素域到范围 {0, 1, 2, .., numBuckets - 1} 的映射。这意味着在理论上，没有任何要求您使用 mod 运算符将一些整数哈希码映射到有效桶索引的范围内。

然而，在实践中，几乎所有的程序员都会使用生成均匀分布的整数值的通用哈希码，然后对其进行修改以使其适合桶的范围。这允许独立于哈希表中使用的桶数开发哈希码。

编辑:您对哈希表的描述称为链式哈希表，并使用一种称为封闭寻址的技术。除了您所描述的之外，还有许多其他哈希表的实现。如果你很好奇 - 我希望你是! :-) - 你可能想看看the Wikipedia page on the subject .