La mise en œuvre d'une carte générique en utilisant une table de hachage en Java

Question

post Détails
Dans les structures de données cours, on m'a donné le code source Java pour une classe « du second degré de sondage de table de hachage » et demandé de mettre en œuvre une carte générique (avec obtenir et mettre méthodes) et stocker les paires clé/définition dans une table de hachage. Je comprends le matériau lors de la lecture du livre mais trouve qu'il est difficile de l'implémenter dans un langage de programmation (Java). Je pense qu'une partie du problème consiste à comprendre exactement ce que la question nécessite et une partie est une déficience dans l'expérience de programmation Java. J'espère recevoir quelques suggestions sur la façon dont je peux aborder des problèmes comme celui-ci et remplir toutes les connaissances Java qui me manquent.

Quelques questions que j'ai eu
Quelle est la fonction de la classe de table de hachage par rapport à la carte générique je suis censé créer? La table de hachage a plusieurs méthodes dont se, insert, enlever, resucée, etc ... est le but de la table de hachage pour générer une valeur de hachage à utiliser comme une clé dans la classe de carte? Les clés et les définitions sont-elles stockées dans la table de hachage ou seront-elles stockées sur la carte? Quel est le point de faire une carte si la table de hachage fait déjà tout cela? Est-ce que quelqu'un peut m'aider à comprendre comment aborder des problèmes comme celui-ci? Quelles sont les références qui pourraient m'aider, que ce soit spécifiquement avec cette question ou avec la façon de compléter efficacement et méthodiquement ce type d'exercice?

J'apprécie toute l'aide que je peux obtenir. J'inclus le code du livre pour aider à illustrer le problème.

Quadratique Probing Code Hash Table De Manuel

public class QuadraticProbingHashTable<AnyType> { 

    public QuadraticProbingHashTable() { 
     this(DEFAULT_TABLE_SIZE); 
    } 

    public QuadraticProbingHashTable(int size) { 
     allocateArray(size); 
     doClear(); 
    } 

    public boolean insert(AnyType x) { 
     int currentPos = findPos(x); 
     if(isActive(currentPos)) return false; 

     array[currentPos] = new HashEntry<>(x, true); 
     theSize++; 

     if(++occupied > array.length/2) rehash(); 

     return true; 
    } 

    private void rehash() { 
     HashEntry<AnyType>[] oldArray = array; 

     allocateArray(2 * oldArray.length); 
     occupied = 0; 
     theSize = 0; 

     for(HashEntry<AnyType> entry : oldArray) 
      if(entry != null && entry.isActive) insert(entry.element); 
    } 

    private int findPos(AnyType x) { 
     int offset = 1; 
     int currentPos = myhash(x); 

     while(array[currentPos] != null && !array[currentPos].element.equals(x)) { 
      currentPos += offset; 
      offset += 2; 
      if(currentPos >= array.length) currentPos -= array.length; 
     } 

     return currentPos; 
    } 

    public boolean remove(AnyType x) { 
     int currentPos = findPos(x); 
     if(isActive(currentPos)) { 
      array[currentPos].isActive = false; 
      theSize--; 
      return true; 
     } else return false; 
    } 

    public int size() { 
     return theSize; 
    } 

    public int capacity() { 
     return array.length; 
    } 

    public boolean contains(AnyType x) { 
     int currentPos = findPos(x); 
     return isActive(currentPos); 
    } 

    public AnyType get(AnyType x) { 
     int currentPos = findPos(x); 
     if(isActive(currentPos)) return array[currentPos].element; 
     else return null; 
    } 

    private boolean isActive(int currentPos) { 
     return array[currentPos] != null && array[currentPos].isActive; 
    } 

    public void makeEmpty() { 
     doClear(); 
    } 

    private void doClear() { 
     occupied = 0; 
     for(int i = 0; i < array.length; i++) array[i] = null; 
    } 

    private int myhash(AnyType x) { 
     int hashVal = x.hashCode(); 

     hashVal %= array.length; 
     if(hashVal < 0) hashVal += array.length; 

     return hashVal; 
    } 

    private static class HashEntry<AnyType> { 
     public AnyType element; 
     public boolean isActive; 

     public HashEntry(AnyType e) { 
      this(e, true); 
     } 

     public HashEntry(AnyType e, boolean i) { 
      element = e; 
      isActive = i; 
     } 
    } 

    private static final int DEFAULT_TABLE_SIZE = 101; 

    private HashEntry<AnyType>[] array; 
    private int occupied; 
    private int theSize; 

    private void allocateArray(int arraySize) { 
     array = new HashEntry[nextPrime(arraySize)]; 
    } 

    private static int nextPrime(int n) { 
     if(n % 2 == 0) n++; 

     for(; !isPrime(n); n += 2) ; 

     return n; 
    } 

    private static boolean isPrime(int n) { 
     if(n == 2 || n == 3) return true; 

     if(n == 1 || n % 2 == 0) return false; 

     for(int i = 3; i * i <= n; i += 2) 
      if(n % i == 0) return false; 

     return true; 
    } 
} 

Carte Skeleton De Manuel

class Map<KeyType,ValueType> { 
    public Map() 

    public void put(KeyType key, ValueType val) 
    public ValueType get(KeyType key) 
    public boolean isEmpty() 
    public void makeEmpty() 

    private QuadraticProbingHashTable<Entry<KeyType,ValueType>> items; 

    private static class Entry<KeyType,ValueType> { 
     KeyType key; 
     ValueType value; 
    } 
} 

Answer 1

En général, ce que vous êtes confronté à un problème de implementing un interface donné. Le Map est l'interface - le HashTable est un moyen de l'implémenter, la structure de données sous-jacente. Cependant, je comprends votre confusion car la définition du HashTable qui vous a été fournie semble mal adaptée au travail car elle ne semble pas avoir l'option d'utiliser une clé personnalisée (au lieu de toujours se fier au code de hachage de l'objet) pour calculer le hachage) ni n'a une option pour avoir un HashEntry personnalisé. Comme la question est spécifiée, je dirais que la réponse est "vous ne pouvez pas". Généralement, implémenter un Map sur un HashTable revient à manipuler les collisions - une approche, qui n'est pas très efficace mais qui fonctionne habituellement, est que chaque fois que vous trouvez une collision (un cas où vous avez des clés différentes mais les mêmes hachages), vous ressentez table entière jusqu'à ce que la collision ne soit plus là. La réponse la plus communément adoptée est d'avoir une table de hachage à plusieurs niveaux, qui stocke récursivement une hashtable (calculant une fonction de hachage différente) à chaque niveau. Une autre méthode consiste à avoir une table de hachage - où les tableaux stockent eux-mêmes des listes d'éléments avec le même hachage - et ressasser si le nombre de collisions est trop grand. Malheureusement, aucune de ces solutions n'est directement implémentable avec la classe d'échantillon qui vous a été fournie.Sans plus de contexte, je ne peux pas en dire plus, mais cela semble être un exercice mal conçu (cela vient de quelqu'un qui torture parfois des élèves avec des choses semblables).

Une façon de pirater cela dans votre cadre crée un type Pair dont la fonction hashCode calcule simplement key.hashCode(). De cette façon, en tant que valeur, vous pouvez stocker un tableau (et ensuite utiliser l'approche de tableau mentionnée ci-dessus) ou vous pouvez stocker un seul élément (et ensuite utiliser l'approche rehash). Dans les deux solutions, la résolution de la gestion des collisions est l'élément le plus difficile (vous devez gérer les cas où la HashTable votre Pair, mais la value partie de la paire ne equals() l'élément que vous souhaitez insérer.