需要帮助开始构建我自己的散列表

我正在学习散列表，试图了解它们是如何工作的。我想制作一个相当简单的哈希表，使用单独的链接（使用数组中的列表）。我有几个问题：需要帮助开始构建我自己的散列表

假设键可以是任何类型的，我会要求用户执行散列函数，对不对？这可以避免吗？
用户还需要提供包含在初始化的列表（碰撞）所述阵列的长度，正确？这可以避免吗？

如果你有任何其他的提示，或者一些散列表的C++的清晰的代码示例，我会感激。

感谢您的帮助。

2012-02-07 xcrypt

通常情况下，是的，你就需要在客户端指定的散列函数，因为如果你正在写一个通用的哈希表和任意类型T的操作，你可以不知道如何哈希它的方式，在语义上是有意义的。您可以通过在存储的元素类型和散列函数上对类进行参数化来完成此操作。例如：

template <typename T, typename Hash = std::hash<T>> 
    class MyHashTable { 
    /* ... */ 
}

在这里，您可以使用默认参数和模板来选择默认散列函数，除非用户另有指定。

虽然客户端通常可以指定表的初始大小，它不是必需的。您可以对桶的数量进行有根据的猜测（比如，最初使用17个桶），随着负载因子的增加，增加表的数量。这是类似的，比如说，如何std::vector工作：实现可以选择默认的大小，但如果客户端，也确实需要一个预先筛分的载体或来电reserve，实施从用户需要的提示。例如，你可以有形式

template <typename T, typename Hash = std::hash<T>> 
    class MyHashTable { 
public: 
    MyHashTable(unsigned numBuckets = 17); 
}

这样的构造，客户可以只构建一个哈希表桶的默认号码，或者如果他们有桶的数量感，他们会就像他们可以将其指定为参数一样。但是，您可能还想隐藏存储桶作为细节，只需让客户端指定要将多少元素放入表中，然后让您的类在幕后执行计算。这使得后台切换实现变得更加容易，因此，如果您想使用动态完美哈希表而不是链式哈希，类可以处理计算初始大小的复杂性。

至于代码示例，我不知道如何提供任何不放弃很多参与建设哈希表的复杂性。 :-)如果您有一段特定的代码感兴趣，并且无法自行编写代码，请随时将其作为单独问题发布，以便获得更有针对性的反馈。

希望这会有所帮助！

来源

2012-02-07 22:23:23 templatetypedef

看的哈希算法的各种实现方式。有很多可用的。如果你愿意，你可以让哈希存储变量。随你便。使用大多数哈希算法，碰撞是可能的。记住这一点。

来源

2012-02-07 22:23:35

我不知道这是如何解决这个问题。如果你正在构建你自己的散列表，那么你可能希望客户端提供散列算法，因为你可能事先不知道存储的类型是什么。此外，由于这是C++，因此您可以使用'std :: hash'来执行散列。 – templatetypedef 2012-02-07 22:28:29

如果你想了解哈希表，我建议你开始用最简单的人至极的线性链哈希表

在这里，您考虑的指针（指针的固定大小的数组类型的定义项目你）你的物品将被存储在哪里，考虑还有一些计数器，一个用于跟踪阵列的长度，另一个用于跟踪添加到表中的物品的数量，直到某个时刻

你可以使用宏定义将项添加到哈希表的功能，如下所示

h(k) = k % M

其中k是要添加的项目的索引（键），M是表示指针数组大小的质数（例如13,29,41,543）和h（k）会给你该项目将被插入的位置。

你应该考虑使用指针的固定大小的数组的原因是因为这种方式，您有

O(n)

成本。

因此，从这个简单的功能，那么你可以修改它，并考虑实施一些更复杂的像开放adressing，线性探测，二次探测和双散列

对于用户要求对项目的数量输入i开始完全同意什么templatetypedef说早些时候

来源

2012-02-07 22:47:13

需要帮助开始构建我自己的散列表

回答

相关问题