algorithm - 定数時間で N サイズのリストで整数を検索する方法は?

Question

リストのプロパティ:

1. サイズ N である必要があります。ここで、N は整数の量です。

2. 空のセルはありません

3. 数字は完全に連続しているとは限りません (つまり、{-23,-15,-3,1,2,6,7,8,15,100})

4. 挿入/検索は一定時間内に行う必要があります。

私の最初の本能は、ハッシュ テーブルを使用することでしたが、これでは数字がスキップされた未使用のセルが作成されます。

そのリストに数値が存在するかどうかを一定時間チェックするために、そのようなリストを構築できる方法はありますか?

Answer 1

私のコメントに続いて、正確なユースケースに応じて、Java のHashSetやLinkedHashSetSetのようなものをチェックアウトできます。

HashSet と同様に、ハッシュ関数がバケット間で要素を適切に分散すると仮定すると、基本操作 (追加、保持、および削除) に対して一定時間のパフォーマンスが提供されます。

他のプラットフォームでのソリューションを探している場合は、同等の実装があるか、Java のソース コードを確認して自分で実装することができます。