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 クラスも衝突を処理する必要があります。これは、その関数が異なる入力に対して同じ値を返す可能性があるためです。