0

そこで、配列のみを使用して作成した HashTable 実装をここに用意し、コードを少し手伝いました。残念ながら、「get」または「put」メソッドの実行中に誰かが追加した行の 1 つがよくわかりません。以下のwhileループで正確に何が起こっているのでしょうか? リニアプロービングの方法ですよね？また、ループがチェックしている条件をチェックするのはなぜですか?

具体的には、

int hash = hashThis(key);

    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }

完全なリファレンスとして、以下に Java クラス全体を示します。

public class Hashtable2 {

private Node[] data;
private int capacity;
private static final Node AVAILABLE = new Node("Available", null);

public Hashtable2(int capacity) {

    this.capacity = capacity; 
    data = new Node[capacity];
    for(int i = 0; i < data.length; i++) {

        data[i] = AVAILABLE;
    }
}

public int hashThis(String key) {

    return key.hashCode() % capacity; 
}

public Object get(String key) {

    int hash = hashThis(key);

    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }
    return data[hash].element();
}

public void put(String key, Object element) {

    if(key != null) {
        int hash = hashThis(key);
        while(data[hash] != AVAILABLE && data[hash].key() != key) {

            hash = (hash + 1) % capacity;
        }

        data[hash] = new Node(key, element);

    }

}



public String toString(){

    String s="<";

    for (int i=0;i<this.capacity;i++)
    {
        s+=data[i]+", ";    

    }

    s+=">";

    return s;
    }

ありがとうございました。

4

2 に答える 2

1

コードの一部を書き直して、findHashメソッドを追加しました。コードの重複を避けるようにしてください。

private int findHash(String key) {
    int hash = hashThis(key);

    // search for the next available element or for the next matching key
    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }
    return hash;
}

public Object get(String key) {

    return data[findHash(key)].element();
}

public void put(String key, Object element) {

    data[findHash(key)] = new Node(key, element); 
}

あなたが求めたのは-このfindHash-loopは正確には何ですか？データは-で初期化されましたAVAILABLE。つまり、データには（まだ）実際のデータは含まれていません。ここで、要素を追加すると、put最初にhashValueが計算されdataます。これは、データを配置する配列内の単なるインデックスです。AVAILABLEさて、同じハッシュ値で異なるキーを持つ別の要素がその位置をすでに取得していることに気付いた場合は、次の位置を見つけようとします。また、このget方法は基本的に同じように機能します。異なるキーを持つデータ要素が検出された場合、次の要素がプローブされます。それdata自体は、いわゆるリングバッファです。つまり、配列の最後まで検索され、インデックス0から始めて、最初に再度検索されます。これはモジュロで行われます。%オペレーター。

大丈夫？

于 2013-02-11T05:16:38.437 に答える