了解散列表

我知道一些散列表使用“存储桶”，它是“条目”的链接列表。了解散列表

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？这样，你保持在极限内？那哈希函数应该如何工作？

来源

2011-01-12 joels

从数学上讲，散列函数通常定义为从希望存储在散列表中的元素的Universe到范围{0,1,2，...，numBuckets-1}的映射。这意味着从理论上讲，使用mod运算符将某些整数散列码映射到有效桶索引的范围中并不需要任何条件。

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

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

来源

2011-01-12 01:22:43 templatetypedef

没有关于散列函数应该如何表现的预定义规则。您可以将所有值映射到索引0 - 一个完美有效的散列函数（表现不佳，但有效）。

当然，如果你的哈希函数返回一个超出相关数组索引范围的值，它将无法正常工作。但是，这并不是说，你需要使用公式(number % TABLE_SIZE)

来源

2011-01-12 01:24:53

投下了这个答案的人可以提供解释吗？我会猜测他们不会。 – 2011-01-12 01:56:16

不，该表通常是一个条目数组。您不会迭代它直到找到相同的散列值，而是使用散列结果（或通常是哈希模数numBuckets）来直接索引到条目数组中。这给你O（1）的行为（迭代将是O（n））。

当您试图存储具有相同散列结果的两个不同对象（称为“散列冲突”）时，您必须找到某种方法来腾出空间。不同的实现方式在处理碰撞方面有所不同。您可以创建具有相同散列的所有对象的链接列表，或者使用一些重新散列来存储在表格的不同条目中。

来源

2011-01-12 01:30:29 Javier

什么是散列表？

它也被称为散列映射是用于实现关联数组。它一个数据结构是能够键映射到的值的结构。

它是如何工作的？

散列表使用散列函数来计算可以找到正确值的桶或槽阵列的索引。

请参阅下图清楚说明。

enter image description here

优点：

在一个良好的尺寸哈希表，每个查找的平均成本为独立元件存储在表中的数量。

许多哈希表设计还允许任意插入和删除键值对。

在许多情况下，哈希表练得更有效超过搜索树或任何其他查表结构。

缺点：当条目的数量非常少

哈希表是不能奏效的。（然而，在某些情况下，计算散列函数的高成本可以通过与钥匙一起保存的散列值减轻）

用途：

它们被广泛应用于各种电脑软件特别是关联数组，数据库索引，缓存和集合。

来源

2013-08-24 10:26:03

回答

相关问题