eine generische Karte Implementierung in Java eine Hash-Tabelle

Question

Veröffentlichungsdetails Kurs
in einem Datenstruktur verwendet wurde, wurde ich Java-Quellcode für eine „quadratische Sondieren Hash-Tabelle“ Klasse gegeben und gebeten, eine generische Karte (mit zu implementieren get und setzen Methoden) und speichern Sie die Schlüssel/Definition-Paare in einer Hash-Tabelle. Ich verstehe das Material beim Lesen des Buches, finde es aber schwierig, es in einer Programmiersprache (Java) zu implementieren. Ich denke, ein Teil des Problems besteht darin, genau zu verstehen, was die Frage erfordert, und ein Teil ist ein Mangel an Java-Programmiererfahrung. Ich hoffe, dass ich einige Vorschläge bekomme, wie ich Probleme wie diese angehen kann und was Java-Kenntnisse ich vermisse.

Einige Fragen, die ich habe
habe Was ist die Funktion der Hash-Tabelle Klasse in Bezug auf die allgemeine Karte ich angeblich zu schaffen? Die Hash-Tabelle hat mehrere Methoden, einschließlich erhalten, Einsatz, entfernen, Aufguss, etc ... Ist der Zweck der Hash-Tabelle einen Hash-Wert zu verwenden als Schlüssel in der Karte Klasse zu generieren? Sind Schlüssel und Definitionen in der Hash-Tabelle gespeichert oder werden sie in der Karte gespeichert? Worauf kommt es an, eine Map zu erstellen, wenn die Hash-Tabelle das bereits erledigt?

Kann mir jemand helfen zu verstehen, wie man solche Probleme angehen kann? Was sind einige Hinweise, die mir helfen könnten, entweder speziell mit dieser Frage oder mit dem Verständnis, wie man diese Art von Übung effektiv und methodisch abschließt?

Ich schätze jede Hilfe, die ich bekommen kann. Ich schließe Code aus dem Buch ein, um das Problem zu veranschaulichen.

Quadratic Probing Hash Table-Code aus Lehrbuch

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; 
    } 
} 

Karte Skeleton Von Lehrbuch

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

Im Allgemeinen, was Sie mit Blick auf ein Problem der implementing ein gegebenes interface. Die Map ist die Schnittstelle - die HashTable ist ein Mittel zur Implementierung, die zugrunde liegende Datenstruktur.

Allerdings verstehe ich Ihre Verwirrung als die Definition der HashTable, die Sie zur Verfügung gestellt wurden scheint für den Job nicht geeignet, da es nicht eine Option, einen benutzerdefinierten Schlüssel verwenden zu haben scheint (stattdessen immer auf den Objekt-Hash-Code für die Berechnung des Hash) noch hat es eine Option, eine benutzerdefinierte HashEntry zu haben. Da die Frage spezifiziert ist, würde ich sagen, dass die Antwort "Sie können nicht" ist. Im Allgemeinen läuft die Implementierung einer Map auf einer HashTable auf die Handhabung von Kollisionen - ein Ansatz, der nicht sehr effektiv ist, aber normalerweise funktioniert, ist, dass Sie immer dann, wenn Sie eine Kollision finden (ein Fall, in dem Sie unterschiedliche Schlüssel aber die gleichen Hashes haben) ganze Tabelle bis die Kollision nicht mehr da ist. Die am häufigsten verwendete Antwort ist eine mehrstufige Hashtabelle, die im Grunde rekursiv eine Hashtabelle (berechnet eine andere Hash-Funktion) auf jeder Ebene speichert. Eine andere Methode ist eine Hashtabelle von Arrays - wobei die Arrays selbst Listen von Elementen mit demselben Hash speichern - und eine erneute Hash-Operation, wenn die Anzahl der Kollisionen zu groß ist. Leider ist keine dieser Lösungen mit der von Ihnen bereitgestellten Beispielklasse direkt implementierbar.Ohne weiteren Zusammenhang kann ich nicht wirklich mehr sagen, aber es scheint nur eine schlecht gestaltete Übung zu sein (das kommt von jemandem, der gelegentlich Schüler mit ähnlichen Dingen quält).

Eine Möglichkeit, dies in Ihrem Framework zu hacken, ist die Erstellung eines Pair-Typs, dessen hashCode-Funktion nur key.hashCode() berechnet. Auf diese Weise könnten Sie als Wert ein Array speichern (und dann den oben erwähnten Array-Ansatz verwenden) oder Sie könnten ein einzelnes Element speichern (und dann den Rehash-Ansatz verwenden). In beide Lösung ist die Kollisionsbehandlung löst das schwierigste Element (Sie haben Fälle zu behandeln, in denen die HashTable Ihre Pair, aber der value Teil des Paares nicht equals() das Element, das Sie einfügen möchten.