鏈式哈希錶鏈接列表

我應該製作一個鏈式哈希表來將每個存儲桶中的名稱作爲鏈接列表。我知道如何使用具有一個值的桶進行此操作，但我不知道如何在每個桶中放置鏈接列表。我有一個人姓名和姓氏，以及哈希碼類。我寫了刪除，但我不知道如何將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 "}; 

}

來源

2016-11-16 Rawsick

你的代碼對我來說沒有多大意義。你爲什麼要將'buckets'聲明爲一系列buckit **列表**？以及如何聲明BucketList？ –

在傳統的Java哈希表中，每個存儲桶只是放置哈希鏈的第一個鏈接的地方。所以'bucket'數組應該是'HashChainNode []' –

BucketList 一般是 – Rawsick

我覺得鏈式哈希表確實是哈希表的哈希表，這樣你就不必四處跳動表時，你有鑰匙的碰撞它映射你的散列鍵到一個Hashtable。

您需要使用HashTable LinkedLists而不是HashTable HashTables來尋求變體。

在一個基本的HashTable中，您需要計算下一個索引，以便在發生關鍵衝突時進行嘗試，基本上，您使用bucketIndex %= BUCKET_COUNT;但是使用鏈式HashTable您不這樣做。您的數組不是將您的元素插入到底層數組中的索引位置，而是您的HashTables數組（或您的案例中的LinkedLists數組），並將您的元素插入到該集合中。

來源

2016-11-16 02:49:49 Danny

在每個存儲桶位置存儲鏈接列表的鏈式散列表（或使用*分開鏈接*的散列表）。它不是「散列表的散列表」。 –

所以從我收集你想實現一個哈希錶鏈接列表。我也看到了這條評論

BucketList一般 - Rawsick

所以讓我嘗試和實現該數據結構的組成部分。

讓我們從BucketList開始。因爲這聽起來像是一個Bucket，它具有定義桶的通用參數T以及桶中的內容。我要重構它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中一些流行的集合實現的源代碼。你會更好地瞭解如何解決這樣的問題。

查看谷歌的Gauva庫。查看一些像MultiMap這樣的複雜集合，並查看它們是如何實現的。

來源

2016-11-16 03:36:31 abhipil

鏈式哈希錶鏈接列表

回答

相關問題