Chain Hash Table Список ссылок

Question

Я должен создать цепочку хеш-таблицы, чтобы помещать имена в каждое ведро в качестве связанного списка. Я знаю, как это сделать с ведрами, которые содержат одно значение, но я не знаю, как поместить список ссылок в каждое ведро. У меня есть класс человека с именем и фамилией, а также с классом hashcode. Я написал удалить, но я не уверен, как поместить 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 действительно HashTable из HashTables, который отображает ваш хэш-ключ к HashTable, так что вам не придется прыгать вокруг стола, когда у вас есть ключевые столкновения.

Ваш запрос на вариант с помощью HashTable из LinkedLists вместо HashTable из HashTables.

В базовом HashTable вам нужно вычислить следующий индекс, чтобы попытаться получить ключевое столкновение, в основном то, что вы делаете с bucketIndex %= BUCKET_COUNT;, но с цепочкой HashTable вы этого не делаете. Вместо того, чтобы вставлять свой элемент в индексированное местоположение в вашем базовом массиве, ваш массив представляет собой массив HashTables (или массив LinkedLists в вашем случае), и вы вставляете свои элементы в эту коллекцию.

Answer 2

Итак, из того, что я собираюсь, вы хотите реализовать хеш-таблицу со связанными списками. Я также видел этот комментарий

BucketList обобщенно - Rawsick

Итак, позвольте мне попытаться реализовать части этой структуры данных.

Начнем с BucketList. Так как это звучит как просто Bucket с общим параметром 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.

Я бы посоветовал прочитать исходный код нескольких популярных реализаций коллекций в Java. Вы получите лучшее представление о том, как подойти к таким проблемам.

Проверьте библиотеку Gauva google. Посмотрите на некоторые из сложных коллекций, таких как MultiMap, и расскажите, как они их реализовали.