どのようなJavaデータ構造体が順序付けされたコレクションであり、機能の一定時間のHashSetのメソッドを提供し、ArrayListのget
メソッドのようにインデックスによる一定の時間の検索を提供しますか? Java APIにはこのようなことが含まれていますか?私はTreeSetの使用を検討しましたが、Java Docsによると、これらの操作はO(log n)です。Javaの順序付けされたHashableコレクション
答えて
LinkedHashSetを使用してください。予測可能な反復順序で、Setインタフェースのハッシュテーブルとリンクリストの実装です。
ハッシュセット内にアイテムが存在するかどうかを確認するために、複雑さは最大でO(n)です。ほとんどの場合、衝突は見られないので、ほとんどの場合、O(1)になります。
LinkedHashSetはインデックスをサポートしていますか? – Aroto
setインターフェイスには、indexOf()やget()などの直接的なメソッドはありません。要素を検索するには、コレクション全体を解析する必要があります。 indexOf()とget()は内部的に同じことをします。 – FallAndLearn
OPは、インデックス*によって定時要素検索*を要求します。 'LinkedHashSet'は一定時間の検索を提供しますが、それはインデックスではなくキーだけです。 –
Java標準ライブラリはこのようなクラスを提供していませんが、あまり問題なく独自に実装することができます。 LinkedHashSet
:List
(恐らくラップArrayList
)の二重で、一定時間の処理のために内部のHashSet
を維持します。
コレクションAPIには、コレクションクラスを簡単に実装できるようにするためのクラスがあります。この場合、具体的なサブクラスAbstractList
の実装を見ていきます。
更新:あなたのアイデアは、インスタンスが自動的に順番にその要素を維持すること、および/または、彼らは重複要素を許可しないということであれば一方 、その後、何を話していることは全くList
ではありません。この場合、インデックス付き検索メソッドを追加する具体的なサブクラスAbstractSet
を実装することを検討してください。あなたはまだHashSet
とArrayList
をラップすることができますが、要素の挿入時にリストの順序を維持するために何らかの努力を必要とします。
['LinekdHashSet'](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html)おそらく? – Mureinik
定時挿入が必要ですか?もしそうなら、これはうまくいかないでしょう。そのようなデータ構造はあなたがO(n)時間に比較ソートを行うことができるからです。 – user2357112
あなたが「発注」と言うとき、ソートされた発注を意味しますか、それとも発注のような他の発注を意味しますか? – user2357112