Implementierung der hashmap-Datenstruktur in java

Ich habe eine technische Prüfung , die Problematik ist hier gegeben, ich bin nicht immer so genau, was ich tun muss, bitte helfen Sie mir für die gleiche, indem Sie einige Beispiel-code.

Implement a hash-map data structure from scratch , where both key and value are of string data type.
The details of how a hash works can be found in Chapter 11 of the book "Introduction to
Algorithms" by Cormen, Leiserson, Rivest. You should also refer to Section 3.7 of "The
Algorithm Design Manual" by Steven Skiena. For the required hash-map implementation,
the following conditions hold true:
1. The key is made up of lower-case english alphabets only (a,b,c...z). It can be of any
length.
2. Values are of string data type.
3. The hash function to be used is the one given in Section 3.7 of Skiena.
4. Choose a suitable size of the hash-map, that is, the number of buckets. It should be
greater than 100.
4. Collisions will be resolved using Chaining. Doubly linked lists will be used to store
colliding entries.
You will have to implement the following operations on the hash-map:
a. Create an empty hash-map.
b. Insert a (key, value) pair into the hash-map.
c. Delete a (key) from the hash-map (if present).
d. Search for a (key) in the hash-map, and if present return its value. Else return null.

Thanks in advance.
Erstens, beginnen Sie mit Kapitel 11. Blick auf ' s java-Implementierung.
Die Anweisungen, die Sie in Ihrer Frage beschreiben Sie genau, was Sie tun müssen. Lesen Sie Bücher/Dokumente verwiesen. Lesen Sie die javadoc für die HashMap zu verstehen, was die Methoden tun.
Diese Frage scheint off-topic, weil es zeigt, dass kein Versuch, den Autor zu verstehen und das problem lösen.

InformationsquelleAutor astack | 2014-03-06

  1. 17

    Ich glaube, dass es hilfreicher sein, wenn ich erkläre, HashMaps in Englisch.

    Was ist eine HashMap?

    Einer HashMap ist eine Datenstruktur, die in der Lage ist, zum anzeigen bestimmter Tasten zu bestimmten Werten. Die Schlüssel und Werte können alles sein. Zum Beispiel, wenn ich ein Spiel, ich könnte jeden link username in eine Freunde-Liste, repräsentiert durch eine Liste von Strings.

    Warum eine HashMap?

    HashMaps sind viel schneller beim abrufen von Daten als arrays und verketteten Listen. Ein sortiertes array ein bestimmter Wert in O(log n) mit binärer Suche. Aber eine HashMap überprüfen können, ob es enthält einen speziellen Schlüssel in O(1). Alle Schlüssel müssen eindeutig sein.

    Wie HashMaps funktionieren?

    HashMaps verwenden Sie ein array in den hintergrund. Jedes element im array ist eine andere Datenstruktur (normalerweise eine verknüpfte Liste oder binary search tree). Die HashMap benutzt eine Funktion auf den Schlüssel, um zu bestimmen, wo der Schlüssel ist-Wert in das array. Zum Beispiel, wenn meine HashMap akzeptiert Strings...möglich, hash-Funktionen verwendet werden können: 

    A. Return the ASCII value of the first letter.
B. Return the sum of the ASCII values of every character in the String.
C. Return the ASCII value of the last character in the String.

    Den Wert, der zurückgegeben wird, bestimmen Sie den index, bei dem der Wert geht in das array.

    Aber Warten Sie! Es gibt ein Problem!!!

    Ist es möglich, dass der zurückgegebene Wert außerhalb der array-Grenzen. Deshalb sollen wir mod der zurückgegebene Wert durch die arrays der Länge.

    return Math.abs(number%hashMapArray.length);

    Kollisionen:

    Ist es nicht möglich, dass mehrere Schlüssel wird der hash-Funktion generieren, die den gleichen index? Ja. Zum Beispiel, wenn wir die erste hash-Funktion, die oben gezeigt in einer hash-map von strings...zwei beliebige Zeichenfolgen, die mit demselben Buchstaben beginnen, werden den gleichen array-index.

    Dies nennt man eine Kollision.

    Wie gehen wir mit Kollisionen?

    Einer Kollision Umgang mit Technik wird als Verkettung bezeichnet. Da jedes element im array ist eine verknüpfte Liste (oder ähnliche Datenstruktur), mehrere Schlüssel, die den gleichen hash-Wert wird in der gleichen Link-Liste oder "Eimer". Danach wird der hash-map ist in der Lage abrufen von Werten durch Berechnung der hash-code mit der hash-Funktion, und suchen in der verlinkten Liste zu sehen, ob es einen Wert enthält, mit dem gleichen Schlüssel.

    Eine gute hash-Funktion geschrieben werden muss, um Kollisionen zu vermeiden.

    Vorteile Verkettung:

    -Array nicht überlaufen

    -Daten können leicht entfernt werden

    Nachteile der Verkettung:

    -Erleiden einen Leistungseinbruch, wenn die Eimer enthalten sehr langen verketteten Listen.

    Die Gesamtzahl der Einträge, um die Anzahl der buckets genannt wird, die Auslastung ist. Wenn die Auslastung zu niedrig, wird eine Menge Platz verschwendet wird. Wenn die Auslastung zu hoch ist, der Vorteil von hashing ist verloren. Einen guten Kompromiss load-Faktor .75

    Und immer noch verstehe ich nicht, also eigentlich nur minimale HashMap ist 3-Komponenten-Sache : 1 Standard-array-Zelle -> innen LinkedList(zum Beispiel) -> im inneren jeder Zelle verknüpfte Liste 1 Instanz der Klasse aufgerufen Eintrag (zum Beispiel) mit 2 Felder, key und value . Bin ich im Recht ?
    Ja, ich glaube, das ist, wie es funktioniert.
    nur um es klar..arrays in die zweite Antwort bezieht sich auf ArrayList und nicht "arrays"

    InformationsquelleAutor Solace

Schreibe einen Kommentar