0

(範囲と分布が不明な)データ ストリームが入ってきて、最後の X個の値をO(1)アクセスを提供するハッシュ テーブルに格納したいとします。

簡単にするために、データが未知の範囲と分布の数のストリームであるとしましょう。これらの数値を配列の要素にマップするには、データの範囲と分布を考慮したハッシュ関数が必要です。

  • この範囲を前もって推定するか、入ってくるデータに関する統計を維持して、それに応じてハッシュ関数を調整すると思います。
  • また、X しきい値に達したときにアレイを再調整する方法も必要です。

    これをできるだけ早く行うための考えやアイデアはありますか?

    • 4

    1 に答える 1