链式哈希表链接列表

我应该制作一个链式哈希表来将每个存储桶中的名称作为链接列表。我知道如何使用具有一个值的桶进行此操作，但我不知道如何在每个桶中放置链接列表。我有一个人姓名和姓氏，以及哈希码类。我写了删除，但我不知道如何将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

链式哈希表链接列表

回答

相关问题