La mise en œuvre de la hashmap structure de données en java

Je vais avoir un test technique , l'énoncé du problème est donnée ci-dessous, je ne suis pas d'obtenir exactement ce que j'ai à faire, merci de m'aider pour le même en fournissant des exemples de 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.
Tout d'abord, commencer par le Chapitre 11. Regardez java de mise en oeuvre.
Les instructions que vous avez inclus dans votre question décrivez exactement ce que vous devez faire. Lire les livres et documents qui sont visés. Lire la javadoc de HashMap pour comprendre ce que les méthodes ne.
Cette question semble être hors-sujet, car il ne montre aucune tentative de l'auteur pour comprendre et résoudre le problème.

OriginalL'auteur astack | 2014-03-06

  1. 17

    Je crois que ça va être plus utile si j'explique HashMaps en anglais.

    Qu'est ce qu'une table de hachage?

    Une table de hachage est une structure de données qui est capable de cartographier certaines touches certaines valeurs. Les clés et les valeurs pourrait être n'importe quoi. Par exemple, si je devais faire un jeu, je pourrais le lien entre chaque nom d'utilisateur à une liste d'amis, représenté par une Liste de Chaînes de caractères.

    Pourquoi utiliser une table de hachage?

    HashMaps sont beaucoup plus rapide pour la récupération de données que les tableaux et les listes chaînées. Un tableau trié pourrait trouver une valeur particulière en O(log n) avec les binaires de recherche. Cependant, une HashMap pouvez vérifier si elle contient une touche particulière en O(1). Toutes les clés doivent être uniques.

    Comment HashMaps travail?

    HashMaps utiliser un tableau en arrière-plan. Chaque élément du tableau est une autre structure de données (généralement une liste chaînée ou binaire un arbre de recherche). La table de hachage utilise une fonction de la clé de déterminer où placer la valeur de la clé dans le tableau. Par exemple, si mon HashMap accepte les Chaînes...possible de fonctions de hachage peut être: 

    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.

    La valeur retournée sera de déterminer l'indice dont la valeur va dans le tableau.

    Mais Attendez! Il y a un Problème!

    Il est possible que la valeur retournée sera à l'extérieur de la matrice de limites. Par conséquent, nous sommes censés mod la valeur retournée par les matrices de longueur.

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

    Collisions:

    N'est-il pas possible que plusieurs touches de faire de la fonction de hachage générer le même indice? Oui. Par exemple, si nous avons utilisé la première fonction de hachage indiqué ci-dessus dans une table de hachage carte de cordes...tout deux Chaînes qui commencent par la même lettre sera donné le même index de tableau.

    Cela s'appelle une collision.

    Comment gérer les collisions?

    Une collision de la manipulation technique est appelée le Chaînage. Étant donné que chaque élément du tableau est une liste chaînée (ou structure de données similaires), plusieurs clés qui ont la même valeur de hachage sera placé dans la même liste, ou "seau". Par la suite, la valeur de hachage de la carte est capable de récupérer les valeurs en calculant le code de hachage avec la fonction de hachage, et la recherche sur le particulier lié liste pour voir si elle contient une valeur avec la même clé.

    Une bonne fonction de hachage doit être écrit afin d'éviter les collisions.

    Avantages à la Chaîne:

    -Tableau ne peut pas de débordement

    -Les données peuvent être facilement enlevés

    Inconvénients à la Chaîne:

    -Peut souffrir d'une dégradation des performances si seaux contiennent de très longues listes liées.

    Le nombre total d'entrées pour le nombre de compartiments est appelé le facteur de charge. Si le facteur de charge est trop faible, beaucoup d'espace est gaspillé. Si le facteur de charge est trop élevé, l'avantage de hachage est perdu. Un bon compromis sur le facteur de charge est .75

    Et encore, je ne comprends pas, donc en fait minime HashMap est à 3 composants chose : 1 régulier de la matrice de cellules -> à l'intérieur LinkedList(par exemple) -> à l'intérieur de chaque liste liée à la cellule 1 instance de la classe appelée Entrée (par exemple) avec 2 champs de la clé et la valeur . Suis-je le droit ?
    Oui je crois que c'est la façon dont il fonctionne.
    juste pour le rendre clair..les tableaux en second lieu, en se référant à la liste de tableaux et non des "tableaux"

    OriginalL'auteur Solace