Maišos lentelės su grandinėmis
Maišos lentelė priskiria raktus lizdams, o kolizijas sudarančius raktus saugo grandinėje.
Esminės žinios
Maišos lentelė priskiria raktus lizdams, o kolizijas sudarančius raktus saugo grandinėje. Esant užpildymo koeficientui α=n/m ir tinkamai atsitiktinai parenkant funkciją iš universaliosios maišos funkcijų šeimos, paieškos trukmės matematinė viltis yra O(1+α); tačiau nepalankus kolizijų išsidėstymas gali pareikalauti O(n).
Sąlygos ir taikymo ribos
- Matematinė viltis skaičiuojama maišos funkcijos pasirinkimo atžvilgiu, kai saugomi raktai ir ieškomas raktas fiksuoti nepriklausomai nuo šio atsitiktinio pasirinkimo. Vien universalumas negarantuoja šio įverčio raktams, parinktiems adaptyviai, stebint maišos funkciją.
- Keisdami lentelės dydį išlaikykite α aprėžtą, kad operacijos sąnaudų matematinė viltis būtų pastovi.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
4 paskaita: grandinės, universalioji maiša ir kolizijų tikimybės įverčio analizė fiksuotoms raktų poroms, 3–5 puslapiai.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-hash-chaining
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra