Implementarea structurii de date hashmap în java [closed] (Programare, Java, Hash, Hashmap, Hashtable, Detectarea Coliziunii)

astack a intrebat.

Am un test tehnic, declarația problemei este dată mai jos, nu înțeleg ce anume trebuie să fac, vă rog să mă ajutați pentru același lucru, furnizând un cod de probă.

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.

Comentarii

  • În primul rând, începeți cu capitolul 11. Uitați-vă la implimentarea lui java. –  > Por Scary Wombat.
  • Instrucțiunile pe care le-ați inclus în întrebare descriu exact ceea ce trebuie să faceți. Citiți cărțile/documentele la care se face referire. Citiți javadoc-ul pentru HashMap pentru a înțelege ce fac metodele. –  > Por Jason.
  • Această întrebare pare a fi în afara subiectului, deoarece nu arată nicio încercare din partea autorului de a înțelege și de a rezolva problema. –  > Por Cameron Skinner.
1 răspunsuri
Solace

Cred că va fi mai util dacă voi explica HashMaps în engleză.

Ce este un HashMap?

Un HashMap este o structură de date care este capabilă să mapeze anumite chei la anumite valori. Cheile și valorile pot fi orice. De exemplu, dacă aș face un joc, aș putea lega fiecare nume de utilizator de o listă de prieteni, reprezentată de o listă de șiruri de caractere.

De ce să folosiți un HashMap?

HashMaps sunt mult mai rapide pentru a prelua date decât array-urile și listele legate. Un array sortat ar putea găsi o anumită valoare în O(log n) cu o căutare binară. Cu toate acestea, un HashMap poate verifica dacă conține o anumită cheie în O(1). Toate cheile trebuie să fie unice.

Cum funcționează HashMaps?

HashMaps utilizează o matrice în fundal. Fiecare element din matrice este o altă structură de date (de obicei o listă legată sau un arbore de căutare binar). HashMap utilizează o funcție asupra cheii pentru a determina unde să plaseze valoarea cheii în matrice. De exemplu, dacă HashMap-ul meu acceptă șiruri de caractere… posibilele funcții hash pot fi:

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.

Valoarea returnată va determina indexul în care valoarea va fi plasată în matrice.

Dar stați! Există o problemă!

Este posibil ca valoarea returnată să fie în afara limitelor array-ului. Prin urmare, ar trebui să modificăm valoarea returnată cu lungimea array-ului.

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

Coliziuni:

Nu este posibil ca mai multe chei să determine funcția hash să genereze același index? Da. De exemplu, dacă am folosit prima funcție hash prezentată mai sus într-o hartă hash de șiruri de caractere… orice două șiruri care încep cu aceeași literă vor primi același index de matrice.

Acest lucru se numește coliziune.

Cum gestionăm coliziunile?

O tehnică de tratare a coliziunilor se numește Chaining. Deoarece fiecare element din matrice este o listă legată (sau o structură de date similară), mai multe chei care au aceeași valoare hash vor fi plasate în aceeași listă legată sau „bucket”. Ulterior, harta hash poate prelua valorile prin calcularea codului hash cu ajutorul funcției hash și prin căutarea în lista legată respectivă pentru a vedea dacă aceasta conține o valoare cu aceeași cheie.

Pentru a evita coliziunile, trebuie scrisă o funcție hash bună.

Avantaje ale înlănțuirii:

-Rețeaua nu se poate supraîncărca.

-Datele pot fi eliminate cu ușurință.

Dezavantaje ale înlănțuirii:

Poate suferi o scădere a performanței în cazul în care bucket-urile conțin liste legate foarte lungi.

Numărul total de intrări raportat la numărul de găleți se numește factor de încărcare. Dacă factorul de încărcare este prea mic, se irosește mult spațiu. Dacă factorul de încărcare este prea mare, se pierde avantajul hashing-ului. Un compromis bun pentru factorul de încărcare este 0,75

Comentarii

  • Și tot nu înțeleg, deci, de fapt, HashMap-ul minim este format din 3 componente: 1 celulă de matrice obișnuită -> în interiorul LinkedList (de exemplu) -> în interiorul fiecărei celule de listă legată 1 instanță a clasei numită Entry (de exemplu) cu 2 câmpuri key și value . Am dreptate? –  > Por Danylo Gurianov.
  • Da, cred că așa funcționează. –  > Por Solace.
  • doar pentru a clarifica…array-urile din al doilea răspuns se referă la ArrayList și nu la „array-uri” – –  > Por Abdullah Khan.