理解哈希表

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]

然后,您可以迭代条目的链接列表,直到找到您要查找的条目或null.

哈希函数总是返回一个NUMBER % HashTable.size？那样,你保持在极限之内？是哈希函数应该如何工作？

Answer 1

从数学上讲,哈希函数通常被定义为从您想要存储在哈希表中的元素的范围到范围{0,1,2,..,numBuckets - 1}的映射.这意味着理论上,您无需使用mod运算符将某些整数哈希代码映射到有效存储区索引的范围内.

但是,在实践中,几乎普遍的程序员将使用通用哈希码生成均匀分布的整数值,然后将其修改为适合桶的范围.这允许独立于散列表中使用的桶的数量来开发散列码.

编辑:您对哈希表的描述称为链式哈希表,并使用称为封闭寻址的技术.除了您描述的哈希表之外,还有许多其他哈希表实现.如果你很好奇 - 我希望你是!:-) - 你可能想查看关于这个主题的维基百科页面.