Ar „Java“ maišymo kortelė tikrai O (1)?

Mačiau keletą įdomių teiginių apie SOh-SOH maišos žemėlapius ir jų paieškos laiką O(1) . Ar kas nors gali paaiškinti, kodėl taip yra? Jei šios maišos kortelės nėra labai skiriasi nuo bet kokių maišymo algoritmų, kuriuos nusipirkau, visada turėtų būti duomenų rinkinys, kuriame yra konfliktų.

Tokiu atveju paieška bus O(n) , o ne O(1) .

Ar kas nors gali paaiškinti, ar jie yra O (1), ir jei taip, kaip tai pasiekti?

125
28 июня '09 в 19:49 2009-06-28 19:49 paxdiablo nustatytas birželio 28 d., 09:49, 2009-06-28 19:49
@ 15 atsakymų

„HashMap“ bruožas yra tas, kad, priešingai nei sako, subalansuoti medžiai, jo elgesys yra tikimybinis. Tokiais atvejais dažniausiai naudinga kalbėti apie sudėtingumą dėl blogiausio įvykio tikimybės. Dėl maišos kortelės tai, be abejo, yra susidūrimo atvejis, kaip paveikti vaizdą. Susidūrimas yra gana lengva įvertinti.

p susidūrimas = n / talpa

Taigi, maišymo kortelė su netgi nedideliu skaičiumi elementų gali patirti bent vieną susidūrimą. Pavadinimas „Big O“ leidžia mums padaryti kažką labiau įtikinamo. Atkreipkite dėmesį, kad bet kokiai pasirinktinai fiksuotai konstantai k.

O (n) = O (k * n)

Šią funkciją galime panaudoti maišos kortelės veikimui pagerinti. Vietoj to galėtume galvoti apie ne daugiau kaip dviejų susidūrimų tikimybę.

p susidūrimas x 2 = (n / talpa) 2

Tai daug mažesnė. Kadangi vieno papildomo susidūrimo apdorojimo kaina neturi reikšmės „Big O“ veikimui, radome būdą, kaip pagerinti našumą, faktiškai nekeičiant algoritmo! Galime ją apibendrinti

p susidūrimas xk = (n / talpa) k

Ir dabar mes galime ignoruoti tam tikrą savavališką susidūrimų skaičių ir galų gale su nykstančia maža tikimybe, kad susidursime daugiau, nei atsižvelgsime. Tikimybę į savavališką mažą lygį galite gauti pasirinkdami tinkamą k, viskas, nekeičiant faktinio algoritmo įgyvendinimo.

Apie tai kalbame sakydami, kad maišos kortelė turi didelę tikimybę gauti O (1) prieigą

100
28 июня '09 в 20:33 2009-06-28 20:33 atsakymas suteiktas „ SingleNegationElimination“ birželio 28 d., 09:33 , 20:33 2009-06-28 20:33

Atrodo, kad sumaišysite blogiausią elgesį su vidutiniu (numatomu) įvykdymo laiku. Pirmasis iš tikrųjų yra O (n) maišos lentelėms apskritai (t.y. nenaudoja tobulo maišymo), tačiau tai retai aktualu praktikoje.

Bet kokiam patikimam maišos lentelės įgyvendinimui kartu su pusiau užsakytu maišytuvu yra O (1) paieškos našumas, turintis labai mažą koeficientą (iš tikrųjų, 2) tikėtinu atveju per labai mažą sklaidą.

33
28 июня '09 в 20:09 2009-06-28 20:09 atsakymą pateikė Konradas Rudolphas birželio 28 d., 09:09 2009-06-28 20:09

„Java“ sistemoje „HashMap“ naudoja hashCode, kad surastų kibirą. Kiekvienas kibiras yra šio kibiro elementų sąrašas. Elementai yra nuskaityti naudojant bendraamžius palyginimui. Pridėjus elementų, „HashMap“ pasikeičia, kai pasiekiama tam tikra procentinė apkrova.

Taigi kartais tai turi būti lyginama su keliais elementais, tačiau apskritai jis yra daug arčiau O (1) nei O (n). Praktiniais tikslais tai yra viskas, ką reikia žinoti.

26
28 июня '09 в 19:54 2009-06-28 19:54 atsakymą duoda FogleBird birželio 28 d. , 09:54 , 2009-06-28 19:54

Atminkite, kad o (1) nereiškia, jog kiekviena paieška tikrina tik vieną elementą - tai reiškia, kad vidutinis patikrintų elementų skaičius išlieka pastovus, lyginant su konteinerio elementų skaičiumi. Todėl, jei norint surasti elementą, kuriame yra 100 elementų, reikia ieškoti vidutiniškai 4 palyginimai, taip pat reikia vidutiniškai 4 palyginimus, kad rastų elementą konteineryje su 10 000 elementų bet kuriam kitam elementų skaičiui (visada yra šiek tiek dispersijos, ypač aplink taškus, kurioje yra išrinktas maišos lentelė ir kai yra labai nedidelis elementų skaičius).

Taigi susidūrimas netrukdo konteineriui atlikti operacijų o (1), jei vidutinis raktų skaičius per kibirą lieka fiksuotoje atskaitoje.

22
28 июня '09 в 20:04 2009-06-28 20:04 Atsakymą pateikė Danielis Jamesas birželio 28 d., 09:04 2009-06-28 20:04

Žinau, kad tai yra senas klausimas, bet iš tikrųjų yra naujas atsakymas.

Jūs teisus, kad maišos žemėlapis tikrai nėra O(1) , nes, kadangi elementų skaičius tampa savavališkai didelis, negalėsite ieškoti pastovaus laiko (ir O-žymėjimas yra apibrėžtas skaičiais, gali būti savavališkai didelis).

Tačiau tai nereiškia, kad realaus laiko sudėtingumas yra O(n) - nes nėra jokios taisyklės, kurioje teigiama, kad kibirai turėtų būti įgyvendinami kaip linijinis sąrašas.

Tiesą sakant, „Java 8“ kaušus įgyvendina kaip „ TreeMaps kai jie viršija ribinę vertę, o tai leidžia faktinį laiką O(log n) .

8
28 марта '15 в 9:25 2015-03-28 09:25 atsakymą pateikia „ ajb“ kovo 28 d., 15 val. 9:25 2015-03-28 09:25

Jei kibirų skaičius (skambutis b) išlieka pastovus (įprastu atveju), tada paieška iš tikrųjų yra O (n).
Kadangi skaičius n tampa didelis, kiekvieno kibiro elementų skaičius yra vidutiniškai n / b. Jei susidūrimo rezoliucija atliekama vienu iš įprastų būdų (pvz., Susietas sąrašas), tada paieška yra O (n / b) = O (n).

Pavadinimas O yra tai, kas atsitinka, kai n tampa didesnis ir didesnis. Jis gali būti klaidinantis, kai jis taikomas tam tikriems algoritmams, o maišos lentelės yra pavyzdys. Mes pasirenkame kibirų skaičių pagal elementų, su kuriais mes tikimės, skaičių. Kai n yra maždaug tokio paties dydžio, kaip b, paieška atliekama maždaug pastoviu laiku, bet mes negalime jį pavadinti O (1), nes O yra apibrėžiamas kaip riba n → ∞.

4
28 июня '09 в 21:05 2009-06-28 21:05 Atsakymą pateikė IJ Kennedy , birželio 28 d., 09:21, 2009-06-28 21:05

O(1+n/k) kur k yra kibirų skaičius.

Jei įgyvendinimas nustato k = n/alpha , tai yra O(1+alpha) = O(1) , nes alpha yra konstanta.

4
20 авг. atsakymą pateikė Satyanarayana Kakollu 20 rug . 2013-08-20 02:43 '13 at 2:43 2013-08-20 02:43

Mes nustatėme, kad standartinis „hash“ lentelės aprašymas, kuris yra O (1), reiškia tikėtiną vidutinį numatomą laiką, o ne griežčiausio blogiausio atvejo rezultatą. Taupymo lentelėje, kuri išsprendžia susidūrimus su grandine (pvz., „Java“ maišos byla), tai techniškai O (1 + α), turinti gerą maišos funkciją , kur α yra lentelės apkrovos koeficientas. Vis dar pastovus, kol saugomų objektų skaičius yra ne didesnis kaip pastovus koeficientas, viršijantis lentelės dydį.

Taip pat buvo paaiškinta, kad, griežtai kalbant, galima sukurti įvestį, kuriai reikia O (n) paieškos bet kuriai deterministinei hash funkcijai. Tačiau taip pat įdomu apsvarstyti blogiausią numatomą laiką, kuris skiriasi nuo vidutinio paieškos laiko. Naudojant grandinę, tai yra O (1 + ilgiausios grandinės ilgis), pavyzdžiui, (log n / log log n), kai α = 1.

Jei domitės teoriniais būdais, kaip pasiekti tikėtiną blogiausio laiko paiešką, galite skaityti apie dinamišką tobulą maišymą , kuris rekursiškai išsprendžia konfliktus su kitu maišos stalu!

2
28 июня '09 в 20:42 2009-06-28 20:42 atsakymą pateikė jtb birželio 28 d. , 09:42 2009-06-28 20:42

Tai yra O (1) tik tada, kai jūsų maišymo funkcija yra labai gera. „Java“ maišos lentelės įgyvendinimas neapsaugo nuo blogų maišos funkcijų.

Jei reikia pridėti lentelę, kai pridėsite elementų arba ne, tai netaikoma klausimui, nes kalbame apie paieškos laiką.

2
28 июня '09 в 21:23 2009-06-28 21:23 atsakymą įteikė Antti Huima birželio 28 d., 09:21, 2009-06-28 21:23

„HashMap“ viduje esantys elementai yra saugomi kaip susieto sąrašo (mazgo) masyvas, kiekvienas susietas sąrašas masyve yra vieno ar kelių raktų unikalios maišos vertės kibiras.
Pridėjus įrašą į „HashMap“, raktų maišymo kodas naudojamas norint surasti talpyklą masyve, pavyzdžiui:

 location = (arraylength - 1)  keyhashcode 

Čia yra bitų ir operatorius.

Pavyzdžiui: 100 "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Operacijos metu jis naudoja tą patį metodą, kaip nustatyti rakto vietą raktui. Geriausiu atveju kiekvienas maišos kodas yra unikalus ir kiekvienam raktui suteikia unikalų kibirą, tokiu atveju gavimo metodas praleidžia laiką tik norėdamas nustatyti kibirą ir gauti pastovią O (1) reikšmę.

Blogiausiu atveju visi raktai turi tokį patį maišos kodą ir yra saugomi toje pačioje kibiroje, o tai veda prie viso sąrašo, kuris veda į O (n).

„Java“ 8 atveju susieto sąrašo kibiras pakeičiamas „TreeMap“, jei dydis padidėja iki daugiau nei 8, tai sumažina blogiausio atvejo paieškos efektyvumą į „O“ (log n).

1
01 дек. Atsakymas duotas Ramprabhu gruodžio 1 d. 2016-12-01 19:29 '16 at 7:29 pm 2016-12-01 19:29

Akademikai, praktikoje, HashMaps turėtų būti laikomi nedideliu poveikiu veiklos rezultatams (nebent jūsų profiliatorius pasakytų kitaip).

1
29 июня '09 в 2:26 2009-06-29 02:26 atsakymą pateikė Ryanas Emerlis, birželio 29 d., 09:26 , 2009-06-29 02:26

Tai priklauso nuo algoritmo, kurį pasirinkote, kad išvengtumėte susidūrimų. Jei jūsų diegimas naudoja atskirą grandinę, tuomet blogiausias atvejis atsitinka, kai kiekvienas duomenų elementas yra išskirtas į vieną vertę (pvz., Prastas maišos funkcijos pasirinkimas). Tokiu atveju duomenų paieška nesiskiria nuo linijinės paieškos susietame sąraše, ty O (n). Tačiau tikimybė, kad tai atsitiks, yra nereikšminga, o paieška yra geresnė, o vidutinis atvejis išlieka pastovus, t.y. O (1).

1
28 июня '09 в 20:15 2009-06-28 20:15 atsakymą pateikė „ Nizar Grira “ birželio 28 d., 09:15 , 2009-06-28 20:15

Tai dažniausiai taikoma daugumai hash lentelių daugelyje programavimo kalbų, nes pats algoritmas nesikeičia.

Jei lentelėje nėra susidūrimų, reikia atlikti tik vieną peržiūrą, todėl veikimo laikas yra O (1). Jei yra susidūrimų, turite atlikti kelias paieškos operacijas, kurios sumažina našumą, palyginti su O (n).

1
28 июня '09 в 20:03 2009-06-28 20:03 atsakymas pateikiamas Tobias Svensson birželio 28 d. 09:03 2009-06-28 20:03

Tik teoriniu atveju, kai maišos kodai visuomet skiriasi, ir kiekvienos maišos kodo kibiras taip pat skiriasi, O (1) egzistuos. Priešingu atveju jis turi pastovią tvarką, t. Padidinant hashmap, jo paieškos tvarka išlieka pastovi.

1
19 окт. atsakymas pateikiamas sn.anurag 19 okt. 2015-10-19 14:36 '15, 14:36 ​​pm 2015-10-19 14:36

Žinoma, maišos kortelės veikimas priklausys nuo šio objekto funkcijos hashCode () kokybės. Tačiau, jei funkcija yra įgyvendinama taip, kad susidūrimo tikimybė yra labai maža, ji turės labai gerų rezultatų (tai nėra griežtai O (1) visais galimais atvejais, bet daugeliu atvejų).

Pavyzdžiui, numatytasis diegimas „Oracle JRE“ yra naudoti atsitiktinį skaičių (kuris yra saugomas objekto pavyzdyje, kad jis nepasikeistų, bet taip pat išjungia nuokrypio užraktą, tačiau tai dar viena diskusija), todėl susidūrimų tikimybė yra labai maža.

-1
28 июня '09 в 19:55 2009-06-28 19:55 atsakymą pateikė Gray Panther birželio 28 d., 09:55, 2009-06-28 19:55