[NOISE].
Než se ponoříme do hash tabulky, pojďme
první recenzi klady a zápory některých
jednodušší datové struktury, počínaje
pole.
Připomeňme si, že pole nám umožňují uchovávat
prvky jednoho typu dat
souvisle v paměti.
Vzhledem k tomu, každý prvek je spojen s
index, nebo místo,
máme náhodný přístup ke všem
prvků v poli.
Jinými slovy, můžeme přistupovat jakýkoli prvek
v jednom kroku do indexování
pole.
To je velký problém, protože algoritmy
jako binární vyhledávání závisí na náhodné
přístup.
Nevýhodou polí je, že jejich velikost
je pevná.
Vzhledem k tomu, pole ukládat data souvislý v
paměť, je nutné zadat velikost pole
při deklarovat pole.
Ty jsou skutečně žádá provozní
systém vyhradit příslušnou částku
paměti pro elementy pole.
Neexistuje žádná záruka, že více paměti,
v těsné blízkosti svého pole, bude k dispozici
pro pozdější použití.
Takže pole nelze snadno pěstovat.
Připomeňme si, že jsme se také dozvěděli o propojeny
seznamy, které mohou růst, protože jejich
prvky nejsou souvislé v paměti.
Každý uzel v propojeném seznamu obsahuje
prvek, který chceme uložit, jakož i
ukazatel na následující prvek v
seznam.
Bohužel, cena, kterou jsme zaplatili za
dynamické velikost je náhodný přístup k
prvky.
Aby bylo možné získat přístup k určité prvek,
je nutné přejít na celý
Seznam dokud požadovaný prvek je
dosáhl.
Takže, když jsem hledal číslo 9, já bych
sledovat ukazatele z uzlu do uzlu,
ověření, zda hodnota každého uzlu
se rovná 9.
Jako takový, v nejhorším případě, vyhledá je
O (n), který je daleko od efektivní.
Můžeme to udělat lépe než O (n), zatímco ještě
což naše datová struktura roste přes
čas?
Hash tabulky nabídnout řešení.
Hash tabulky jsou používány při rychlé
vkládání, mazání a vyhledávání z
prvky je prioritou.
Teoreticky, vkládání, mazání a vyhledávání
mohou být dokonce provedeno v konstantní
čas.
Takže, co je hash tabulka vlastně je?
Hash tabulka je jen pole spolu
s funkcí, kterou budeme volat hash
funkce.
Funkce hash se část dat
jako vstup, zavoláme tento klíč, a
výstupy celé číslo, běžně označované
jako hodnota hash.
Hodnota hash mapuje naši klíč
Zejména index v tabulce hash.
Byste nejprve použít funkce hash
určit, kde v tabulce hash, aby
uložit daný klíč.
Později, měli byste použít stejnou funkci hash
zjistit, kde se v tabulce hash, aby
hledat pro daný klíč.
Z tohoto důvodu je důležité, aby hash
Funkce se chová konzistentně a výstupy
stejný hash hodnotu za stejných kláves.
Uvědomte si, že hashovací tabulky mohou být použity k
ukládání dat všech typů.
Ale pro zjednodušení věci, budeme soustředit na
struny pro teď.
Zde je jednoduchý hash funkce pro řetězce.
Tato funkce hash vypočte hash
funkce na základě prvního písmene
klíč.
"Apple" začíná písmenem "A", tak je to
mapovány na indexu 0 v tabulce hash.
Podobně, "banana" je namapován na index 1,
a "kočka" je mapována na index 2.
Je-li přítel zeptá, zda slovo "pes" je v
tabulka, budeme vstupní "pes" do hash
funkce, která vypíše hodnoty hash
ze dne 3..
Vzhledem k tomu, "pes" není uložen na indexu 3, jsme
lze s jistotou říci, že "pes" není
v tabulce,
i když jsme jen zkontrolovat jeden z
hash tabulky je 26 indexy.
Čas hodit klíče do věcí.
Co když chceme uložit "mravence" do
Tabulka stejně?
"Ant" hash index 0, stejně jako "jablko" udělal.
Toto je příklad kolize,
Výsledkem dvou tlačítek zatřiďování do stejné
index.
I když vaše hash tabulka je větší než
nastavit vaše data, a vy jste si vybrali dobrý
hash funkce,
budete ještě potřebovat plán pro nakládání s
kolize, zda a kdy se objeví.
Pojďme diskutovat o výhodách a nevýhodách obou
společné metody pro řešení kolizí:
lineární snímání a oddělené zřetězení.
S lineární snímání, jestliže klíč hash na
stejný index jako dříve uložené
klíč je přiřazen další dostupné
slot v tabulce.
Takže, "mravenec" je nyní uložena na indexu 3, protože
indexy 0, 1 a 2 jsou již v provozu.
A pokud se pokusíte uložit třetí slovo, které
začíná na písmeno "A", je to zadáno
index 4, protože indexy 0, 1, 2, a 3
jsou plné.
Jak můžete vidět i z tohoto jednoduchého
Například jednou kolize nastane, vás
výrazně zvýší pravděpodobnost, že
další kolizi dojde ve stejném
oblast.
To se nazývá shlukování, a to
Závažným nedostatkem na lineární snímání.
Navíc, nejhorší případ vložení, mazání,
a doba vyhledávání se převádí na O (n),
jako další k dispozici slot může mít
případně jako poslední slot v tabulce.
Možná samostatné řetězení nabídne více
přesvědčivé řešení.
V samostatném modelu řetězení, hash
tabulka je vlastně pole ukazatelů na
spojové seznamy.
Pokud dojde ke kolizi, klíč může být
vložena v konstantním čase v čele
vhodné spojový seznam.
Co se stane teď, když jsme se hledat pro "jablko"
v tabulce hash?
V nejhorším případě musíme projít
Celý spojový seznam, počínaje indexem 0..
Vyhledávací čas nejhorší případ pro hash
tabulka, která používá oddělené zřetězení je
tedy O (n / k), kde k je
velikost tabulky hash.
Počkejte, k je konstanta.
Takže O (n / k) je opravdu jen O (n),
které bylo vyhledávání doba nejhorší případ pro
spojový seznam.
Už opravdu jsme prošli všechny
potíže učení o hash tabulky
jen aby skončil tam, kde jsme začali?
To může být případ od teoretické
perspektiva, ale v reálném světě,
O (n / k) může být obrovské zlepšení oproti
O (n).
Přemýšlejte o tom tímto způsobem: Předpokládejme, že k je
10 - byste raději čekat 100 sekund
nebo 100 / k?
10 sekund od aplikace Microsoft Word dokončit
kontrola pravopisu dokumentu.
Jak jste právě viděli, řešení kolizí
znamená jeden druh lineární hledání nebo
další, což zpomaluje věci dolů
výrazně.
Proto, budete chtít vybrat hash
funkce, která minimalizuje možnost
kolize vyskytující se v první řadě.
Zde jsou některé vlastnosti dobrého hash
funkce je třeba mít na paměti.
Dobrý hashovací funkce by měly využívat
všechny informace poskytnuté daný klíč
, aby se maximalizoval počet
Možné hodnoty hash.
Například, když jsme měli dva řetězce, "kočka"
a "housenka", tak chceme, aby hash
na různých místech na stole.
Je-li funkce hash vzal v úvahu pouze
První jeden, dva, nebo dokonce tři písmena
z řetězců, kolize by mohlo dojít,
neboť obě slova začínají na stejné
tři písmena.
Hash hodnoty by měly být rovnoměrně
přes hash tabulky.
Tím se sníží délku spojené
seznamy by měly srážkám dochází.
Je to také dobré znamení, pokud vaše hash hodnota
je schopen generovat velmi odlišné
hash hodnoty pro podobné klíče,
takže kolize mnohem méně pravděpodobné.
Naším cílem je rychlé vložení, mazání,
a vyhledávání.
Hašovací funkce hraje klíčovou roli v
Každý z těchto procesů a bude
volal velmi často.
Proto se ujistěte, že používá jen velmi
Jednoduchá a rychlá operace, aby se minimalizovalo běh
čas.
Doufám, že jste si užili tento krátký
úvod do hash tabulky.
Mé jméno je Lauren, a to je CS50.