1. ホーム
  2. java

[解決済み] Java HashTable実装の線形プロービング

2022-02-07 14:41:50

質問内容

そこで、私はここに、配列だけを使って書いた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;
    }

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

解決方法は?

コードの一部を書き換えて、findHash-methodを追加しただけです - コードの重複を避けるようにしてください!

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 - でのインデックスに過ぎません。 data の配列のどこにデータを置くかを指定します。さて、もしその位置が、同じハッシュ値で異なるキーを持つ別の要素によってすでに取られていることに気づいたら、次の AVAILABLE の位置を指定します。そして、その get メソッドは基本的に同じように動作します。異なるキーを持つデータ要素が検出されると、次の要素がプローブされ、以下同様です。 そのため data は、いわゆるリングバッファである。つまり、配列の最後まで検索され、次にインデックス0から始まり、再び先頭から検索されます。これは,modulo % 演算子を使用します。

よしっ