Întrebări în interviu

În primul rând, ce este HashMap. HashMap este o matrice asociativă. Pe scurt, o matrice asociativă este o structură de date care stochează perechi cheie-valoare.







Pentru a face mai ușor să înțelegeți ce este, puteți reprezenta HashMap ca coșuri numerotate în care sunt stocate date (Figura 1). Când adăugați un nou obiect în HashMap. În plus față de obiectul însuși, trecem de asemenea o cheie, care va fi găsită mai târziu.

Cum poate fi determinată poziția obiectului de cheia? Pentru aceasta trebuie să știm codul hash al cheii. De unde pot să obțin? Totul este foarte simplu, dacă înțelegem că orice obiect din java poate acționa ca o cheie. Toți știu că obiectul de clasă implementează metoda hashCode (), ceea ce înseamnă că va fi moștenit sau redefinit de "cheia" în sine. pentru că toate în Java sunt moștenite din clasa Object. Acum este clar unde cheia vine de la hashCode!

Odată ajuns în hashMap. Tasta + obiectul stocat a fost trecut, funcția hash specială calculează ce coș să includă datele noastre.

După cum înțelegeți, nu există coșuri în HashMap. În schimb, există o matrice care stochează linkuri către liste în care datele noastre sunt stocate. Fiecare element de matrice are o singură listă.

Această întrebare pe care nu am întrebat-o niciodată, am găsit-o pe hubr. Răspunsul este 16. Dar, ca și în cazul ArrayList, puteți specifica un număr diferit în constructor.

Această întrebare este de asemenea comună. O coliziune este atunci când două obiecte diferite intră într-un coș (listă legată). Motivul pentru aceasta este că aceștia au același hashcode. Pentru o lucrare mai eficientă cu HashMap, codul hash nu trebuie repetat pentru obiecte care nu sunt echivalente.

După cum am menționat mai sus, toate datele sunt stocate în liste. De ce este așa? De ce să nu stocați numai un singur obiect? Răspunsul este simplu. Toate pentru că este o modalitate de a rezolva coliziunile. Cum apare adăugarea? Cod de examinare 1

  • În primul rând, aflăm ce coș corespunde cheii obiectului. Apoi verificăm dacă există deja obiecte în el, dacă nu, apoi adăugați unul curent. Dacă da, atunci a existat o coliziune.
  • Apoi începem să comparăm cheia și hashcode-ul obiectului curent și cele care sunt înăuntru (dacă există mai multe dintre ele, desigur).
  • În primul rând, verificăm dacă tastele hashcode sunt egale.
  • Dacă da, comparăm cheia lor cu metoda equals.
  • Dacă egalurile returnează true, atunci cheile se potrivesc cu "value" și hashcode - înlocuirea este făcută, noul obiect înlocuiește cel care există deja sub aceeași cheie,
  • Dacă hashcode și "value" ale cheii sunt inegale - la sfârșitul listei se adaugă un obiect nou.






HashMap are un câmp loadFactor. Acesta poate fi specificat prin constructor. Valoarea implicită este de 0,75. Pentru ce este? Lucrarea sa asupra numărului de coșuri ne dă numărul necesar de obiecte care trebuie adăugate pentru a dubla numărul de coșuri. De exemplu, dacă avem un dosar cu 16 coșuri și loadFactor este de 0,75, extensia va avea loc atunci când adăugăm 16 * 0,75 = 12 obiecte. Dosarul este dublat.

Considerăm mai întâi cazul în care nu există coliziuni. În acest caz, adăugarea, ștergerea și căutarea obiectelor de către cheie se efectuează în timpul constant O (1). Desigur, nu se ia în considerare cazul extinderii numărului de elemente. În general vorbind, atunci când lucrați cu HashMap, este mai bine să specificați în proiectant cât de multe coșuri trebuie să lucrați și bine dacă este egal cu numărul de obiecte unice cu care veți lucra. În acest caz, nu trebuie să cheltuiți timpul și resursele pentru a crea un nou HashMap cu dublul numărului de găleți. De ce o astfel de performanță bună? Totul este simplu. Voi repeta că nu există coliziuni - în acest caz nu există nicio dependență de alte elemente din acest dosar. Ștergeți, inserați, căutarea este efectuată în aproximativ același mod. Se face cheia HashCode, se calculează coșul și se execută ștergerea, inserarea sau căutarea. Totul! Nu există alte obiecte nicăieri. Dar numai dacă nu există coliziuni.

Acum hai să vorbim despre cazul în care există încă coliziuni. Lucrând teoretic cu HashMap în care pot apărea coliziuni, obținem complexitatea temporară O (log (n)) pe operațiile de inserare, salvare și ștergere. În cel mai rău caz, când toate obiectele returnează același HashCode, și astfel intră într-un coș. De fapt, aceasta este o listă legată și apoi o complexitate temporară precum LinkedList O (n).

Asta e tot pentru moment. Mult noroc.

Pentru a înțelege că o persoană știe cu adevărat cum funcționează aceasta. Modul în care funcționează HashMap este necesar și nu pentru că este solicitat un interviu.

Aflați cum funcționează HashMap. Trebuie să cunoști programatorul. ce este interfața hărții. Și modul în care această interfață este implementată de Sun / Oracle este doar o chestiune de curiozitate. Există o mulțime de implementări ale interfeței Map (Google, Apache etc.) și ce ar trebui să facem cu privire la modul în care o face Oracle din interior? Este mult mai important pentru programator să știe că în cele din urmă metode native sunt utilizate pentru punerea în aplicare. Apoi mulți oameni cred că sunt utilizate matricele de java. Și cum Oracle construiește structuri interne nu este absolut importantă.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: