[解決済み] 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
%
演算子を使用します。
よしっ
関連
-
[解決済み】宣言されたパッケージが期待されるパッケージと一致しない ""
-
[解決済み] SQLエラー。0, SQLState: 08S01 通信リンクの失敗 [重複]。
-
[解決済み] JavaでInputStreamを読み込んでStringに変換するにはどうすればよいですか?
-
[解決済み] JavaでNullPointerExceptionを回避する方法
-
[解決済み] JavaにおけるHashMapとHashtableの違いは何ですか?
-
[解決済み] Java Mapの各エントリを効率的に反復処理するには?
-
[解決済み] Javaでメモリーリークを発生させるにはどうしたらいいですか?
-
[解決済み] Javaにおけるpublic、protected、package-private、privateの違いは何ですか?
-
[解決済み] JavaでArrayListではなくLinkedListを使用するのはいつですか?
-
[解決済み] JavaでStringをintに変換するにはどうしたらいいですか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み】エラー「No enclosing instance of type Foo is accessible」の原因と修正方法について教えてください。
-
[解決済み】"|="の意味は何ですか?(パイプ等号演算子)
-
[解決済み】Javaの部分文字列:「文字列のインデックスが範囲外」。
-
[解決済み] [Solved] java.lang.NoClassDefFoundError: クラスXXXを初期化できませんでした。
-
[解決済み] StringBuilderをクリアまたは空にするにはどうすればよいですか?重複] [重複] [重複] [重複] [重複] [重複
-
[解決済み] Hide Utility Class Constructor : ユーティリティクラスはパブリックまたはデフォルトコンストラクタを持つべきではありません。
-
[解決済み】Ubuntu: OpenJDK 8 - パッケージを見つけることができません。
-
[解決済み】Javaの".class expected "について
-
[解決済み】Java: GZIPInputStreamの作成に失敗しました。GZIP形式ではありません
-
[解決済み】koch snowflake java recursion