如何实现动态哈希表的哈希函数？

我想实现一个通用的HashTable。（这个问题是继续问here问题）如何实现动态哈希表的哈希函数？

我已经实施了通用散列函数的情况下，当表的大小是固定的。但是，在实时情况下，使用HashTable的大小最初固定为大约2^32位是一个非常糟糕的主意，因为它可能导致大量内存浪费。

所以，我现在试图做的是动态增加hast表的大小，从一些初始值，每当它满了。

但是，当我这样做时，散列函数将现在将新值返回到先前散列的密钥。

是否有任何方法可以解决这个问题，而不是重新散列之前用新值散列值的值。

来源

2013-04-27 Sankalp

重散列是大多数散列表所做的。这并没有那么糟糕（无论如何，在调整大小时，您都会触摸整张桌子）。你为什么要避免它？ – delnan 2013-04-27 10:10:23

错误与“动态增加hast表的大小”有关。你需要显示一些代码。 – dasblinkenlight 2013-04-27 10:10:52

@dasblinkenlight：这不是一个错误，因为散列函数通常使用值来确定返回的散列值在散列表的大小范围内，所以期望这种行为。 – Sankalp 2013-04-27 10:13:04

你无法避免换汤不换药：桶，其中一个元素的哈希表内结束的位置取决于两个或三件事情，这取决于你的冲突解决策略：

元素的哈希码，
表的大小，和
当使用线性探测，它也与把它们在同一个桶中的散列码之前元件的存在或不存在

如果您更改以上三个因素中的任何一个，则需要全面重新组合：除非您执行非常糟糕的操作，例如选取非主表格大小，否则确定位置的值会随着您的不同而有所不同更改tableSize。在线性探测中散列到同一个存储桶的元素的存在或不存在也会发生变化。这就是为什么你需要一个完整的rehash。

来源

2013-04-27 10:18:04 dasblinkenlight

你提到的是真实的。为了避免冲突，我已经将哈希表作为链表的数组实现。所以，重新散列会有很多杂乱的代码随着大量的指针操作而流动。你能否提供一种更好的实现避免碰撞的方法，避免在代码中使用乱码指针，因为它通常会留下代码异味？ – Sankalp 2013-04-27 10:30:00

@Sankalp随着你使用的策略（它被称为“单独链接”），代码不应该是那么混乱：你需要的只是在所有桶中走完所有的列表，并将它们散列到新的地方。还有其他的[冲突解决策略]（http://en.wikipedia.org/wiki/Hash_table#Collision_resolution），您可以使用：例如，线性探测可以让您避免链接列表。不过，这种其他策略可能适用于您的散列键集，也可能不适用。 – dasblinkenlight 2013-04-27 11:17:59

如何实现动态哈希表的哈希函数？

回答

相关问题