(tady chybí nějaká okecávka)
Hashovací tabulka slouží k vyhledávání záznamů podle jejich klíče. Když funguje správně, dokáže prvek se zadaným klíčem vyhledat v konstantním čase.
Kdybychom se mohli spolehnout, že všechny klíče budou čísla v rozumně malém rozsahu, mohli bychom si vytvořit právě tak velké pole a prvky přímo ukládat na index daný jejich klíčem. Hashovací tabulka vlastně jen řeší situaci, kdy je klíč v příliš velkém rozsahu: vytvoříme si nějakou funkci, která klíč převede na celé číslo, a to vydělíme se zbytkem velikostí pole. Téhle funkci budeme říkat hashovací – ale narozdíl od kryptografického použití na po ní nechceme vlastně nic složitého.
Snadno se může stát, že více prvkům přiřadíme stejný index. Když zvolíme dotyčnou hashovací funkci dobře, nebudou se prvky nijak výrazně hromadit v žádném z indexů, ale přesto musíme s menšími shluky počítat. Stačí do pole nedávat přímo prvky ze vstupu, ale seznamy prvků – nejlépe další pole nebo spojové seznamy, podle situace. Když prvek přidáváme do hashovací tabulky, najdeme seznam s příslušným indexem a prvek přidáme nakonec, když prvek hledáme, musíme příslušný seznam projít od začátku do konce. Protože jsou shluky jsou převážně malé, bude nám to ale trvat při troše štěstí jen konstantní množství času.
Většinou předem neznáme množství dat, která budeme chtít uložit, a proto musíme tabulku dynamicky zvětšovat. Její velikost by měla být zhruba přímo úměrná počtu prvků, které v ní jsou; můžeme si stanovit libovolný poměr. Když je v tabulce prvků moc, vytvoříme novou tabulku dvojnásobné velikosti a všechny prvky do ní přeneseme. Naopak, když je plná méně než ze čtvrtiny zvoleného poměru, můžeme ji zmenšit na polovinu, abychom šetřili paměť. V průměru pak přidávání a odebírání prvků pořád běží v konstantním čase.
Hashovací tabulky se vyplatí použít často, když chceme vyhledávat vždy jednu hodnotu a přesně známe její klíč. Typicky se používají v interpretovaných jazycích, kde obsahují všechny dostupné proměnné podle jejich názvu. Naopak v některých aplikacích s velkým důrazem na bezpečnost můžou působit nespolehlivě, protože jejich rychlost je založená na vrtkavé pravděpodobnosti. Také nemusí umožňovat všechny druhy dotazů, které bychom požadovali: například v hashovací tabulce nejde rychle vyhledávat sousední klíče (nejbližší vyšší, nejbližší nižší), obzvlášť v případě, kdy hledaná hodnota v tabulce není.
Vyhledávání půlením intervalů (bisekcí) je ve svojí podstatě úplně jednoduché. Někde v paměti máme pole prvků utříděných podle velikosti (dejme tomu, rostoucí) a máme v něm najít zadaný prvek X. Tak se podíváme, jaký prvek je uprostřed pole a podle toho buďto stejným způsobem budeme pokračovat v levé, nebo v pravé polovině. V každém kroku takhle vyřadíme něco jako polovinu prvků, takže logaritmicky mnoha krocích zúžíme prohledávaný interval na jediný prvek a jeho index můžeme navrátit. Časová složitost je O(log(N)), což je mohutné zlepšení oproti tomu, kdybychom procházeli pole celé. (Mimochodem, všimněte si malého paradoxu: časová složitost je menší než paměťová. Jak to?)
Je to ale jeden z těch algoritmů, které rády padají, když zapomeneme někde přičíst jedničku. Dovolím si tedy pečlivý rozbor zadání.
Prvky ve vstupním poli si rozdělme na tři skupiny: skupina A jsou prvky menší než X, B jsou rovné X a C jsou větší. Jejich hodnoty nás podrobněji nezajímají, takže celé pole můžu přepsat jako třeba AAAABBBCCCCC. Zavedeme si dvě proměnné, ohraničující interval prvků, které ještě chceme prohledat: L je index prvku nejvíc vlevo, který nás ještě zajímá a H je první index vpravo, který nás už nezajímá. Tyhle indexy nějak budeme posouvat a algoritmus skončí právě ve chvíli, kdy L = H; tenhle index navrátí jako výsledek.
Ještě jsme se nerozhodli, co navrátit, když je správných prvků (prvků skupiny B) v poli několik. Zkusme v tom případě najít první z nich. Chceme se tedy dostat do stavu, kdy prvky vpravo od H a včetně něj jsou ze skupin B, C a prvky vlevo od L (vyjma L samotného) jsou ze skupiny A. Zapsáno trochu neobvykle, ale stručněji: pole[i < L] ∈ A & pole[i ≥ H] ∈ (B ∪ C). Zařídíme, aby tohle platilo po celou dobu běhu algoritmu.
V každém kroku tedy vybereme nějaký index i zhruba ve středu pole a podíváme se, do které skupiny patří příslušný prvek. Pokud pole[i] je ve skupině B nebo C, nezbývá nám než posunout horní hranici H na toto místo: H = i. Když je prvek pole[i] ze skupiny A, můžeme posunout spodní hranici dokonce na následující prvek: L = i + 1. Podmínka "pole[i < L] ∈ A" totiž po samotném prvku pole[L] nic nepožaduje.
Proč jsem napsal „zhruba ve středu pole”? Protože se musíme ještě rozhodnout, kam zaokrouhlovat polovinu. Záleží na tom v jediném případě, a to když nám k prohledání zbývají dva sousední prvky. V tu chvíli musíme za prostřední vzít ten levý z nich, jinak by algoritmus navěky zacyklil (můžete si rozepsat a vyzkoušet). Stačí tedy, když budeme průměr zaokrouhlovat dolů. Celý kód, zapsaný v Pythonu, vypadá takhle:
def bisekce(pole, hodnota):
dolni = 0; horni = len(pole)
while dolni < horni:
stred = (dolni + horni) // 2
if pole[stred] < hodnota:
dolni = stred + 1
else:
horni = stred
return dolni
Všimněte si, že když skupina B úplně chybí a pole je například ve tvaru AAAACCCC, algoritmus navrátí index prvního C: rozhoduje se to právě v tom stavu s dvěma prvky. Horní index na začátku nastavujeme na neexistující hodnotu len(pole) (tedy jedno místo za posledním prvkem); když v poli chybí i skupina C, algoritmus navrátí právě tuhle hodnotu. To je užitečné, ačkoliv samozřejmě musíme dát pozor, abychom ze získaného indexu rovnou nečetli.
Kdybychom se na začátku rozhodli, že chceme poslední prvek ze skupiny B, stanovili bychom si pravidla obráceně: pole[i ≤ L] ∈ (A ∪ B) & pole[i > H] ∈ C. V případě, kdy pole[i] je ve skupině A nebo B, nastavíme L = i. Když je pole[i] ve skupině C, můžeme nastavit dokonce H = i - 1. Pak si všimneme, že musíme zaokrouhlovat nahoru, aby algoritmus v posledním kroku nezatuhnul, a napíšeme upravený kód:
def bisekce(pole, hodnota):
dolni = -1; horni = len(pole) - 1
while dolni < horni:
stred = (dolni + horni + 1) // 2
if pole[stred] <= hodnota:
dolni = stred
else:
horni = stred - 1
return dolni
Všimněte si ještě, že v případě pole AAAACCCC bude výsledek tentokrát ukazovat na poslední A. Proto jsme si taky dolní hranici nastavili na -1, a algoritmus tuhle hodnotu navrátí právě v případě, že pole obsahuje jen samá céčka.
Nabízí se ještě otázka – šlo by to udělat křižmo? Třeba aby algoritmus navracel první B, ale poslední A v případě, že skupina B chybí? Samozřejmě je možné to dopsat ručně jako jednu podmínku na konec; stručněji to ale zabudovat do algoritmu neumím.