c++ - HashSet c++ 说明

Question

我迷失在我一直在研究的这个话题上。在我的课堂上，我们正在实现自己的哈希集类。因此，我们有一个底层数据结构，如向量或数组，并使用散列函数来快速确定元素是否在集合中。那是我不遵循的部分。哈希函数将如何用于此确定？

Answer 1

假设您有一个大小为 100 的底层数组，并且您只能插入 0 到 99 之间的值。

像这样的东西：

class UselessHashMap
{
public:
  void insert(int value){
    _arr[hash(i)] = i;
  }
private:
  int hash(int i) { return i };
  std::array<int,100> _arr;
}

现在，假设您想要存储超过 100 个元素，并且您不能拥有一个具有无限 (std::numeric_limits::max() ) 大小的数组。在这种情况下，您的哈希函数必须返回一个介于 0-99 之间的值，当然您的 UselessHashMap 类也需要处理冲突，因为该函数可能会为不同的输入返回相同的值。