[NOISE].
Kabla ya kupiga mbizi katika meza hash, hebu
kwanza kupitia faida na hasara za baadhi
miundo rahisi data, kwa kuanzia na
arrays.
Kumbuka kwamba arrays kuruhusu sisi kuhifadhi
mambo ya aina moja data
contiguously katika kumbukumbu.
Kwa sababu kila kipengele ni kuhusishwa na
index, au eneo,
sisi kupata random kwa yote ya
vipengele katika safu.
Kwa maneno mengine, tunaweza kupata hiki yoyote
katika hatua moja kwa Indexing katika
safu.
Hii ni mpango mkubwa, kwa sababu algorithms
kama search binary hutegemea random
upatikanaji.
upande wa chini ya arrays ni kwamba kawaida yao
ni fasta.
Kwa sababu data arrays duka contiguously katika
kumbukumbu, lazima kutaja safu ukubwa
wakati kutangaza safu.
Wewe ni ufanisi kuuliza uendeshaji
mfumo wa hifadhi ya kiasi sahihi
ya kumbukumbu kwa ajili ya mambo safu ya.
Hakuna uhakika kwamba zaidi ya kumbukumbu,
karibu na safu yako, itakuwa inapatikana
kwa matumizi ya baadaye.
Hivyo arrays hawezi kukua kwa urahisi.
Kumbuka kwamba sisi pia kujifunza kuhusu uhusiano
orodha, ambayo inaweza kukua kwa sababu wao
mambo ni si contiguous katika kumbukumbu.
Kila node katika orodha wanaohusishwa ina
hiki kwamba tunataka kuhifadhi, kama vile
pointer kwa hiki mara kwa mara katika
orodha.
Kwa bahati mbaya, bei tumekuwa kulipwa kwa
nguvu ukubwa ni kupata random kwa
vipengele.
Ili kupata hiki fulani,
ni muhimu kwa tindanga nzima
orodha mpaka hiki taka ni
kufikiwa.
Hivyo, kama mimi nina kuangalia kwa namba 9, ningependa
kufuata kuyatumia na nodi kwa node,
kuangalia kama thamani ya kila node
ni sawa na 9.
Kama vile, katika kesi mbaya, kuangalia juu ni
O (n), ambayo ni mbali na ufanisi.
Je, sisi kufanya vizuri zaidi kuliko O (n) wakati bado
kuruhusu mfumo wetu wa data kukua juu ya
wakati?
Meza Hash kutoa ufumbuzi.
Meza Hash hutumika wakati wa haraka
insertion, kufutwa, na chaguo-msingi ya
mambo ni kipaumbele.
Katika nadharia, insertion, kufutwa, na chaguo-msingi
wanaweza hata kukamilika katika mara kwa mara
wakati.
Hivyo, ni nini meza hash anyway?
meza hash ni tu safu pamoja
na kazi, ambayo tutaweza wito hash
kazi.
kazi hash inachukua kipande cha data
kama pembejeo, tutaweza wito huu muhimu, na
Matokeo integer, inajulikana
kama thamani hash.
thamani hash ramani yetu muhimu kwa
hasa index katika meza hash.
D awali kutumia heshi kwa
kuamua wapi katika meza hash kwa
kuhifadhi muhimu kutolewa.
Baadaye, utaweza kutumia huo heshi
kuamua ambapo katika meza hash kwa
kutafuta ufunguo huo.
Kwa sababu hii, ni muhimu kwamba hash
kazi kutenda mara kwa mara na matokeo
sawa hash thamani kwa funguo kufanana.
Kujua kwamba meza hash inaweza kutumika kwa
kuhifadhi data za kila aina.
Lakini kurahisisha mambo, tutaweza kuzingatia
masharti kwa sasa.
Hapa ni rahisi heshi kwa masharti.
Hii kazi hash computes hash
kazi ya msingi juu ya barua ya kwanza ya
muhimu.
"Apple" inaanza na herufi "A", hivyo ni
mapped kwa index 0 katika meza hash.
Vile vile, "ndizi" ni mapped kwa index 1,
na "paka" ni mapped kwa index 2.
Kama rafiki anauliza kama neno "mbwa" ni katika
meza, tutaweza pembejeo "mbwa" katika hash
kazi, ambayo itakuwa thamani ya pato la hash
ya 3.
Tangu "mbwa" si kuhifadhiwa katika index 3, sisi
wanaweza kusema kwa kujiamini kwamba "mbwa" ni si
katika meza,
ingawa tumekuwa tu kuangaliwa moja ya
hash meza ya 26 fahirisi.
Wakati wa kutupa bisibisi katika mambo.
Nini kama tunataka kuhifadhi "ant" katika
meza kama vile?
"Ant" hashes kwa index 0, kama vile "apple" hakuwa.
Huu ni mfano wa mgongano,
matokeo ya funguo mbili hashing sawa
index.
Hata kama hash meza yako ni kubwa kuliko
data yako kuweka, na umefanya waliochaguliwa nzuri
hash kazi,
wewe bado wanahitaji mpango kwa ajili ya kukabiliana na
migongano, kama na wakati wao kutokea.
Hebu kujadili faida na hasara za mbili
mbinu ya kawaida kwa ajili ya kutatua migongano:
linear uchunguzi na tofauti chaining.
Pamoja na linear uchunguzi, ikiwa hashes muhimu kwa
index hiyo kama awali kuhifadhiwa
muhimu, ni kwa ajili ya inapatikana ijayo
yanayopangwa katika meza.
Hivyo, "ant" sasa ni kuhifadhiwa katika index 3, tangu
fahirisi 0, 1, na 2 walikuwa tayari katika matumizi.
Na kama sisi kujaribu kuhifadhi neno tatu
kuanza na herufi "A", ni kwa ajili
kwa index 4, tangu fahirisi 0, 1, 2, na 3
ni full.
Kama unaweza kuona hata kutoka hii rahisi
mfano, mara moja mgongano hutokea, wewe
kwa kiasi kikubwa kuongeza nafasi ya kuwa
mgongano mwingine kutokea katika huo
eneo hilo.
Hii inaitwa kuunganisha, na ni
drawback kubwa kwa linear uchunguzi.
Aidha, kesi mbaya insertion, kufutwa,
na mara chaguo-msingi na devolved kwa O (n),
kama ijayo inapatikana yanayopangwa inaweza kuwa na
uwezekano wa kuwa yanayopangwa mwisho katika meza.
Labda tofauti chaining kutoa zaidi
kulazimisha ufumbuzi.
Katika tofauti chaining mfano, hash
meza ni kweli safu ya kuyatumia kwa
wanaohusishwa orodha.
Wakati mgongano hutokea, ni muhimu inaweza kuwa
kuingizwa katika wakati mara kwa mara katika kichwa cha
wanaohusishwa sahihi orodha.
Nini kinatokea sasa wakati sisi kutafuta "apple"
katika meza hash?
Katika hali mbaya zaidi, sisi lazima tindanga
nzima wanaohusishwa orodha, kuanzia saa index 0.
kesi mbaya chaguo-msingi wakati kwa hash
meza kwamba anatumia tofauti chaining ni
kwa hiyo O (n / k), ambapo k ni
ukubwa wa meza hash.
Kusubiri pili, k ni mara kwa mara.
Hivyo O (n / k) ni kweli tu O (n),
ambayo ilikuwa mbaya zaidi kesi chaguo-msingi wakati kwa
orodha wanaohusishwa.
Je, sisi kweli wamekwenda kwa njia zote
shida ya kujifunza juu ya meza hash
tu kuishia nyuma ambapo sisi kuanza?
Hiyo inaweza kuwa kesi kutoka kinadharia
mtazamo, lakini katika ulimwengu wa kweli,
O (n / k) inaweza kuwa uboreshaji mkubwa juu ya
O (n).
Fikiria kwa njia hii: kudhani kwamba k ni
10 - bila wewe badala ya kusubiri sekunde 100
au 100 / k?
Sekunde 10 kutoka Microsoft Word kumaliza
Spell kuangalia hati yako.
Kama wewe tu kuona, kutatua migongano
unahusu aina moja ya kutafuta linear au
mwingine, ambayo kupungua mambo chini
mno.
Kwa hiyo, utasikia wanataka kuchagua hash
kazi ambayo itapunguza nafasi ya
migongano kutokea katika nafasi ya kwanza.
Hapa ni baadhi ya mali ya hash nzuri
kazi ya kukumbuka.
nzuri heshi lazima kufanya matumizi ya
habari zote zilizotolewa na muhimu kutokana na
ili kuongeza idadi ya
iwezekanavyo hash maadili.
Kwa mfano, kama tulikuwa na masharti mawili, "paka"
na "caterpillar", tunatarajia wao wanataka hash
maeneo mbalimbali juu ya meza.
Kama heshi tu alichukua katika akaunti ya
moja kwanza, mbili, au barua hata tatu
ya masharti, mgongano kutokea,
tangu maneno yote kuanza kwa moja
barua tatu.
Maadili Hash lazima kuenea sawasawa
katika meza ya hash.
Hii kupunguza urefu wa wanaohusishwa
orodha ya lazima migongano kutokea.
Pia ni dalili nzuri kama hash thamani yako
ni uwezo wa kuzalisha tofauti sana
hash maadili kwa funguo sawa,
kufanya migongano uwezekano mdogo.
Lengo letu ni haraka insertion, kufutwa,
na chaguo-msingi.
kazi hash ina jukumu muhimu katika
kila wa taratibu hizi na kuwa na
aitwaye mara nyingi sana.
Kwa hiyo, kuhakikisha ni ajira tu sana
, shughuli rahisi haraka ili kupunguza kukimbia
wakati.
Natumaini wameweza walifurahia muhtasari huu
kuanzishwa kwa hash meza.
Jina langu ni Lauren, na hii ni CS50.