data-structures - その中のデータの量に関係なく、データ構造

Question

データの配置がそのボリュームに依存しないデータ構造はありますか?

Answer 1

「データの検索は、その中のデータの量とは無関係です」-これは、取得操作の O(1) を意味すると思います。それはハッシュマップになります。

これは、ハッシュに基づいてオブジェクトをフェッチすることを前提としています。

各要素をチェックして、属性が特定の値と一致するかどうかを確認する必要がrsonあるern場合は、その値を前もってキーにする必要があります。

検索する必要がある値が複数ある場合 (すべてが一意で不変でなければなりません)、値ごとに 1 つずつ、複数のマップを作成できます。これにより、複数で検索できます。ただし、それらはすべて一意で、不変で、事前にわかっている必要があります。

前もってキーを確立しないと、それは O(N) になります。つまり、必要なものが見つかるまで、すべての要素を順番にチェックする必要があります。平均して、コレクションのサイズが大きくなるにつれて、この時間は長くなります。それが O(N) の意味です。