配列を使用してハッシュテーブルを実装する必要がありますか？別のデータ構造でも同じ効率が得られますか？はいの場合、なぜですか？いいえの場合、アレイによって提供されるのと同じ効率を確保するために、データ構造はどのような条件を満たす必要がありますか？
質問する
759 次
1 に答える
2
配列を使用してハッシュテーブルを実装する必要がありますか？
HashTableいいえ。アレー以外の他のデータ構造とのインターフェースを実装できます。たとえば、赤黒木（javaのTreeMap）。
これにより、O(logN)アクセス時間が提供されます。
ただし、アクセス時間Hash Tableがあると予想されO(1)ます（最良の場合-衝突はありません）。
これは、一定時間でランダムアクセスの可能性を提供するアレイを介してのみ達成できます。
アレイと同じ効率を確保するには、データ構造がどのような条件を満たす必要がありますか？
O(N)アレイと同等のパフォーマンス（未満）である必要があります。ツリーマップは、すべての操作O(logN)でアクセス時間が最悪です
于 2012-09-03T15:54:40.953 に答える