3

バックグラウンド

クラスでは、線形連鎖ハッシュテーブルを作成しました。リンクリストの配列を格納し、getまたはputが呼び出されるたびに、キーがハッシュされ、配列サイズによってモジュロされます。次に、getまたはputが、結果のリンクリスト（これも実装しました）で呼び出されます。

ST（シンボルテーブル）インターフェースがあります。によく似てMapいますが、必要な操作のいくつかはMap、私が実装するには混乱しすぎていました。このインターフェイスの実装には、リンクリスト、赤黒木、線形プローブハッシュテーブル、および線形チェーンハッシュテーブルの実装があります。

任意のデリゲートシンボルテーブルタイプを受け入れる線形チェーンハッシュテーブルに似たものを作りたいと思います。たとえば、赤黒木タイプで初期化すると、赤黒木のテーブルが作成され、get関数とput関数はそれらの赤黒木に委任されます。

私の実装は、ライブラリが提供するものよりもほぼ確実に遅いこと、そして実際のコードでそれらを使用する方がよいことを認識しています。私はただ実験して学ぼうとしています。

質問

ハッシュテーブルがそのタイプのテーブルで構成され、呼び出しがそれらのシンボルテーブルに委任されるように、ハッシュテーブルにタイプを提供するための最良の方法は何ですか？

ジェネリックスを初期化できないため、ジェネリックスを使用できません。また、構築時とサイズ変更時に初期化する必要があります。

開始したいタイプの空白のシンボルテーブルを用意して、そのcopyメソッドを使用することを考えましたが、もっと良い方法があるはずです。ある？

4

2 に答える 2

4

必要Factoryなバッキング構造のインスタンスを作成するも提供する必要があります。

Map別のものに委任する簡単な例Map：

public static interface Supplier<T> {

    T get();
}

public static class DelegatingMap<K, V> implements Map<K, V> {

    private final Map<K, V> backingMap;

    public DelegatingMap(final Supplier<Map<K, V>> backingMapSupplier) {
        backingMap = backingMapSupplier.get();
    }

    @Override
    public int size() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public boolean isEmpty() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    //etc...
}
于 2013-03-24T16:59:09.980 に答える
2

型消去のため、実行時にオブジェクトは型パラメーターを自動的に追跡しません。そのため、new T()コンパイルされません。

これを回避するには、呼び出し元にClasstypeパラメーターのオブジェクトを提供するように要求します。このオブジェクトを使用して、新しいインスタンスを作成できます。もちろん、リフレクションを使用すると、コンパイル時のチェック（特に、コンパイラーはシンボルテーブルの実装に必要なコンストラクターがあることをチェックしません）、およびIDEが提供する静的分析（コンストラクターの呼び出し階層は表示されません）をバイパスします発信者）。

または、呼び出し元にファクトリオブジェクトを提供するように要求することもできます。これにより、必要に応じてシンボルテーブルの実装を作成できます。これはより柔軟性があり（たとえば、呼び出し元はコンストラクター引数を選択できます）、静的にタイプセーフですが、より冗長です...

于 2013-03-24T17:03:54.360 に答える