O（1）期待値とO（logn）最悪ケースの集合に整数が存在するかどうかを調べる

Question

O（1）の集合に特定の整数が存在するかどうかを判断できるデータ構造を記述する必要がある）期待時間とO（logn）最悪の場合もO（n）スペースを消費します。 iveは共通のデータ構造を含んでいるテーブルを見ていましたが、大きな時間/空間の複雑さがありましたが、これらの要件を満たすものはどれも見つかると思われますか？これらの要件に合わせてBSTを変更する方法はありますか？

Answer 1

@Carcigenicateがコメントしたように、ハッシュマップは必要な動作を示します。衝突の場合を除いて、一定の参照時間がO(1)になります。衝突の場合、ハッシュマップは通常、指定されたバケットの項目のリストを作成します。最悪の場合のシナリオでは、ハッシュマップはリストのように動作します。しかしこれは最悪の場合の検索時間がO(n)であることを意味しますが、それはあなたの要求に合っていません。

Javaは最新の8バージョンでは、同じバケットと衝突するアイテムを格納するリストの代わりにバランスの取れたツリーを使用するHashMapクラスを公開しました。これにより、最悪の場合の検索時間がO(logn)になります。

したがって、問題を解決するには、衝突のためにツリーを使用するようにハッシュマップの実装を変更する必要があります。 Java 8を使用している場合、人生は既に良いですし、ちょうどHashMapで実行することができます。