Java pitanja za intervju — Java kolekcijski okvir (Java kontejneri), 29 pitanja o Java kolekcijskom okviru (14.000 reči, 67 crteža), obavezno čitanje za pobedu na intervjuu 👍

Sanfen E10999 reči37 minuta

Naslovna slika pobede na intervjuu — kolekcijski okvir

Uvod

14.554 reči, 67 crteža, detaljno objašnjeno 29 najčešćih pitanja o Java kolekcijskom okviru na intervjuu (nema teških pitanja za učenje), kandidati koji nauče ova pitanja o Java kontejnerima, ovaj put će saboriti intervjutera, mislim da je sigurno (ručni pas). Sastavio: Chenmo Wang Er, pogledajlink za prenos, autor: Sanfen E, pogledajlink za original.

Svetla verzija je pogodnija za štampanje, što je i način koji mnogi studenti vole, štampanje učinkovitije uči.

Pobeda na intervjuu — kolekcijski okvir PDF drugo izdanje

decembra 2024. godine započeo sam drugo izdanje.

Za česta pitanja, označiću poziciju na kojoj se pojavljuju u „Vodiču za Java intervju (plaćeno)“, koja kompanija, koje je originalno pitanje, i dodaću 🌟, sadržaj je jasan; ako želite da uštedite vreme, možete prvo da učite ova pitanja, što pre možete da „poznaš neprijatelja i sebe, bezbicjedno u 100 bitaka“.
Razlikujem savršene odgovore od objašnjenja principa, da kandidati znaju „zašto“ i „kako“, a ujedno mogu efikasno da odgovaraju na intervjuu.
Kombinujem sa projektima (TehničkiPai, pmhub) u formiranju izraza, da intervjuter maksimalno oseti tvoju iskrenost, a ne mehaničko učenje.
Popravljao sam probleme iz prvog izdanja, uključujući privatne poruke članova, komentare sa sajta i GitHubissu, da bi ovaj vodič za intervju bio potpuniji.
Dodao sam ponude koje su članovi Erge programerske planete dobili, zahvalnice na „pobedi na intervjuu“, kao i priznanja za izmene biografija, da motivišem sve i dam više samopouzdanja.
Optimizovao sam format, dodao crteže, reorganizovao odgovore, da bi bili govorniji i bliži očekivanjima intervjutera.

Pobeda na intervjuu već je prosledila 1438 GitHub zapisa

Naravno, dozvolite mi mali ego — planetina PDF verzija će biti mesec dana ranija nego zvanični nalog, jer su članovi planetar platili, treba da prvi uživaju male benefite. Verujem da svi razumiju, jer je online verzija besplatna, a CDN, serveri, domeni, OSS itd. koštaju.

Nego mog utrošeno vreme i energiju, ako vam pomogne molim vas dajte reč, da i tvoji kolege, drugovi mogu da koriste.

Uključio sam Ergeov napredni put za Java, JVM napredni put, napredni put konkurentnog programiranja, kao i sve verzije „pobede na intervjuu“, pokriva Java osnove, Java kolekcije, Java konkurentnost, JVM, Spring, MyBatis, računarske mreže, operativne sisteme, MySQL, Redis, RocketMQ, distribuirane sisteme, mikroservise, dizajn paterne, Linux itd. 16 velikih tema, ukupno više od 400.000 reči, 2000+ crteža, zaista iskreno.

Prikažimo PDF tamnu verziju, format jasan, font elegantan, pogodniji za noćno čitanje, noću je ugodnije.

Pobeda na intervjuu — kolekcijski okvir PDF tamna verzija

Uvod

1.🌟Koje su česte kolekcijske okvire?

Preporučeno čitanje: Ergeov napredni put za Java: Java kolekcijski okvir
Preporučeno čitanje: Blokirajući red BlockingQueue.

Ergeov napredni put za Java: Osnovni odnosi Java kolekcija

Kolekcijski okvir može se podeliti na dve glavne grane:

①, Prva grana Collection, uglavnom se sastoji od List, Set, Queue:

List predstavlja uređene, ponovljive kolekcije, tipični predstavnik je ArrayList koja enkapsulira dinamičke nizove i LinkedList koja enkapsulira liste;
Set predstavlja neuređene, neponovljive kolekcije, tipični predstavnik su HashSet i TreeSet;
Queue predstavlja red, tipični predstavnik je dvostrani red ArrayDeque, kao i red prioriteta PriorityQueue.

②, Druga grana Map, predstavlja kolekciju parova ključ-vrednost, tipičan predstavnik je HashMap.

Druga verzija odgovora:

①, Collection interfejs: Osnovni način predstavljanja kolekcijskog okvira, obezbeđuje osnovne operacije kao što su dodavanje, brisanje, čišćenje, ima tri podinterfejsa:

List: Uređena kolekcija, može sadržati dupličirane elemente. Implementacije uključuju ArrayList, LinkedList itd.
Set: Kolekcija koja ne sadrži dupličirane elemente. Implementacije uključuju HashSet, LinkedHashSet, TreeSet itd.
Queue: Kolekcija za održavanje reda elemenata. Implementacije uključuju PriorityQueue, ArrayDeque itd.

②, Map interfejs: Predstavlja kolekciju parova ključ-vrednost, jedan ključ se mapira na jednu vrednost. Ključevi ne mogu biti duplićirani, svaki ključ odgovara samo jednoj vrednosti. Implementacije Map interfejsa uključuju HashMap, LinkedHashMap, TreeMap itd.

Koji su česti alati za rad sa kolekcijama?

Kolekcijski okvir se nalazi u java.util paketu, obezbeđuje dva česta alata:

Collections: Obezbeđuje neke statičke metode za sortiranje, binarnu pretragu, sinhronizaciju kolekcija.
Arrays: Obezbeđuje neke statičke metode za sortiranje nizova, štampanje, i konverziju u List.

Krako predstavi red

U Javi se redovi uglavnom realizuju kroz Queue interfejs i BlockingQueue interfejs iz konkurentnog paketa.

Red prioriteta PriorityQueue je neograničen red, elementi su sortirani po prirodnom redosledu ili Comparator upoređivaču.

Dvostrani red ArrayDeque je red zasnovan na nizu, može da umetne i briše elemente na oba kraja.

LinkedList implementira podinterfejs Deque od Queue interfejsa, takođe može da se koristi kao dvostrani red.

Koje kolekcije si koristio, koje su prednosti i mane?

Često koristim ArrayList, LinkedList, HashMap, LinkedHashMap.

ArrayList može da se posmatra kao dinamički niz, može dinamički da proširi kapacitet niza kada je potrebno, samo treba da kopira elemente u novi niz. Prednost je brzina pristupa, može direktno preko indeksa da pronađe element. Mana je što umetanje i brisanje elemenata može zahtevati pomeranje ili kopiranje elemenata.
LinkedList je dvostruko spregnuta lista, pogodna za česta umetanja i brisanja. Prednost je što pri umetanju i brisanju elemenata treba samo promeniti pointere prethodnog i sledećeg čvora, mana je što pristup elementu zahteva obilazak liste.
HashMap je kolekcija parova ključ-vrednost zasnovana na heš tabeli. Prednost je što može brzo da pronađe vrednost preko heš vrednosti ključa, ali se može desiti heš kolizija, i ne čuva redosled umetanja parova ključ-vrednost.
HashMap na osnovu HashMapa dodaje dvostruku spregnutu listu da bi čuvao redosled umetanja parova ključ-vrednost.

Koja je razlika između reda i steka?

Red je FIFO (First-In-First-Out) struktura podataka, prvi element koji se dodaje redu postaje prvi element koji se uklanja, pogodan za scenarije gde treba redosledno da se obrađuju zadaci, kao što su redovi poruka, raspoređivanje zadataka itd.

Stek je LIFO (Last-In-First-Out) struktura podataka, poslednji element koji se dodaje steku postaje prvi element koji se uklanja, pogodan za scenarije gde treba povratak, kao što je stek poziva funkcija, istorija pretraživača itd.

Koji kontejneri su sigurni za niti?

Vector, Hashtable, ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue, ArrayBlockingQueue, LinkedBlockingQueue su svi sigurni za niti.

Koji interfejse nasleđuje Collection?

Collection nasleđuje Iterable interfejs, što znači da sve klase koje implementiraju Collection interfejs moraju implementirati metodu iterator(), nakon toga mogu da koriste pojačanu for petlju za obilazak elemenata kolekcije.

Ergeov napredni put za Java: Collection izvorni kod

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua Youyonga Finans: Kolekcijske okvire koje poznaješ?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua Huawei: Reci o Java kontejnerima i HashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua E, letnji stažista Xiaomi: Kolekcije koje poznaješ?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 16, letnji stažista Meituan: Koje kolekcije znaš, reci razliku između HashMap i TreeMap, razliku u scenarijima primene; reci koje redove postoje, šta znači blokirajući red?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje Java backend intervjua 7, Agricultural Bank: Kolekcije koje si koristio, prednosti i mane
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 1, Huawei OD: Koja je razlika između reda i steka?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje Agricultural Bank 1: Način implementacije blokirajućeg reda
Vodič za Java intervju (plaćeno) sadrži originalno pitanje Java backend intervjua 1, zbirka malih kompanija: Koje su Java kontejneri? Koja je razlika između List, Set i Map?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua Java backend 3, 360: Koje su Java kolekcije
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 11, Huawei: Koje su tipovi Java kolekcija? Koje su sigurne za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 6, China Merchants Bank: Koje su Java kolekcije?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua Youyong: Možeš da navedeš nekoliko kolekcijskih kontejnera?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje tehničkog intervjua Java 12, BYD: Predstavi Java kolekcije
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 1, OPPO: Predstavi Java kolekcijski okvir
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 10, vivo: Koje su Java kolekcije

List

2.🌟Koja je razlika između ArrayList i LinkedList?

Preporučeno čitanje: Ergeov napredni put za Java: ArrayList i LinkedList

ArrayList je zasnovan na nizu, LinkedList je zasnovan na spregnutoj listi.

Sanfen E pobeda na intervjuu: ArrayList i LinkedList strukture podataka

Koje su različite namene ArrayList i LinkedList?

U većini slučajeva, ArrayList je bolja za pretragu, LinkedList je bolja za dodavanje i brisanje.

①, Zato što je ArrayList zasnovan na nizu, get(int index) može direktno preko indeksa niza da dobavi element, vremenska kompleksnost je O(1); LinkedList je zasnovan na spregnutoj listi, get(int index) treba da obilazi listu, vremenska kompleksnost je O(n).

Naravno, get(E element) ovakva pretraga, obe kolekcije treba da obilaze i upoređuju preko equals da dobave element, pa je vremenska kompleksnost O(n).

②, Ako ArrayList dodaje ili briše na kraju niza, vremenska kompleksnost je O(1); ako pri add-u uključuje proširivanje, vremenska kompleksnost može narasti na O(n).

Ali ako se umetne na sredinu, treba pomeriti elemente iza umetnutog mesta unapred ili unazad, čak može da pokrene proširivanje, efikasnost će biti mnogo niža, postaje O(n).

Sanfen E pobeda na intervjuu: ArrayList i LinkedList umetanje na sredinu

LinkedList zato što je spregnuta lista, umetanje i brisanje treba samo promeniti reference prethodnog čvora, sledećeg čvora i umetnutog čvora, ne treba pomerati elemente.

Ako se umetne ili obriše na početku liste, vremenska kompleksnost je O(1); ako se umetne ili obriše na sredini liste, vremenska kompleksnost je O(n), jer treba obilaziti listu da pronađe mesto umetanja; ako se umetne ili obriše na kraju liste, vremenska kompleksnost je O(1).

Sanfen E pobeda na intervjuu: ArrayList i LinkedList brisanje na sredinu

Dali ArrayList i LinkedList podržavaju random access?

①, ArrayList je zasnovan na nizu, takođe implementira RandomAccess interfejs, pa podržava random access, može preko indeksa direktno da dobavi element.

②, LinkedList je zasnovan na spregnutoj listi, ne može preko indeksa direktno da dobavi element, ne podržava random access.

Koja je razlika u memorijskoj zauzetosti ArrayList i LinkedList?

ArrayList je zasnovan na nizu, zauzima jedan kontinualni memorijski prostor, pa je memorijska zauzetost kompaktija; ali ako uključuje proširivanje, treba ponovo dodeliti memoriju, prostor je 1.5 puta originalni.

Ergeov napredni put za Java: ArrayList proširivanje

LinkedList je zasnovan na spregnutoj listi, svaki čvor ima pokazivač na sledeći i prethodni čvor, pa svaki čvor zauzima malo više memorijskog prostora nego ArrayList.

Koji su različiti scenariji upotrebe ArrayList i LinkedList?

ArrayList je pogodna za:

Čest random access: Scenariji gde treba često pristupati elementima preko indeksa.
Više operacija čitanja nego pisanja: Kao što je čuvanje lista koje se retko menjaju.
Dodavanje elemenata na kraju: Scenariji gde treba često dodavati elemente na kraj liste.

LinkedList je pogodna za:

Scenariji gde treba često umetati i brisati elemente na sredini liste.
Više sekwencijalnog pristupa nego random access.
LinkedList može realizovati red (FIFO) i stek (LIFO).

Koja je razlika između spregnute liste i niza?

Niz zauzima jedan kontinualni memorijski prostor, možemo brzo pristupiti bilo kom elementu preko indeksa niza. Niz prilikom kreiranja mora navesti veličinu, jednom se dodeli memorija, veličina niza je fiksna.
Elementi spregnute liste čuvaju se na bilo kojoj poziciji u memoriji, svaki čvor preko pokazivača pokazuje na sledeći čvor.

Razlika u memorijskoj zauzetosti niza i spregnute liste

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua stažista 10, JD backend: Vremenska kompleksnost ArrayList i LinkedList
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua E, letnji stažista Xiaomi: Kolekcije koje poznaješ?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua F, Xiaomi: Razlika i scenariji upotrebe ArrayList i LinkedList
Vodič za Java intervju (plaćeno) sadrži originalno pitanje tehničkog intervjua Java 12, BYD: Razlika između niza i spregnute liste
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 2, Kuaishou: Razlika ArrayList i LinkedList
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 9, Dewu: Koja je razlika između arraylist i linkedlist u kolekcijama? Koje su prednosti i mane?

memo: 7. septembra 2025. izmenjeno do ovde, danas dok sam pomagao članu da sredi biografiju, dobio sam povratne informacije da je prešao regularni zaposlenih u Ant Group. Nadam se da ćeš i ti proći intervju bezbedno i dobiti željenu ponudu.

3.Koji je mehanizam proširivanja ArrayList?

Znam. Kada se dodaje element u ArrayList, prvo proverava da li treba proširiti, ako trenutni kapacitet+1 premašuje dužinu niza, će se proširiti.

Sanfen E pobeda na intervjuu: ArrayList proširivanje

Posle proširivanja nova dužina niza je 1.5 puta originalna, zatim kopira vrednosti starog niza u novi niz.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 7, Lenovo: Predstavi Java kolekcije, izaberi jednu i opiši princip.

4.Kako ArrayList radi serializaciju?

U ArrayList-u je writeObject metoda prepisana, da bi se realizovala prilagođena logika serializacije: serijalizuje samo važeće podatke, jer kapacitet elementData niza obično veći od stvarnog broja elemenata, pri deklaraciji dodato je transient ključna reč.

Ergeov napredni put za Java: elementData

Zašto ArrayList ne serializuje direktno niz elemenata?

Razlog efikasnosti, niz može biti dužine 100, ali stvarno koristi 50, preostalih 50 se ne koristi, ne treba serializovati.

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Serijalizuj strukturu trenutnog ArrayList-a
    int expectedModCount = modCount;
    s.defaultWriteObject(); // Serijalizuj ne-transient polja
    // Serijalizuj veličinu niza
    s.writeInt(size);
    // Serijalizuj svaki element
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
    // Proveri da li je došlo do konkurentne izmene tokom serializacije
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

5.Šta je fail-fast?

fail—fast je mehanizam detekcije grešaka Java kolekcija.

Kada se iterator koristi za obilazak kolekcije, ako nit A za vreme obilaska, nit B izmeni sadržaj kolekcije, će se baciti Concurrent Modification Exception.

Iterator prilikom obilaska direktno pristupa sadržaju kolekcije, i za vreme obilaska koristi modCount promenljivu. Ako se sadržaj kolekcije promeni za vreme obilaska, promeniće se vrednost modCount. Svaki put pre nego što iterator koristi hashNext()/next() za obilazak sledećeg elementa, proverava da li je vrednost modCount promenljive jednaka expectedmodCount vrednosti, ako jeste, vrši se obilazak; inače baca izuzetak, prekida obilazak.

Uslov bacanja izuzetka je detekovanje modCount!=expectedmodCount. Ako se pri promeni kolekcije modCount vrednost tačno postavi na expectedmodCount vrednost, izuzetak neće biti bačen. Zato se ne može osloniti na ovaj izuzetak za programiranje konkurentnih operacija, ovaj izuzetak se samo preporučuje za detekciju bugova konkurentnih izmena.

Kolekcije iz java.util paketa su fail-fast, ne mogu se koristiti u više nitima uz konkurentne izmene (izmene za vreme iteracije), na primer ArrayList klasa.

Šta je fail-safe (sigurnosno neuspeh)?

Kolekcioni kontejneri koji koriste mehanizam fail-safe, prilikom obilaska ne pristupaju direktno sadržaju kolekcije, već prvo kopiraju originalni sadržaj kolekcije, i obilaze kopiju.

Princip: Zato što se prilikom iteracije obilazuje kopija originalne kolekcije, izmene originalne kolekcije za vreme obilaska ne mogu detektovati iterator, pa neće pokrenuti Concurrent Modification Exception.

Mana: Prednost obilaska kopije je što izbjegava Concurrent Modification Exception, ali takođe iterator ne može pristupiti izmenjenom sadržaju, tj: iterator obilaza kopiju kolekcije dobijenu u trenutku početka obilaska, izmene originalne kolekcije za vreme obilaska iterator ne zna.

Scenariji: Kontejneri iz java.util.concurrent paketa su fail-safe, mogu se koristiti konkurentno u više nitima, konkurentne izmene, na primer CopyOnWriteArrayList klasa.

6.Koje metode postoje da se ArrayList učini sigurnom za niti?

Često se koriste dve.

Može koristiti Collections.synchronizedList() metodu, može vratiti List koji je siguran za niti.

SynchronizedList list = Collections.synchronizedList(new ArrayList());

Interno se realizuje kroz synchronized ključnu reč zaključavanje.

Takođe može direktno koristiti CopyOnWriteArrayList, to je ArrayList siguran za niti, prati princip copy-on-write, svaki put kada se izmeni lista, kreira se nova kopija, ova nova kopija će zameniti staru listu, a sve operacije čitanja stare liste se i dalje vrše na originalnoj listi.

CopyOnWriteArrayList list = new CopyOnWriteArrayList();

Prosto rečeno, CopyOnWrite znači kada dodamo element u kontejner, ne dodamo direktno u kontejner, već prvo kopiramo novi kontejner, zatim u novom kontejneru dodamo element, nakon dodavanja, referencu originalnog kontejnera pokazujemo na novi kontejner. Više niti pri čitanju ne treba zaključavanje, jer trenutni kontejner neće dodati nikakav element. Tako se realizuje sigurnost niti.

Koja je razlika između ArrayList i Vector?

Vector priposta ostacima iz perioda JDK 1.0, ne preporučuje se, i dalje postoji zato što Java želi da održi kompatibilnost unazad.

ArrayList je uveden u JDK 1.2, da zameni Vector kao glavnu nesinhronizovanu implementaciju dinamičkog niza. Zato što sve metode Vector-a koriste synchronized ključnu reč za sinhronizaciju, efikasnost je niža u okruženju jedne niti.

Ergeov napredni put za Java: Vector izvorni kod

Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 6, China Merchants Bank Zhaoyin Network Technology: Metodi da se nesigurne kolekcije učine sigurnim za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 2, BYD: Razlika između ArrayList i Vector

7.Šta znaš o CopyOnWriteArrayList?

CopyOnWriteArrayList je verzija ArrayList sigurna za niti.

CopyOnWrite——copy-on-write, već jasno pokazuje princip.

CopyOnWriteArrayList koristi strategiju razdvajanja čitanja i pisanja. CopyOnWriteArrayList kontejner dozvoljava konkurentno čitanje, operacije čitanja su bez zaključavanja. Š se tiče operacija pisanja, na primer dodavanje elementa u kontejner, prvo kopira trenutni kontejner, zatim izvršava operaciju pisanja na novoj kopiji, nakon završetka referencu originalnog kontejnera pokazuje na novi kontejner.

Sanfen E pobeda na intervjuu: CopyOnWriteArrayList princip

Map

U Map-u je najvažniji HashMap, na intervjuu se gotovo uvijek pita, moraš se dobro pripremiti.

8.🌟Možeš reći koja je podna struktura HashMap-a?

Preporučeno čitanje: Ergeov napredni put za Java: Detaljno HashMap

Podna struktura HashMap u JDK 8 jeniz+spregnuta lista+crveno-crno stablo.

Sanfen E pobeda na intervjuu: JDK 8 HashMap struktura podataka

Niz služi za čuvanje parova ključ-vrednost, svaki par može se dobiti direktno preko indeksa, indeks se dobija daljnjom hash() obradom heš vrednosti ključa.

Kada više ključeva nakon heš obrade dobije isti indeks, treba rešiti heš koliziju kroz spregnutu listu——parove ključ-vrednost sa istim indeksom čuvaju se kroz spregnutu listu.

Međutim, kada je spregnuta lista predugačka, efikasnost pretrage će biti niža, pa kada dužina spregnute liste premaši 8 (i dužina niza je veća od 64), spregnuta lista će se pretvoriti u crveno-crno stablo. Efikasnost pretrage crveno-crnog stabla je O(logn), brže od O(n) spregnute liste.

hash() metoda cilja da koliko je moguće više smanji heš kolizije, osigurava ravnomernu distribuciju elemenata na svakoj poziciji niza.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Ako heš vrednost ključa već postoji u nizu, odgovarajuća vrednost će biti preklopljena novom vrednošću.

Početni kapacitet HashMap je 16, kako se elementi stalno dodaju, HashMap treba da se proširi, prag jecapacity * loadFactor, capacity je kapacitet, loadFactor je faktor opterećenja, podrazumevano 0.75.

Posle proširivanja veličina niza je 2 puta originalna, zatim ponovo računa heš vrednost svakog elementa, i stavlja u novi niz.

Šta radi faktor opterećenja?

Faktor opterećenja (load factor) je broj između 0 i 1, služi za merenje stepena popunjenosti heš tabele. Predstavlja odnos broja elemenata smeštenih u heš tabeli i kapaciteta heš tabele.

Faktor opterećenja previsok (blizu 1) će dovesti do povećanja heš kolizija, utiče na efikasnost operacija pretrage, umetanja i brisanja.
Faktor opterećenja prenizak (blizu 0) će ugroziti memoriju, jer u heš tabeli postoji mnogo nekorišćenog prostora.

Podrazumevani faktor opterećenja je 0.75, ova vrednost daje dobar balans između vremenske i prostorne efikasnosti.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua redovnog stažista 25, Xiaomi: Opiši princip HashMap-a
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua Huawei: Reci o Java kontejnerima i HashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua Huawei: Reci o razlici Redis i HashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua državnog preduzeća: Reci podnu strukturu HashMap, konverziju spregnute liste i crveno-crnog stabla, dužinu HashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua K, letnji regrutacija Xiaomi: Reci strukturu podataka HashMap i neke važne parametre
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 16, Tencent Cloud Zhi: Podna implementacija HashMap, zašto nije siguran za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 1, Kuaishou glavna stanica tehnički odsek: Koja je struktura HashMap?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 1 Wenxin Yiyan 25 stažista Java backend: princip podne implementacije hashmap, tok implementacije put() metode, mehanizam proširivanja?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 27, Tencent cloud backend tehnički: Podna implementacija Hashmap? Zašto spregnuta lista postaje crveno-crno stablo? Zašto ne koristi balansirano binarno stablo?

memo: 24. septembra 2025. izmenjeno do ovde. Danas član mi je poslao privatnu poruku, pohvalio je „pobedu na intervjuu“, rekao da je veoma korisno, nedavno je dobio ponudu China Merchants Bank Zhaoyin Network Technology.

9.Šta znaš o crveno-crnom stablu?

Crveno-crno stablo je samo-balansirajuće binarno stablo pretrage:

Svaki čvor je ili crven ili crn;
Koreni čvor je uvek crn;
Svi listovi su crni (NULL čvorovi na slici);
Dečiji čvorovi crvenog čvora moraju biti crni;
Sa svakog čvora do svakog lista svi jednostavni putevi sadrže isti broj crnih čvorova.

Sanfen E pobeda na intervjuu: Crveno-crno stablo

Zašto ne koristi binarno stablo?

Binarno stablo je osnovna struktura stabla, svaki čvor ima najviše dva dečija čvora, ali binarno stablo lako može pasti u ekstremne situacije, na primer ako se podaci unose uređeno, binarno stablo će degradirati u spregnutu listu, efikasnost pretrage će postati O(n).

Zašto ne koristi balansirano binarno stablo?

Balansirano binarno stablo ima više zahteva od crveno-crnog stabla, visina levog i desnog podstabla svakog čvora se može razlikovati najviše za 1, ova balansiranost visine garantuje odličnu efikasnost pretrage, ali pri umetanju i brisanju može zahtevati česta rotiranja za održavanje balansa stabla, troškovi održavanja su viši.

Zašto koristi crveno-crno stablo?

Vremenska kompleksnost pretrage spregnute liste je O(n), kada je dužina lista veća, performanse pretrage opadaju. Crveno-crno stablo je kompromisno rešenje, vremenska kompleksnost pretrage, umetanja, brisanja su sve O(log n).

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua Java backend 1, Ctrip: Zašto HashMap koristi crveno-crno stablo, uslov konverzije liste u stablo, pravila umetanja i brisanja crveno-crnog stabla
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 2, Kuaishou: Zašto HashMap koristi crveno-crno stablo?

10.Kako crveno-crno stablo održava balans?

Rotacijaibojenje.

①, Kroz levu i desnu rotaciju prilagođava strukturu stabla, izbjegava previše duboku jednu stranu.

Sanfen E pobeda na intervjuu: Leva rotacija

Sanfen E pobeda na intervjuu: Desna rotacija

②, Bojenje, popravlja crveno-crna pravila, time osigurava da visina stabla neće biti disbalansirana.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua Java backend 1, Ctrip: Zašto HashMap koristi crveno-crno stablo, uslov konverzije liste u stablo, pravila umetanja i brisanja crveno-crnog stabla

memo: 6. januara 2025. izmenjeno do ovde.

11.🌟Koja je putanja put metode HashMap?

Heš adresiranje → Obrada heš kolizije (spregnuta lista ili crveno-crno stablo) → Odredi da li treba proširiti → Umetni/preklopi čvor.

Sanfen E pobeda na intervjuu: Tok podataka HashMap umetanja

Detaljna verzija:

Prvi korak, kroz hash metodu dalje remeti heš vrednost, da bi se smanjile heš kolizije.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Drugi korak, vrši prvo proširivanje niza; i koristi heš vrednost i dužinu niza da bi modulskim operacijom odredio poziciju indeksa.

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Ako je trenutna pozicija prazna, direktno umetne par ključ-vrednost na tu poziciju; inače proverava da li je ključ prvog čvora na toj poziciji isti kao ključ novog čvora, ako je isti direktno preklopi vrednost, ako nije, znači da se desila heš kolizija.

Ako je spregnuta lista, novi čvor doda na kraj liste; ako dužina spregnute liste je veća ili jednaka 8, onda spregnutu listu pretvori u crveno-crno stablo.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // Ako je table prazna, prvo inicijalizuj
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // Izračunaj poziciju indeksa, i pronađi odgovarajuću kantu
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // Ako je kanta prazna, direktno umetni
    else {
        Node<K,V> e; K k;
        // Proveri da li se prvi čvor poklapa
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // Preklopi
        // Ako je čvor stabla, stavi u stablo
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // Ako je spregnuta lista, obiđi i umetni na kraj
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Ako dužina liste dostigne prag, pretvori u crveno-crno stablo
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // Preklopi
                p = e;
            }
        }
        if (e != null) { // Ako se pronađe poklapanje ključa, preklopi staru vrednost
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // Brojač izmena
    if (++size > threshold)
        resize(); // Proveri da li treba proširiti
    afterNodeInsertion(evict);
    return null;
}

Svaki put nakon umetanja novog elementa, proverava da li treba proširiti, ako je trenutni broj elemenata veći od praga (capacity * loadFactor), vrši proširivanje, veličina niza posle proširivanja je 2 puta originalna; i ponovo računa indeks svakog čvora, vrši redistribuciju podataka.

Ako prepisuješ samo equals metodu a ne hashCode, šta će se desiti pri put-u?

Ako prepisuješ samo equals metodu, ne prepisuješ hashCode metodu, dovestiće to da dva objekta koji su jednaki po equals imaju različite hashCode vrednosti, tako da će se dva objekta staviti na različite pozicije u nizu, pri get-u neće moći dobiti ispravnu vrednost.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua stažista 10, JD backend: Može li se prepisati samo jedna metoda hashcode i equals, ako se prepise samo equals a ne hashcode, šta će se desiti pri map put
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 1, Kuaishou glavna stanica tehnički odsek: Proces put metoda HashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 1 Wenxin Yiyan 25 stažista Java backend: princip podne implementacije hashmap, tok implementacije put() metode, mehanizam proširivanja?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 2, Kuaishou: Tok elemenata HashMap

12.Kako HashMap pronalazi elemente?

Preko heš vrednosti locira indeks → Locira kantu → Proveri prvi čvor → Obiđi spregnutu listu ili crveno-crno stablo da pronađe → Vrati rezultat.

Sanfen E pobeda na intervjuu: Tok pretrage HashMap

13.Kako je dizajnirana hash funkcija HashMap?

Prvo dobavi heš vrednost ključa, to je 32-bitna int vrednost, zatom XOR operacijom poveži gornjih 16 bita i donjih 16 bita heš vrednosti, time može garantovati ravnomernu heš distribuciju.

static final int hash(Object key) {
    int h;
    // Ako je key null, vrati 0; inače, koristi hashCode i remeti
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

14.Zašto hash funkcija može smanjiti heš kolizije?

Brz odgovor: Indeks heš tabele se računa kroz h & (n-1), n je kapacitet podnog niza; n-1 i neka heš vrednost rade & operaciju, ekvivalentno odsijecaju najniža 4 mesta. Ako je kapacitet niza mali, uzimanje samo donjih mesta h lako dovodi do heš kolizije.

Kroz XOR operaciju uvodi gornje bitove h u donje bitove, može povećati randomičnost heš vrednosti, time smanjuje heš kolizije.

Objasni.

Ergeov napredni put za Java: hash funkcija u JDK 8

Uzmimo primer početne dužine 16, 16-1=15. Binarno je0000 0000 0000 0000 0000 0000 0000 1111. Uzimanje samo poslednjih 4 bitova znači da se gornji bitovi heš vrednosti odbacuju.

Sanfen E pobeda na intervjuu: hash & operacija

Na primer 1111 1111 1111 1111 1111 1111 1111 1111, uzmi poslednjih 4 bitova, to je 1111.

1110 1111 1111 1111 1111 1111 1111 1111, uzmi poslednjih 4 bitova, takođe 1111.

Zar se nije desila heš kolizija?

Ovada hash funkcija (h = key.hashCode()) ^ (h >>> 16) dolazi do izražaja.

Sanfen E pobeda na intervjuu: schema hash funkcije

Nepotpisano pomeranje heš vrednosti za 16 bitova unapred znači da se gornjih 16 bitova originalne heš vrednosti pomera na poziciju donjih 16 bitova. Tako, gornjih 16 bitova i donjih 16 bitova originalne heš vrednosti mogu učestvovati u donjim bitovima konačnog izračuna indeksa.

Izbor 16 bitova zato što je polovina od 32-bitnog integera, ova obrada uzima u obzir informacije gornjih bitova, a potpuno ne zanemaruje originalne informacije donjih bitova, time se postiže fin balans.

Dajmo primer (dužina niza je 16).

Ključ prvog para: h1 = 0001 0010 0011 0100 0101 0110 0111 1000
Ključ drugog para: h2 = 0001 0010 0011 0101 0101 0110 0111 1000

Ako nema hash funkcije, direktno uzmi donja 4 bita, onda su donja 4 bita i h1 i h2 1000, to znači da će oba para biti stavljena na 8. poziciju niza.

Pogledajmo proces obrade hash funkcije.

①, Za izračun prvog ključah1:

Original: 0001 0010 0011 0100 0101 0110 0111 1000
Pomeraj: 0000 0000 0000 0000 0001 0010 0011 0100
XOR: ---------------------------------------
Rezultat: 0001 0010 0011 0100 0100 0100 0100 1100

②, Za izračun drugog ključah2:

Original: 0001 0010 0011 0101 0101 0110 0111 1000
Pomeraj: 0000 0000 0000 0000 0001 0010 0011 0101
XOR: ---------------------------------------
Rezultat: 0001 0010 0011 0101 0100 0100 0100 1101

Kroz gornji izračun, možemo videti dah1ih2nakonh ^ (h >>> 16)operacije dobijaju različite rezultate.

Sada, uzimajući u obzir da je dužina niza 16 (treba najniža 4 bita da odrede indeks):

Zah1najniža 4 bita su1100(u dekadnom sistemu 12)
Zah2najniža 4 bita su1101(u dekadnom sistemu 13)

Tako,h1ih2će biti stavljene na 12. i 13. poziciju niza, time se izbjegava heš kolizija.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 2, Alipay letnja regrutacija: Zašto se koristi XOR operacija gornjih i donjih bitova? Zašto mora biti XOR gornjih i donjih 16 bitova?

15.Zašto je kapacitet HashMap stepen dvojke?

Da bi brzo locirao elemente u podnom nizu.

HashMap kroz hash & (n-1) locira indeks elemenata, n je veličina niza, to jest kapacitet podnog niza HashMap.

Dužina niza-1 upravo odgovaraju „maski donjih bitova“——donji bitovi maske su najbolje svi 1, inače & operacija nema smisla, rezultat je uvek 0.

Stepen dvojke je paran broj, paran broj-1 je neparan broj, binarna poslednja cifra neparnog broja je 1, time garantuje hash &(length-1) poslednja cifra može biti 0 ili 1 (zavisi od heš vrednosti), time može garantovati ravnomernu distribuciju heš vrednosti.

Drugo rečeno, rezultat & operacije je da sve gornje bitove heš vrednosti postavlja na nulu, samo čuva donje bitove.

a&b rezultat: A, b odgovarajući bitovi su istovremeno 1, rezultat je 1, inače 0. Na primer 5&3=1, 5 binarno je 0101, 3 binarno je 0011, 5&3=0001=1.

Pretpostavimo da je neka heš vrednost binarno 10100101 11000100 00100101, koristimo je za & operaciju, pogledajmo rezultat.

Znamo da je početna dužina HashMap 16, 16-1=15, binarno je 00000000 00000000 00001111 (gornje bitove popunjavamo nulama):

     10100101 11000100 00100101
&     00000000 00000000 00001111
----------------------------------
     00000000 00000000 00000101

Budući da su svi gornji bitovi 15 nule, rezultat & operacije gornjih bitova sigurno je 0, ostaje samo 4 donja bita0101, to jest dekadno 5.

Tako će ključ sa heš vrednošću10100101 11000100 00100101 biti stavljen na 5. poziciju niza.

Da li postoji strategija optimizacije za pozicioniranje indeksa niza modulom dužine niza?

Brz odgovor: Strategija HashMap je da operaciju modula hash % table.length optimizuje u bitovnu operaciju hash & (length - 1).

Zato što kada je dužina niza stepen 2 na N, hash & (length - 1) = hash % length.

Na primer 9 % 4 = 1, 9 binarno je 1001, 4 - 1 = 3, 3 binarno je 0011, 9 & 3 = 1001 & 0011 = 0001 = 1.

Još jedan primer 10 % 4 = 2, 10 binarno je 1010, 4 - 1 = 3, 3 binarno je 0011, 10 & 3 = 1010 & 0011 = 0010 = 2.

Kada dužina niza nije stepen 2 na n, hash % length i hash & (length - 1) rezultati se ne poklapaju.

Na primer 7 % 3 = 1, 7 binarno je 0111, 3 - 1 = 2, 2 binarno je 0010, 7 & 2 = 0111 & 0010 = 0010 = 2.

S gledišta binarnog, hash / length = hash / $2^{n}$ = hash >> n, to jest pomeri hash desno n mesta, sada dobijaš količnik hash / $2^{n}$ .

Deo koji se pomera, onda je hash % $2^{n}$ , to jest ostatak.

$2^{n}$ binarna forma je 1, iza koje sledi n nula, pa $2^{n}$ - 1 binarna forma je n jedinica. Na primer 8 = $2^{3}$ , binarno je 1000, 7 = $2^{3}$ - 1, binarno je 0111.

hash % lengthoperacija je traženje ostatka hash podeljenog $2^{n}$ . U binarnom sistemu, rezultat ove operacije je vrednost najnižih n bitova binarne reprezentacije hash.

Zato što u operaciji modula $2^{n}$ , sve vrednosti iznad $2^{n}$ bita ne doprinose rezultatu, samo deo ispod ovog praga određuje ostatak.

Na primer 26 binarno je 11010, treba izračunati 26 % 8, 8 je $2^{3}$ , pa fokusiramo se na najniža 3 bita binarne reprezentacije 26: najniža 3 bita od 11010 su 010.

010 odgovara dekadnom 2, rezultat 26 % 8 je 2.

Kada se izvršihash & (length - 1), zapravo zadržava najniža n bitova binarne reprezentacije hash, svi gornji bitovi se brišu.

Dajmo primer, hash je 14, n je 3, to jest dužina niza je $2^{3}$ , to jest 8.

  1110 (hash = 14)
& 0111 (length - 1 = 7)
  ----
  0110 (rezultat = 6)

Zadržava najniža 3 bita od 14, gornji bitovi se brišu.

Ovako, dve operacije hash % length i hash & (length - 1) imaju savršenu zatvorenost. U računaru, brzina bitovnih operacija je daleko veća od operacije ostatka, jer računar suštinski prepoznaje samo binarno.

Šta je modul operacija?

U Javi se obično koristi % operator za označavanje ostatka, Math.floorMod() za modul.

Kada su operandi pozitivni, rezultat modul operacije i operacije ostatka je isti; samo kada se pojave negativni operandi, rezultati se razlikuju.

Količnik modul operacije teži ka negativnoj beskonačnosti; količnik operacije ostatka teži ka 0. To je osnovni razlog zbog kojeg se ove dve razlikuju pri postojanju negativnih brojeva.

Kada je dužina niza stepen 2 na n, modul/ostatak operaciju može zameniti bitovnom operacijom, efikasnije, jer računar suštinski prepoznaje samo binarno.

Na primer, 7 ostatak 3, i 7 modul 3, rezultat je 1. Zato što su oba zasnovana na operaciji deljenja, 7 / 3 količnik je 2, ostatak je 1.

Za HashMap, treba kroz hash % table.length da odredi poziciju elementa u nizu.

Na primer, dužina niza je 3, hash je 7, onda je rezultat 7 % 3 1, to jest može element staviti na poziciju indeksa 1.

Kada je hash 8, rezultat 8 % 3 je 2, to jest može element staviti na poziciju indeksa 2.

Kada je hash 9, rezultat 9 % 3 je 0, to jest može element staviti na poziciju indeksa 0.

Zar nije čudno, dužina niza je 3, upravo 3 pozicije su iskorišćene.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua K, letnja regrutacija Xiaomi: Zašto je stepen 2 kad počinje proširivanje Tok mehanizma proširivanja
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 2, Alipay letnja regrutacija: hashCode pozicioniranje indeksa niza modulom dužine niza, da li postoji strategija optimizacije?

16.Ako pri inicijalizaciji HashMap prosledim kapacitet 17, kako će to da obradi?

HashMap će kapacitet podesiti na najmanji stepen dvojke veći ili jednak 17, to jest 32.

Sanfen E pobeda na intervjuu: Izračun kapaciteta

Zato što je najbolje da veličina heš tabele bude stepen 2 na N, time može kroz (n - 1) & hash efikasno izračunati vrednost indeksa.

Objasni.

U konstruktoru inicijalizacije HashMap, postoji ovaj kod:

public HashMap(int initialCapacity, float loadFactor) {
 ...
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}

Prag threshold će se izračunati kroz metodu tableSizeFor().

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

①, int n = cap - 1; izbjegava direktno udvostručavanje kapaciteta kada je upravo stepen dvojke.

②, Zatim kroz stalno desno pomeranje (>>>) i OR operaciju sa samim sobom (|=), sva donja mesta binarne reprezentacije n postavlja na 1.

n |= n >>> 1; proširuje gornju 1 na sledeće mesto.
n |= n >>> 2; proširuje na sledeća dva mesta.
Tako redom, do n |= n >>> 16;, proširuje na poslednjih 16 mesta, time od gornje 1 do najnižeg mesta, svi postaju 1.

③, Ako je n manje od 0, znači da je cap negativan broj, direktno vrati 1.

Ako je n veće ili jednako MAXIMUM_CAPACITY (obično je $2^{30}$ ), vrati MAXIMUM_CAPACITY.

Inače, vrati n + 1, zato što su svi donji bitovi n 1, pa n + 1 je najmanji stepen dvojke veći od cap.

Da li pri inicijalizaciji HashMap treba proslediti kapacitet?

Ako unapred znaš da će Map čuvati mnogo parova ključ-vrednost, unapred navođenje dovoljno velikog početnog kapaciteta može smanjiti operacije re-heširanja uzrokovane proširivanjem.

Zato što pri svakom proširivanju, HashMap treba da postojeće elemente ubaci u novi niz, ovaj proces je relativno spor, naročito kada Map već ima mnogo podataka.

Naravno, preveliki početni kapacitet će ugroziti memoriju, naročito kada je stvarni broj elemenata mnogo manji od početnog kapaciteta. Ako ne navodeš početni kapacitet, HashMap će koristiti podrazumevani početni kapacitet 16.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje tehničkog intervjua 1, Qi An Xin: Map kolekcija pri upotrebi obično treba navesti vrednost kapaciteta? Zašto navesti? Mehanizam proširivanja?

17.Koje metode konstruisanja heš funkcija još poznaješ?

①, Metoda ostatka deljenjem:H(key)=key%p(p<=N),ključ se deli pozitivnim celim brojem p koji nije veći od dužine heš tabele, dobijeni ostatak je adresa, naravno HashMap ima optimizaciju i modifikaciju, efikasnije, raspored je više balansiran.

Osim toga, postoje i sledeće česte metode konstruisanja heš funkcija:

②, Metoda direktnog adresiranja:Direktno prekokeymapira na odgovarajuću poziciju niza, na primer 1232 stavi na poziciju indeksa 1232.

③, Metoda analize cifara:Uzmi neke cifrekey(na primer desetice i stotine) kao poziciju mapiranja

④, Metoda sredine kvadrata:Uzmi nekoliko srednjih cifarakeykvadrata kao poziciju mapiranja

⑤, Podelikeyna segmente istog broja cifara, zatim njihov zbir kao poziciju mapiranja.

18.Koje metode postoje za rešavanje heš kolizija?

Skraćeni odgovor: Znam 3, metoda re-heširanja, metoda otvorenog adresiranja i metoda spregnute liste.

Šta je metoda re-heširanja?

Pripremi dva heš algoritma, kada se desi heš kolizija, koristi drugi heš algoritam, dok se ne pronađe prazno mesto. Zahtev za dizajn heš algoritma je relativno visok.

Šta je metoda otvorenog adresiranja?

Kada se desi heš kolizija, traži sledeće prazno mesto. Postoje 3 metode:

Linearna detekcija: Od pozicije kolizije, redom traži unazad, dok ne pronađe prazno mesto.
Kvadratna detekcija: Od pozicije kolizije x, prvi put povećaj $1^{2}$ pozicija, drugi put povećaj $2^{2}$ , dok ne pronađe prazno mesto.
Duplo heširanje: Slično re-heširanju, pripremi više heš funkcija, kada se desi kolizija, koristi drugu heš funkciju.

Sanfen E pobeda na intervjuu: Metoda spregnute liste VS metoda otvorenog adresiranja

Šta je metoda spregnute liste?

To jest metoda adrese liste, kada se desi heš kolizija, koristi spregnutu listu da spoji kolizione elemente. HashMap upravo koristi metodu spregnute liste.

Kako proveriti da su ključevi jednaki?

Zavisno odkeymetodaequals()ihashCode().

if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))

①, hashCode() :KoristikeymetoduhashCode()da izračuna heš kod ključa.

②, equals() :Kada su heš kodovi dvakeyista,HashMapće još pozvatikeymetoduequals()za precizno poređenje. Samo kadaequals()metoda vratitrue, dvakeyse smatraju potpuno istim.

Ako referenca dvakeypokazuje na isti objekat, onda će njihovehashCode()iequals()metode obe vratititrue, pa premo equals poređenju može prvo koristiti==operator jednom.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 2, Alipay letnja regrutacija: Kako HashMap rešava koliziju? Kako proveriti da su ključevi jednaki?

19.Zašto je prag konverzije spregnute liste u crveno-crno stablo 8?

Stablicanje se dešava kada je dužina niza table veća od 64, i dužina spregnute liste je veća od 8.

Zašto 8?

Sanfen E pobeda na intervjuu: Komentar izvornog koda

Veze sa statistikom. U idealnom slučaju, koristeći random heš kodove, čvorovi u listi sledi Poissonovu distribuciju, verovatnoća pojave broja čvorova je opadajuća, verovatnoća pojave 8 čvorova je samo 0.00000006.

To jest, u normalnim okolnostima, dužina spregnute liste od 8 je mali verovatni događaj.

8 je tačka balansa. Kada je dužina liste manja od 8, iako je pretraga O(n), zbog malog n stvarne performanse su prihvatljive, a memorijski troškovi liste su mali. Kada dužina liste dostigne 8, performanse pretrage su već relativno loše, u ovom trenutku prednost konverzije u crveno-crno stablo je relativno jasna, jer su vremenske kompleksnosti pretrage, umetanja, brisanja crveno-crnog stabla sve O(log n).

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 19, JD backend: Prag konverzije spregnute liste u crveno-crno stablo HashMap

memo: 9. avgusta 2025. izmenjeno do ovde. Danas čitatelj je dao povratne informacije, nedavno čita „pobedu na intervjuu“, verovatnoća pojave na intervjuu je vrlo visoka, mnoga druga standardna pitanja nisu pomenula, a ti si sumirao. Dobiti takve pozitivne povratne informacije, za me je zaista važno, hvala.

20.Kada se dešava proširivanje HashMap?

Kada broj parova ključ-vrednost premaši prag, to jest kapacitet * faktor opterećenja.

Ergeov napredni put za Java: HashMap proširivanje

Koliki je podrazumevani faktor opterećenja?

0.75.

Koliki je početni kapacitet?

1 levo pomereno 4 mesta, 0000 0001 → 0001 0000, to jest 2 na 4.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

Zašto koristiti 1 << 4 umesto direktno 16?

Pisati 1<<4 uglavnom da bi se naglasilo da je ova vrednost stepen dvojke, a ne potpuno slučajan izbor.

Bez obzira da li HashMap proširuje ili ne, dužina podnog niza treba biti stepen dvojke, jer može kroz bitovne operacije brzo izračunati indeks elementa.

Zašto izabrati 0.75 kao podrazumevani faktor opterećenja HashMap?

Ovo je empirijska vrednost. Ako je suviše niska, npr. 0.5, će ugroziti prostor; ako je suviše visoka, npr. 0.9, će povećati heš kolizije.

Ergeov napredni put za Java: Zašto izabrati 0.75

0.75 je najbolje rešenje koje su autori JDK-a potvrdili kroz veliku količinu verifikacije, može maksimalno smanjiti broj rehash operacija.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua K, letnja regrutacija Xiaomi: Zašto je stepen 2 kad počinje proširivanje Tok mehanizma proširivanja

memo: 7. januara 2025. drugo izdanje optimizovano do ovde.

21.🌟Koje je mehanizam proširivanja HashMap?

Pri proširivanju, HashMap kreira novi niz, čiji je kapacitet dvostruko originalni. Zatim obilazi elemente stare heš tabele, redistribuše ih u novu heš tabelu.

Ako u trenutnoj kanti ima samo jedan element, direktno kroz heš vrednost ključa i veličinu niza modulom zaključa novu poziciju indeksa: e.hash & (newCap - 1).

Ako je trenutna kanta crveno-crno stablo, pozvaće split() metodu da razdvoji čvorove stabla, da bi održalo balans stabla.

Ako je trenutna kanta spregnuta lista, kroz heš vrednost starog ključa i veličinu starog niza modul (e.hash & oldCap) == 0 kao uslov, ako je uslov tačan, element ostaje na poziciji originalnog indeksa; inače element se pomera na poziciju originalnog indeksa + veličina starog niza.

Koji problem postoji pri proširivanju u JDK 7?

JDK 7 pri proširivanju koristi metodu umetanja na početku za re-umetanje čvorova liste, time će dovesti do toga da lista ne može da održi originalni redosled.

Detaljno objasni.

JDK 7 kroz heš vrednost i veličinu niza-1 & operaciju određuje indeks elementa.

static int indexFor(int h, int length) {
    return h & (length-1);
}

Pretpustimo se:

Dužina niza table je 2
Heš vrednost ključa je 3, 7, 5

Posle modul operacije, ključevi su doživeli heš koliziju, svi trebaju da se stu u table[1] kantu. Pre proširivanja izgleda ovako:

Ergeov napredni put za Java: JDK7 pre proširivanja

Pretpostavimo da je faktor opterećenja loadFactor 1, to jest kada je broj elemenata veći od dužine table, vrši se proširivanje.

Kapacitet niza posle proširivanja je 4.

key 3 posle modula (3%4) je 3, stavlja se na table[3].
key 7 posle modula (7%4) je 3, stavlja se na početak table[3] liste.
key 5 posle modula (5%4) je 1, stavlja se na table[1].

Ergeov napredni put za Java: JDK7 posle proširivanja

Može se videti, zato što JDK koristi metodu umetanja na početku, 7 je trčala ispred 3, originalni redosled je bio 3, 7, 5, 7 je bila iza 3.

for (Entry<K,V> e : oldTable) {
    while (null != e) {
        Entry<K,V> next = e.next;
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    }
}

Najbolji slučaj je da posle proširivanja 7 ostaje iza 3, održava originalni redosled.

Kako JDK 8 rešava ovaj problem?

JDK 8 promenio je metodu umetanja na kraju, i kada (e.hash & oldCap) == 0, element ostaje na poziciji originalnog indeksa; inače element se pomera na poziciju originalnog indeksa + veličina starog niza.

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loHead != null)
    newTab[j] = loHead;
if (hiHead != null)
    newTab[j + oldCap] = hiHead;

Zato što se pri proširivanju dužina niza udvostručuje, na primer: 16 → 32, otuda, opseg indeksa novog niza je dvostruko veći od opsega originalnog indeksa.

Originalni indeks index = (n - 1) & hash, posle proširivanja novi indeks je index = (2n - 1) & hash.

To jest, ako (e.hash & oldCap) == 0, pozicija elementa u novom nizu je ista kao stara pozicija; inače, pozicija elementa u novom nizu je stara pozicija + veličina starog niza.

Pretpostavimo da je dužina niza pre proširivanja 16 (n-1 to jest binarno 0000 1111, 1X $2^{0}$ +1X $2^{1}$ +1X $2^{2}$ +1X $2^{3}$ =1+2+4+8=15), key1 je 5 (binarno 0000 0101), key2 je 21 (binarno 0001 0101).

key1 i n-1 & operacijom daju 0000 0101, to jest 5;
key2 i n-1 & operacijom daju 0000 0101, to jest 5.
Tada se desila heš kolizija, rešava se kroz metodu spregnute liste.

Sada, HashMap je proširen, kapacitet je 2 puta originalni, to jest 32 (n-1 to jest binarno 0001 1111, 1X $2^{0}$ +1X $2^{1}$ +1X $2^{2}$ +1X $2^{3}$ +1X $2^{4}$ =1+2+4+8+16=31).

key1 i n-1 & operacijom daju 0000 0101, to jest 5;
key2 i n-1 & operacijom daju 0001 0101, to jest 21=5+16, to jest pozicija pre proširivanja niza + dužina originalnog niza.

Sanfen E pobeda na intervjuu: Promena pozicije proširivanja

Time može izbjegati ponovno računanje heš vrednosti svih elemenata, samo potrebno je proveriti jedan gornji bit, može brzo odrediti novu poziciju.

Sanfen E pobeda na intervjuu: Schema migracije čvorova proširivanja

Da li pri proširivanju svaki čvor treba da izvrši bitovnu operaciju?

Ne treba. HashMap kroz (e.hash & oldCap) da proveri da li čvor treba da se pomera, 0 znači zadržati originalni indeks; 1 tek treba da se pomera na novi indeks (originalni indeks + oldCap).

Time izbjegava ponovno izračunavanje hashCode, značajno poboljšava performanse proširivanja.

Tako, čak i ako ima stotine hiljada podataka, možda samo pola podataka treba da se pomera na novu poziciju. Osim toga, brzina bitovnih operacija je vrlo brza, stoga, iako operacija proširivanja uključuje obilazenje cele heš tabele i ocenu svakog čvora, trošak ovog dela operacije je relativno nizak.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua K, letnja regrutacija Xiaomi: Zašto je stepen 2 kad počinje proširivanje Tok mehanizma proširivanja
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua E, letnji stažista Xiaomi: Reci mehanizam proširivanja HashMap, 1.8 specifična implementacija proširivanja
Vodič za Java intervju (plaćeno) sadrži originalno pitanje tehničkog intervjua 1, Qi An Xin: Map kolekcija pri upotrebi obično treba navesti vrednost kapaciteta? Zašto navesti? Mehanizam proširivanja?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 1 Wenxin Yiyan 25 stažista Java backend: princip podne implementacije hashmap, tok implementacije put() metode, mehanizam proširivanja?

memo: 9. avgusta 2025. izmenjeno do ovode. Danas dok sam pomagao članu da sredi biografiju, dobio sam ovakvu povratnu informaciju: hvala Erge što mi je barem prošao letnji staž, trenutno u Honor. Hvala svakoj povratnoj informaciji članova.

Reč člana stažiste Honor o izmeni biografije

22.Koje optimizacije JDK 8 radi na HashMap?

①, Podna struktura podataka iz niz + spregnuta lista promenjena u niz + spregnuta lista ili crveno-crno stablo.

Ako se više ključeva mapira na istu heš vrednost, lista će postati dugačka, u najgorem slučaju, kada se svi ključevi mapiraju u istu kantu, performanse će degradirati na O(n), a vremenska kompleksnost crveno-crnog stabla je O(logn).

②, Način umetanja spregnute liste iz umetanja na početku promenjen u umetanje na kraju. Umetanje na početku nakon proširivanja lako menja originalni redosled liste.

③, Vreme proširivanja iz određivanja pri umetanju promenjeno u određivanje posle umetanja, time može izbjegati nepotrebnu proveru proširivanja pri svakom umetanju, jer je moguće da posle umetanja i dalje nije potrebno proširivanje.

Ergeov napredni put za Java: Razlika vremena proširivanja JDK7 JDK8

④, Heš remećenje algoritam takođe je optimizovan. JDK 7 se realizuje kroz višestruka pomeranja i XOR operacije.

Ergeov napredni put za Java: hash metoda JDK 7

JDK 8 učinio je XOR operaciju gornjih 16 bitova i donjih 16 bitova heš vrednosti, da i informacije gornjih bitova mogu učestvovati u izračunu donjih bitova, time može u velikoj meri smanjiti heš kolizije.

Ergeov napredni put za Java: hash metoda JDK 8

Vodič za Java intervju (plaćeno) sadrži originalno pitanje drugog intervjua 2, Meituan poželjna logistika raspoređivanje: Interna struktura HashMap, razlika 1.7 i 1.8, kakva unapređenja

23.Možeš sam dizajnirati i implementirati HashMap?

Ovo pitanjeKuaishoučesto pitaju. Verziju crveno-crnog stabla većina ne može napisati, ali verziju niz+spregnuta lista nije problem, detaljno možeš videti: Ručno pisati HashMap, intervjuter Kuaishou direktno pozdravlja stručnjaka!.

Može, prvo kažem opšti dizajn:

Prvi korak, realizovati hash funkciju, remeti hashCode ključa
Drugi korak, realizovati metodu spregnute liste za rešavanje heš kolizije
Treći korak, nakon proširivanja, ponovo izračunati heš vrednost, elemente staviti u novi niz

Sanfen E pobeda na intervjuu: Celokupna struktura prilagođenog HashMap

Kompletan kod:

24.🌟Da li je HashMap siguran za niti?

Preporučeno čitanje: Detaljno HashMap

HashMap nije siguran za niti, uglavnom postoji nekoliko problema:

①, Proširivanje u više nit će pasti u beskonačnu petlju. HashMap u JDK 7 koristi metodu umetanja na početku za obradu spregnute liste, u okruženju više niti pri proširivanju će se desiti kružna spregnuta lista, dovodi do beskonačne petlje.

Ergeov napredni put za Java: Kružna spregnuta lista

Međutim, u JDK 8 je promenjeno umetanje na kraju, popravljen je ovaj problem, pri proširivanju održava originalni redosled liste.

②, Pri konkurentnom put-u elemenata u više nit, može dovesti do gubitka elemenata. Zato što izračunata pozicija može biti preklopljena drugom nitom, na primer jedna nit stavlja 3, druga nit stavlja 7, onda će 3 biti izgubljena.

③, Pri konkurentnom put i get, get može dobiti null. Nit 1 izvršava put, zato što je broj elemenata premašio prag i proširuje se, nit 2 u ovom trenutku izvršava get, može se desiti ovaj problem.

Ergeov napredni put za Java: get do null

Zato što nakon što nit 1 završi table = newTab, table nita 2 je već promenjeno, na primer par ključ-vrednost indeksa 3 se pomera na poziciju indeksa 7, tada nit 2 ide da get element indeksa 3 i ne može dobiti.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje Huawei OD: Da li je HashMap siguran za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje drugog tehničkog intervjua 8, Huawei: Da li je HashMap siguran za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 9, ByteDance Feishu backend: Zašto HashMap nije siguran, kako poboljšati, i ConcurrentHashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 16, Tencent Cloud Zhi: Podna implementacija HashMap, zašto nije siguran za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua stažiste 4, JD cloud: hashmap će zaključati, da li znaš
Vodič za Java intervju (plaćeno) sadrži originalno pitanje tehničkog intervjua Java 12, BYD: sinhronizacija i nesinhronizacija map
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 1, OPPO: Zašto HashMap nije siguran za niti?

25.🌟Kako rešiti problem sigurnosti HashMap za niti?

U ranijoj verziji JDK, možeš koristiti Hashtable da bi osigurao sigurnost niti. Hashtable na metodama dodaje synchronized ključnu reč.

Osim toga, možeš kroz Collections.synchronizedMap metodu vratiti Map siguran za niti, interno kroz synchronized objektnu bravu osigurava sigurnost niti, lakše je od direktnog dodavanja synchronized ključne reči na metodu.

Ergeov napredni put za Java: Collections.synchronizedMap

Elegantnije rešenje je korišćenje ConcurrentHashMap iz konkurentnog paketa alata, koristiCAS+ synchronized ključnu rečda osigura sigurnost niti.

Chu Nian Chu Lian: Implementacija u ConcurrentHashMap 8

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua K, letnja regrutacija Xiaomi: Koje su map sigurne za niti, kako ConcurrentHashMap osigurava sigurnost niti, zašto je efikasniji od hashTable
Vodič za Java intervju (plaćeno) sadrži originalno pitanje drugog tehničkog intervjua 8, Huawei: Koje su kolekcije sigurne za niti u Javi?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog tehničkog intervjua 9, ByteDance Feishu backend: Zašto HashMap nije siguran, kako poboljšati, i ConcurrentHashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 16, Tencent Cloud Zhi: Koje su tipovi kolekcija sigurnih za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 6, China Merchants Bank Zhaoyin Network Technology: Metodi da se nesigurne kolekcije učine sigurnim za niti?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 8, JD: Koja je razlika između hashMap i hashTable
Vodič za Java intervju (plaćeno) sadrži originalno pitanje intervjua 1, OPPO: Razlika od ConcurrentHashMap
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 27, Tencent cloud backend: Znaš li Hashtable? Da li HashMap može garantovati konkurentnu sigurnost? Kako ConcurrentHashMap garantuje?
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 19, ByteDance Tomato Fiction: Hashtable i HashMap

26.Da li su interni čvorovi HashMap uređeni?

Neuređeni, random umetanje na osnovu heš vrednosti.

27.Kako LinkedHashMap realizuje uređenost?

LinkedHashMap na osnovu HashMap-a održava dvostruku spregnutu listu, kroz before i after identifikuje prethodni i sledeći čvor.

Sanfen E pobeda na intervjuu: Entry čvor

Time realizuje redosled umetanja ili redosled pristupa.

Sanfen E pobeda na intervjuu: LinkedHashMap princip implementacije

28.Kako TreeMap realizuje uređenost?

TreeMap kroz komparator ključeva odlučuje redosled elemenata, ako nije naveden komparator, onda ključ mora implementirati Comparable interfejs.

Ergeov napredni put za Java: TreeMap izvorni kod

Podna struktura TreeMap je crveno-crno stablo, crveno-crno stablo je samo-balansirajuće binarno stablo pretrage, svaki čvor je veći od bilo kog čvora u levom podstablu, manji od bilo kog čvora u desnom podstablu.

Pri umetanju ili brisanju elemenata kroz rotaciju i bojenje održava balans stabla.

Pri pretrazi počinje od korenskog čvora, koristi karakteristike binarnog stabla pretrage, postepeno rekurzivno pretražuje levo ili desno podstablo, dok ne pronađe ciljni element.

29.Razlika između TreeMap i HashMap

①, HashMap je zasnovan na nizu+spregnutu listu+crveno-crno stablo, pri put-u elementa prvo računa heš vrednost ključa, zatim kroz heš vrednost izračunava indeks smeštaja elementa u nizu, zatim element stavlja na navedenu poziciju, ako se desi heš kolizija, koristi spregnutu listu za rešavanje, ako dužina liste je veća od 8, pretvara se u crveno-crno stablo.

②, TreeMap je zasnovan na crveno-crnom stablu, pri put-u elementa prvo proverava da li je koreni čvor prazan, ako je prazan, direktno ubacuje u koreni čvor, ako nije, kroz komparator ključa da sudi da li element treba ubaciti u levo ili desno podstablo.

U slučaju bez heš kolizije, efikasnost pretrage HashMap je O(1). Pogodno je za scenarije gde su česte operacije pretrage.

Efikasnost pretrage TreeMap je O(logn). I garantuje uređenost elemenata, stoga je pogodno za scenarije gde treba mnogo raspona pretrage ili uređenog obilaska.

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 16, letnji stažista Meituan: Koje kolekcije znaš, reci razliku između HashMap i TreeMap, razliku u scenarijima primene
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua 2, Kuaishou: Razlika HashMap i TreeMap

Set

30.Koja je podna implementacija HashSet?

HashSet je realizovan kroz HashMap, samo vrednost je popunjena fiksanim Object objektom, a ključ se koristi za operacije.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    // ……
}

U stvarnom razvoju, HashSet se ne koristi često, na primer, ako trebamo čuvati grupu elemenata uređeno, ArrayList i LinkedList su pogodniji; ako trebamo čuvati parove ključ-vrednost i pretraživati prema ključu, HashMap je možda pogodniji.

HashSet se uglavnom koristi za deduplikaciju, na primer, ako trebamo da prebrojimo koliko različitih reči postoji u jednom članku, možemo koristiti HashSet za realizaciju.

// Kreiraj HashSet objekat
HashSet<String> set = new HashSet<>();

// Dodaj elemente
set.add("Chenmo");
set.add("Wang Er");
set.add("Chen Qingyang");
set.add("Chenmo");

// Ispiši broj elemenata HashSet
System.out.println("HashSet size: " + set.size()); // output: 3

// Obiđi HashSet
for (String s : set) {
    System.out.println(s);
}

HashSet automatski deduplikuje, zato što je realizovan kroz HashMap, ključevi HashMap su jedinstveni, isti ključ će preklopiti originalni ključ, pa drugi put isti ključ elementa direktno preklapa prvi ključ.

Sanfen E pobeda na intervjuu: HashSet ugnježdenje

Koja je razlika između HashSet i ArrayList

ArrayList je zasnovan na dinamičkom nizu, HashSet je zasnovan na HashMap.
ArrayList dozvoljava dupličirane elemente i null vrednosti, može imati više istih elemenata; HashSet garantuje jedinstvenost svakog elementa, ne dozvoljava dupličirane elemente, zasnovan na hashCode i equals metodima elementa da odredi jedinstvenost elementa.
ArrayList održava redosled umetanja elemenata, može pristupati elementima preko indeksa; HashSet ne garantuje redosled elemenata, redosled čuvanja elemenata zavisi od heš algoritma, i može se promeniti pri dodavanju ili brisanju elemenata.

Kako HashSet proverava duplikate elemenata, da li put-uje kada su dupličirani?

add metoda HashSet se realizuje kroz poziv put metode HashMap:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Zato logika HashSet-a za proveru duplikata elemenata podno još uvek logika HashMap:

HashMap pri umetanju elementa obično treba tri koraka:

Prvi korak, kroz hash metodu izračunava heš vrednost ključa.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Drugi korak, niz vrši prvo proširivanje.

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

Treći korak, prema heš vrednosti izračunava indeks ključa u nizu, ako na odgovarajućem indeksu nema podatke, direktno ubacuje.

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Ako na odgovarajućem indeksu već postoje podaci, treba proceniti da li je isti ključ, ako jest preklopi vrednost, inače treba proceniti da li je čvor stabla, ako jest ubaci čvor u stablo, inače ubaci podatke u listu.

else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
}

To jest, HashSet kroz heš vrednost elemenata procenjuje da li su elementi duplićirani, ako su duplićirani, preklopiće originalnu vrednost.

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua stažista 10, JD backend: Razlika HashSet i ArrayList
Vodič za Java intervju (plaćeno) sadrži originalno pitanje prvog intervjua stažista 10, JD backend: Kako HashSet procenjuje duplikate elemenata, da li put-uje kada su duplićirani

Kažem nekoliko reči iz srca.

Zapravo na internetu postoji mnogo standardnih pitanja, time može svima dati više izbora.

„Pobeda na intervjuu“ drugo izdanje na osnovu početne verzije gostiju planete Sanfen E, dodao sam moja razmišljanja, integrisao rezultate više od 1000 stvarnih iskustava sa intervjua, i od 24. do 25. generacije, pomoglo mnogim prijateljima. Buduće 26., 27. generacije će takođe imati koristi, time će dobiti željenu ponudu.

Pomoći svima, drago mi je, i u procesu rekonstrukcije „pobede na intervjuu“ sam mnogo narastao, mnoge slabije osnove su ojačane.

Mislim da su svi prilično objektivni komentari

Priznanje dvostrukog nepostojućeg master studenta na Erge standardna pitanja

Često mislim da sam zen tip osobe, ne volim da se nadmećem s drugima, ne volim da namerno promovišem svoja dela.

Volim da čekam cvetanje.

Ako misliš da je „pobeda na intervjuu“ dobra, možeš reći mlađim kolegama i sestrama da postoji ovaj besplatni materijal za učenje.

Još ću nastaviti da optimizujem, ne znam kad će doći treće izdanje, ali ću se truditi.

Neka svi imaju svetlu budućnost.

Ovaj put i dalje tri verzije, svetla, tamna i epub verzija. Prikažimo jednu epub verziju, nekim prijateljima je hitno ova verzija, takođe ispunjava želju.

Pobeda na intervjuu — kolekcijski okvir: epub verzija

Nego mog utrošeno vreme i energiju, ako vam pomogne molim vas dajte reč, da i tvoji kolege, drugovi mogu da koriste.

Detaljno objašnjeno 29 pitanja o Java kolekcijskom okviru na intervjuu, ovaj put će saboriti intervjutera, mislim da je sigurno (ručni pas). Sastavio: Chenmo Wang Er, pogledajlink za prenos, autor: Sanfen E, pogledajlink za original.

Ništa me ne zaustavlja——osim cilja, čak i ako na obali ima ruže, hladovine, mirna luka, ja sam brod bez veza.

Serijski sadržaj: