ハッシュマップデータ構造を理解しようとしています

Question

私はハッシュマップデータ構造を構築することに取り組んでいる宿題に取り組んでいます。私は与えられたコード行を理解していません。次のようにプログラムでは、変数が開始されます。

private Map<K,V>[] buckets; 

私はハッシュマップで使用されるときバケットの概念が何であるかを知っているが、どのように私はバケットを作成するマップ配列を使用することができますか？このコードを見ると、ハッシュマップの配列を作成する必要があるようですが、それはまったく意味がありません。

さらに詳しい情報が必要な場合は、私に知らせてください。

ご協力いただきまして誠にありがとうございます。

以下は、提供されたコードです。

package cs2321; 

import net.datastructures.*; 

public class HashMap<K, V> implements Map<K, V> { 

private Map<K,V>[] buckets; 

protected final int mDefaultHashSize = 1021; 

/** 
* Constructor that takes a hash size 
* @param hashsize The number of buckets to initialize 
*     in the HashMap 
*/ 
public HashMap(int hashsize){ 
    // TODO: Be sure to initialize the bucket array 
    //  using the hashsize given as the number of buckets 
} 

public HashMap(){ 
    // TODO: Be sure to initialize the bucket array 
    //  using the default hash size provided. 
} 


public Iterable<Entry<K, V>> entrySet() { 
    // TODO Auto-generated method stub 
    return null; 
} 

public V get(K key) throws InvalidKeyException { 
    // TODO Auto-generated method stub 
    return null; 
} 

public boolean isEmpty() { 
    // TODO Auto-generated method stub 
    return false; 
} 

public Iterable<K> keySet() { 
    // TODO Auto-generated method stub 
    return null; 
} 

public V put(K key, V value) throws InvalidKeyException { 
    // TODO Auto-generated method stub 
    return null; 
} 

public V remove(K key) throws InvalidKeyException { 
    // TODO Auto-generated method stub 
    return null; 
} 

public int size() { 
    // TODO Auto-generated method stub 
    return 0; 
} 

public Iterable<V> values() { 
    // TODO Auto-generated method stub 
    return null; 
} 

}

Answer 1

広いコードベースを見ずに、正確に言うのは難しいが、私は、この文脈での「地図」は本当に「MapEntry」または類似した何かを意味し、マップエントリことと思われる与えられた情報から、 のキーと値のペアを表します。

ハッシュマップバケットは、異なるキーを持つが同じハッシュ値を持つエントリを区別できるように、キーと値の両方を含む必要があることに注意してください。

Javaのマップエントリは通常、Map.Entry interfaceに準拠すると予想されます。あなたのケースで使用されている「マップ」クラスがこのインタフェースをサポートしている場合、それはこの役割を果たしているということを示す良い例です:-)

もちろん、それぞれの内容を表すハッシュマップですバケツ。あなたはすでに、彼らはすでにハッシュマップの実装を持っている場合、それは奇妙なことと同じハッシュコード

を持って知っているので、単一のバケツの中にハッシュマップを使用することの何のメリットがありません

• ：しかし、それは二つの理由から非常に奇妙に思えますそれを使用して別のハッシュマップを再実装します。

地図は別の種類の地図（赤い黒色の木かもしれません）かもしれませんが、再びそれは奇妙です - 通常、バケットの実装では、ヘビー級ではなく配列またはリンクリストが使用されますマップデータ構造。

アップデート（コードが掲載された後）

今掲示コードから、つまり、内容を表現するために、別のマップ構造を使用してハッシュマップを実装するために、意図は最後の2つのオプションの一つであることは明らかと思われます各バケットごとに上に挙げた理由のために奇妙に思えますが、テンプレートコードから、これが意図されていることが合理的には明らかだと思います。

Answer 2

ここには、HashMapの動作をデモンストレーションするために使用されるHashMapの配列があります。それを調べて、それがどのように機能し、なぜHashMapsが広く使われているのかを教えてください。

public class Test { 
static private Map<String,String>[] buckets; 
static int numberOfBuckets = 3; 
static public void main(String...strings) { 
    buckets = new Map[numberOfBuckets]; 
    for (int x=0; x!=numberOfBuckets; x++) { 
     buckets[x]=new HashMap<String,String>(); 
    } 
    String s1 = "one ijsiji jdj i"; 
    String s2 = "two ijs42i jdj i"; 
    String s3 = "th3 ijsiji 42j i"; 
    String s4 = "i42 ji jdj i"; 
    buckets[(Math.abs(s1.hashCode()) % numberOfBuckets)].put(s1,""); 
    buckets[(Math.abs(s2.hashCode()) % numberOfBuckets)].put(s2,""); 
    buckets[(Math.abs(s3.hashCode()) % numberOfBuckets)].put(s3,""); 
    buckets[(Math.abs(s4.hashCode()) % numberOfBuckets)].put(s4,""); 
    for (int x=0; x!=numberOfBuckets; x++) { 
     System.out.println(buckets[x]); 
    } 
} 
} 

意味がありません。あなたが正しい出力

{two ijs42i jdj i=} 
{one ijsiji jdj i=, i42 ji jdj i=} 
{th3 ijsiji 42j i=}