チェーンハッシュテーブルリンクリスト

Question

連鎖リストとして各バケットに名前を入れるためのチェーンハッシュテーブルを作成することになっています。私は一つの値を保持するバケットでこれを行う方法を知っていますが、各バケットにリンクリストを入れる方法はわかりません。私は名字とハッシュコードクラスを持つpersonクラスをすでに持っています。私は削除を書いたが、LinkedListをそのメソッドに入れる方法がわからない。私はbucketListクラスも持っています。私はLinkedListを実装する必要がありますか？メソッドを削除したり置いたりするときに何が起こるかを知ることができれば、残りの処理方法を理解することができます。あなたは

public class MyChainHashTable<K, V> { 

private static final int BUCKET_COUNT = 10; 

private BucketList[] buckets = new BucketList[BUCKET_COUNT]; 

private void remove(K key, V value) { 
    int bucketIndex = key.hashCode(); //TODO 
    int bucketsProbed = 0; 

    while (!buckets[bucketIndex].isEmptySinceStart() && bucketsProbed < BUCKET_COUNT) { 
     // if this bucket isn't empty, and it matches what we're looking for 
     if (!buckets[bucketIndex].isEmpty() 
       && buckets[bucketIndex].getElement().equals(value)) { 
      buckets[bucketIndex].clear(); 
      return; 
     } 
     bucketsProbed++; 
     bucketIndex++; 
     bucketIndex %= BUCKET_COUNT; // circle back to 0 
    } 
} 

private boolean put(K key, V value) { 
    return false; 

} 

private void showTable() { 
    // old phone UI 
    String[] keyBoard = {"1 ", "2 ABC", "3 DEF", "4 GHI", "5 JKL", 
      "6 MNO", "7 PRS", "8 TUV", "9 WXY", "0 "}; 

} 

Answer 1

私は連鎖ハッシュテーブルが本当にあなたがキーの衝突を持っている場合、テーブルの周りにジャンプする必要がないようにハッシュテーブルへのあなたのハッシュキーをマップするハッシュテーブルのハッシュテーブルだと思いますありがとうございました。

HashTableの代わりにLinkedListsのHashTableを使用して、その変形版を要求しています。

基本的なHashTableでは、基本的にはbucketIndex %= BUCKET_COUNT;で何をしているのですか？しかし、それをしないと、次のインデックスを計算する必要があります。基本的な配列のインデックスされた場所に要素を挿入する代わりに、配列はHashTables（またはあなたの場合はLinkedListsの配列）の配列であり、要素をそのコレクションに挿入します。

Answer 2

私が集めたことから、リンクされたリストを持つハッシュテーブルを実装したいと考えています。 Rawsick

だから私は、このデータ構造の一部を試してみて、実装してみましょう - 私はまた、一般的にこのコメント

最高の人生の見つけ方を見ました。

BucketListから始めましょう。これは、バケットを定義する一般的なパラメータTと、バケット内のものであるVとの単なるバケットのように聞こえるからです。それはBucket<T, V>

今

public class Bucket<T extends Colletion<V>, V> { 
    private T bucket; 

    public T add(V value) { 
     return bucket.add(V); 
    } 
    // More functions here 
} 

にハッシュテーブルつもりリファクタリングよ、

public class MyChainHashTable<K, V> { 
    private static final int BUCKET_COUNT = 10; 
    // Advisable to use a resizeable array here, like an ArrayList 
    // No need for bucket count then 
    private Bucket<LinkedList, V>[] buckets = new Bucket<>[BUCKET_COUNT]; 

    public V put(K key, V value) { 
     int bucketIndex = key.hashCode() % BUCKET_COUNT; 
     buckets[bucketIndex].add(V); 
    } 
    // More functions here 
} 

これは、ハッシュテーブルに非常に単純なアプローチでした、唯一のバケット自体は少しバケツができると私の中に複雑でした値をJava Collectionsフレームワークの任意のクラスの形式で格納します。

Javaのコレクションの一般的な実装のソースコードを読むことをお勧めします。このような問題にどのようにアプローチするかについて、より良い考えが得られます。

GoogleのGauvaライブラリをご覧ください。 MultiMapのような複雑なコレクションのいくつかを見て、それらがどのように実装されたかを調べてください。