První série začátečnické kategorie třicátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 30-Z1-1: Kevinova nepatnáctka
- 30-Z1-2: Sářiny loutky
- 30-Z1-3: Petrovo luštění zprávy
- 30-Z1-4: Zuzčin projekt
- 30-Z1-5: Třicet totemů
- 30-Z1-6: Zuzčina první šifra
30-Z1-1 Kevinova nepatnáctka (Zadání)
Pro sledování pohybu prázdného místa v krabičce M×N pochopitelně nebylo nutné si pamatovat stav každého pole v krabičce – stačilo si vytvořit dvě číselné proměnné m a n a v nich si držet pozici prázdného místa. Při provádění posunů pak bylo třeba proměnné správně aktualizovat, a protože krabička má omezené rozměry, kontrolovat, že jsme z ní „nevypadli“.
Výchozí hodnoty m a n dostaneme na vstupu. Pak postupně procházíme znaky
posunu, ale před úpravou m a n si vždy zkontrolujeme, zda lze posun
uskutečnit. To můžeme provést například tak, že si vytvoříme proměnné dm a
dn, do kterých uložíme rozdíl nové a staré pozice (například pro znak
< bude dm = 0, dn = -1). Pak si zkontrolujeme, že m + dm je ve
správném rozsahu mezi jedničkou a M a podobně n + dn v rozsahu mezi
jedničkou a N. Pokud tomu tak je, aktualizujeme m a n.
Z programátorského hlediska mohou být zajímavé různé možnosti, jak v závislosti
na znaku posunu správně přiřadit hodnoty do dm a dn. Autorské řešení,
psané v Pythonu, používá konstrukce if a elif (else-if).
Předpokládáme, že v proměnné move je uložen znak posunu:
diff_x = 0
diff_y = 0
if move == "^":
diff_y = -1
elif move == "v":
diff_y = 1
elif move == "<":
diff_x = -1
elif move == ">":
diff_x = 1
else:
print("Chyba vstupu")
Ale například v mnoha jiných jazycích můžete použít konstrukci switch,
která rovnou počítá s tím, že rozhodujete na základě jediné proměnné. Třeba
v jazyce C:
int diff_x = 0;
int diff_y = 0;
switch (move) {
case '^':
diff_y = -1;
break;
case 'v':
diff_y = 1;
break;
case '<':
diff_x = -1;
break;
case '>':
diff_x = 1;
break;
default:
printf("Chyba vstupu\n");
}
Pokud by možných posunů bylo více, mohlo by se vyplatit si pořídit slovník, datovou strukturu, kde budou pohyby uloženy pod příslušným znakem. Při procházení pohybu se pak jenom podíváte na příslušné místo do slovníku. Takhle by mohla vypadat inicializace na začátku programu (tentokrát znovu v Pythonu):
moves_x = {'^': 0, 'v': 0, '<': -1, '>': 1}
moves_y = {'^': -1, 'v': 1, '<': 0, '>': 0}
a následné použití:
diff_x = moves_x[move]
diff_y = moves_y[move]
Pro více informací se můžete podívat do naší hešovací kuchařky. Protože je však pokročilejší, ujistěte se nejprve, že jste dobře pochopili obsah kuchařky pro začátečníky.
Ať už použijeme jakýkoliv výše uvedený postup, časová složitost bude O(T), kde T je počet posunů. Paměťová složitost bude konstantní – udržujeme si velikost krabičky a aktuální pozici prázdného místa, nic navíc.
30-Z1-2 Sářiny loutky (Zadání)
Tato úloha se dala řešit tzv. hladovým algoritmem: tak říkáme algoritmům, které jdou během výpočtu „rovnou za nosem“ a příliš si nelámou hlavu s tím, že to, co se nyní jeví jako nejlepší nápad, se nám později může vymstít.
Řekněme, že jako první se budeme zaobírat nejtěžší loutkou. Tu určitě nakonec někdy musíme pověsit, a pro výsledek je jedno, jestli to uděláme teď, nebo později.
Označme nejtěžší loutku jako T a nejlehčí loutku jako L. Přípustné budeme říkat všem loutkám, které můžeme s T pověsit, aniž by byla překročena kapacita věšáku. Podíváme se tedy, s jakou další loutkou nejtěžší loutku pověsíme. Může se stát, že kvůli nosnostem věšáků není k T žádná loutka přípustná, pak nemáme na výběr a musíme ji pověsit samotnou. V opačném případě bychom intuitivně chtěli k T pověsit z přípustných loutek co nejtěžší, abychom si co nejvíce ulehčili práci s rozvěšováním zbylých loutek. Ukáže se však, že ve skutečnosti na váze druhé loutky nezáleží a můžeme si z přípustných loutek vybrat třeba tu nejlehčí.
Jak se taková věc dokazuje? Například můžeme ukázat, že když existuje nějaké řešení, ve kterém jsme „donuceni“ dát k T nějakou jinou loutku, pak musí existovat stejně dobré řešení, ve kterém k T můžeme dát nejlehčí loutku L.
Řekněme, že máme řešení, ve kterém k naší loutce T pověsíme nějakou loutku A. Chceme toto řešení umět upravit tak, abychom k T pověsili L. To však umíme: stačí se podívat, na jaký věšák jsme L v tomto řešení umístili, a pak A a L prohodit. Rozmyslíme si, že tím nosnosti věšáků nepokazíme: Ať jsme A prohozením umístili kamkoliv, kapacitu nepřekročíme, protože když se A vešlo vedle nejtěžší loutky, vejde se vedle libovolné jiné. Na věšáku, na kterém je T, kapacitu také nepřekročíme, protože L je lehčí než A, takže T s L je lehčí než T s A.
Dostáváme hrubý obrys funkčního algoritmu: vezmeme nejlehčí loutku L a nejtěžší loutku T a zkusíme, zda L + T překročí nosnost věšáku. Pokud ano, musíme T pověsit samotnou (nevejde se k nejlehčí loutce, takže ani k žádné jiné), pokud ne, pověsíme T s L. V obou případech pověšené loutky odstraníme a postup opakujeme na zbylé loutky, dokud máme ještě nějaké nepověšené.
Všechny loutky si tedy na začátku uložíme do pole, které seřadíme vzestupně podle hmotnosti. Dokud není pole prázdné, opakovaně z něj vybíráme nejtěžší (tedy poslední) loutku a věšíme ji buď s první (nejlehčí) loutkou, nebo samotnou. Po každém pověšení odstraníme poslední prvek pole a případně i první, pokud se na věšák vešly obě loutky.
Takový algoritmus je však příliš pomalý, protože odstranění prvku ze začátku pole nás pro N loutek stojí O(N) času a těchto odstranění provedeme až O(N).
Můžeme však časovou složitost snadno zlepšit: to, co nás stojí hodně času, je opakované odstraňování prvků ze začátku seznamu. To se ale chová celkem předvídatelně: po k odstraněních ze začátku bude na prvním místě v seznamu prvek, který byl na začátku programu na (k+1)-tém místě. Podobně se chová odstraňování z konce pole.
Nemusíme tedy z okrajů seznamu vůbec
odstraňovat, stačí pracovat s původním polem a pamatovat si navíc ukazatele na
nejlevější a nejpravější ještě nepověšenou loutku, které zvýšíme resp. snížíme
o jedna vždy, když jsme v původním algoritmu odstraňovali prvek ze začátku
resp. konce seznamu. Také se nám změní podmínka ve while cyklu, protože
už netestujeme, zda je seznam prázdný, nýbrž zda je výřez pole určený našimi
dvěma ukazateli prázdný (tedy zda se první ukazatel dostal za druhý).
Takto upravený algoritmus už pro každý věšák vykoná jen konstantně mnoho práce: podívá se na dva indexy do pole, spočte součet dvou hmotností a posune nejvýše oba ukazatele o jedna. Jelikož je však věšáků řádově tolik, co loutek (určitě jich není méně než N/2 a více než N), stráví algoritmus věšením loutek O(N) času. Nesmíme však zapomenout na seřazení, které na začátku musíme provést. K tomu můžeme použít libovolný rychlý třídící algoritmus, například některý z naší třídící kuchařky, ve které se mimo jiné dočtete, že za rychlé považujeme třídící algoritmy, které pro obecná data běží v čase O(N log N). To je tedy zároveň celková časová složitost našeho programu. Paměťová složitost je O(N), protože nám stačí pamatovat si všechny loutky v poli, případně s nějakým čítačem počtu použitých věšáků.
30-Z1-3 Petrovo luštění zprávy (Zadání)
Naším cílem je najít pro každou pozici v textu nejčastější znak z několika zpráv. Ukážeme si několik způsobů, jak na to, a porovnáme jejich efektivitu. Zpráv je N a jejich délku nazvěme například T.
Nabízí se vytvořit dvourozměrné pole velikosti 26×T s počty výskytů znaků, kde každý řádek odpovídá jednomu z písmen abecedy a sloupeček pozici v textu. Políčko v poli tedy bude odpovídat počtu výskytů daného znaku na dané pozici v textu.
Pokud nyní budeme procházet přes políčka našeho pole a snažit se vypočítat jejich hodnoty, tak skončíme s nepříliš efektivním algoritmem. Abychom vyplnili hodnotu v políčku pro daný znak a pozici v textu, tak musíme z každé zprávy přečíst jeden znak, tedy celkem projdeme N znaků. Toto budeme muset udělat pro každé políčko, kterých je 26×T, a tedy celkem při vyplňování tabulky provedeme 26×T×N operací.
Půjdeme na to jinak, vyhneme se opakovanému čtení zpráv. Pokud máme na začátku toto velké pole vynulované, tak můžeme postupně procházet text zpráv ze vstupu. Pro každý přečtený znak známe jeho pozici a o jaký znak jde, tedy můžeme v tabulce do patřičného políčka přičíst 1. Tento postup provede pouze T×N operací a také nám vyplní tabulku. Zároveň víme, že přesně tolik má znaků vstup, tedy tato část rychleji ani nepůjde.
Poté, co máme takovéhle pole, nám stačí projít všechny sloupce a v každém najít pozici maxima. Pak na vstup můžeme vypsat znaky, kterým tato maxima přísluší.
Zbavme se ještě potřeby velkého pole. Jeho velikost je sice O(N), ale vystačíme si s polem velikosti jenom 26. Pro zjištění jednoho znaku pro výstup totiž potřebujeme jen informace z jednoho sloupečku. Můžeme tedy jen projít znaky všech zpráv na té pozici a spočítat si četnost výskytů. Pak vybereme maximum, vypíšeme znak, vyčistíme pole a přesuneme se na další pozici.
Všechny naše algoritmy měly sice asymptotickou časovou složitost O(TN), ale první algoritmus byl 26-krát pomalejší, což se u opendatové úlohy projeví.
Paměťová složitost prvního přístupu s velkou tabulkou byla zřejmě O(TN). Pro řešení s polem konstantní velikosti je ale bohužel také O(TN), jelikož si musíme do paměti uložit text načtený ze vstupu, abychom ho mohli procházet po sloupcích. Pokud se ale podíváme na konstanty, tak jsme si polepšili. Nyní totiž máme pole, do kterého ukládáme maximálně 26 různých hodnot. Naopak pro velkou tabulku četností musíme být schopni uložit N různých hodnot.
Ještě se bude hodit jeden implementační detail. Pro naše řešení je potřeba nějak
přepočítat znaky A až Z na čísla 0 až 25 pro indexování v poli. Naštěstí v ASCII
kódování jsou všechna tato písmena za sebou a v běžných programovacích jazycích
lze typicky znak převést na číslo v ASCII. Pak můžeme prostě odečíst 65, což je
hodnota A v ASCII. Pro převod z indexu na znak naopak 65 přičteme. Například
v Pythonu k tomuto slouží funkce ord() a chr().
30-Z1-4 Zuzčin projekt (Zadání)
Úloha po nás chce pro každý dotaz sestavit organizační hierarchii a pak se podívat na jednoho pracovníka a jeho pomocníky. Můžeme postupovat poměrně přímočaře a výběr spolupracovníků odsimulovat. Nejdříve najdeme hlavního ředitele, pak všechny jeho přímé podřízené, pak všechny jejich podřízené atd. Takto budeme postupně budovat jednotlivá „patra“ hiearchie, dokud nedojdeme k hledanému člověku, nebo neprojdeme všechny.
Jen je potřeba dát pozor na to, abychom nevolili jako podřízené lidi, které už jsme zvolili dříve – je potřeba si pro každého člověka pamatovat, jestli už je zařazen, například v seznamu indexovaným číslem člověka. Pak je třeba dát pozor na to, že každý dává přednost výše postaveným nadřízeným a pak těm s nižším číslem. Nikdo výše postavený ho při našem budování pater už oslovit nemůže, protože to by se stalo už při procházení předchozího patra; nižší číslo však někdo další mít může. Stačí si ale před průchodem patro setřídit podle čísla člověka a oslovovat postupně od člověka s nejmenším číslem, aby každého oslovil první ten, kdo má „největší přednost“. Třídění pravděpodobně najdete ve standardní knihovně svého oblíbeného jazyka a běžně používaným algoritmům to trvá O(N log N), kde N je velikost pole. Pokud nevíte, jak to funguje, můžete se podívat do kuchařky o třídění
Jak dlouho to bude trvat, když provedeme až O(N) setřídění až O(N) velkého pole? Můžeme ale nahlédnout, že každý člověk bude jen v jednom patře, protože každého vybereme jen jednou. Takže se nám sice může stát, že v jednom patře bude třeba polovina všech lidí, ale určitě se nám nestane, že ve všech patrech dohromady bude víc lidí než jich je celkem. Pak je docela zřejmé, že třídění nám zabere dohromady maximálně O(N log N) času, protože dohromady nebudeme třídit víc než N prvků. Pak ještě potřebujeme u každého nadřízeného projít všechny kamarády a zkusit je přiřadit – což je vlastně projití všech „kamarádských vazeb“. Celková časová složitost tak bude O(N log N + M) pro každý dotaz, kde N jsme si označili počet lidí a M počet vazeb mezi nimi.
Toto řešení stačilo na plný počet bodů. Poznamenejme, že to jde i v O(N + M); toto řešení zde však detailně popisovat nebudeme. Zájemci mohou nahlédnout do zdrojového kódu.
Program (Python 3, O(N log N + M))
30-Z1-5 Třicet totemů (Zadání)
Naším úkolem bylo nalézt správné počty klád K a P tak, aby totemy, které Kevin a Petr postaví, byly stejně vysoké. Informaticky řečeno máme na vstupu dvě posloupnosti délek klád a hledáme takové jejich počáteční úseky, které mají stejný součet.
Pro potřeby určení složitosti algoritmů si řekněme, že počty klád na hromadách jsou M a N, tedy K < M a P < N.
Nejprve si rozmyslíme, jak je vlastně rychlé to nejjednodušší řešení: vyzkoušení všech kombinací. Pro každé K si projdeme všechna možná P a zjistíme, jestli výsledné totemy nejsou stejně vysoké.
Pokud bychom počítali výšku totemů pro každé P a K znovu, zabralo by nám toto zjištění O(M+N) času. Každý ale vidí, že pokud je budeme brát postupně, můžeme si spoustu práce ušetřit. Pokud známe výšku totemu pro nějaké K, výšku totemu pro K+1 získáme přičtením délky (K+1)-ní klády. Pro P to platí analogicky.
S tímto pozorováním už sestavíme následující algoritmus, který vyzkouší všechny kombinace počtů použitých klád:
Delky_K = [...]
Delky_P = [...]
Totem_K = 0
for K in 1 .. M + 1:
Totem_K = Totem_K + Delky_K[K - 1]
Totem_P = 0
for P in 1 .. N + 1:
Totem_P = Totem_P + Delky_P[P - 1]
if Totem_K == Totem_P:
print(K, P)
Pro zachování programátorských konvencí předpokládáme, že první prvek pole má
index 0, a for cyklus 0 .. N projde možnosti od 0 do N-1 včetně.
Poměrně snadno vidíme, že vnitřní cyklus udělá nejvýše tři kroky, a spustí se (MN)-krát. Proto je časová složitost algoritmu O(MN).
S tím se ale nespokojíme! Je přeci jasné, že vyzkoušet všechny možnosti nemůže být to nejrychlejší řešení. To rychlejší může být vidět už z představy, jak by úlohu řešili Petr s Kevinem s opravdovými kládami: pochybuji, že by zkoušeli zvyšovat vyšší z totemů s nadějí, že se tím výška vyrovná.
Z této myšlenky vymyslíme algoritmus rychlejší. Oba aktéři začnou s prázdnými totemy, a v každém kroku jednu kládu přidá ten, jehož totem je menší:
Totem_K = Totem_P = 0
K = P = 0
while True:
if Totem_K < Totem_P and K < M:
K = K + 1
Totem_K = Totem_K + Delky_K[K - 1]
elif P < N:
P = P + 1
Totem_P = Totem_P + Delky_P[P - 1]
else:
break
if Totem_K == Totem_P:
print(K, P)
Všimněte si, že v případě stejné výšky obou totemů (i nulové) kládu přidává Petr.
Je potřeba si důkladně rozmyslet, že tento algoritmus vydá správný výsledek. Vcelku zřejmě nevypíše žádnou možnost, která není správná, ale není zřejmé, že nějakou správnou možnost nepřeskočí.
Na chvíli podezírejme algoritmus z toho, že přeskočil správnou možnost Kx, Px s výškou totemů T. Všimněte si, že druhá větev podmínky neobsahuje ověření, že Petrův totem je nižší – algoritmus skončí, až když P = N - 1. Víme tedy jistě, že algoritmus v jednu chvíli měl P = Px. Jak vypadalo K ve chvíli, kdy se tak stalo poprvé?
Jednou možností je, že Kevinův totem byl sice ostře menší, ale už mu žádné další klády nezbývají. To se ale stát určitě nemohlo, vždyť by pak Kevin nikdy nemohl postavit totem výšky T.
Druhou možností je, že Kevinův totem byl vyšší než Petrův, a proto algoritmus zvýšil P. Protože předpokládáme, že algoritmus možnost Kx, Px přeskočil, musel v tu chvíli už mít K > Kx, jinak by možnost jistě našel.
To ovšem znamená, že už dříve nastala situace, ve které měl algoritmus K = Kx, a P < Px. Snadno ale vidíme, že v takové situaci by algoritmus jen zvyšoval P, dokud by ztracenou možnost nenašel. Algoritmus tedy žádnou správnou možnost přeskočit nemohl.
Jak je teď algoritmus rychlý? V každé iteraci se zvýší jedna z proměnných K nebo P. Ani jedna z nich však nemůže být vyšší než M, respektive N. Dostali jsme tedy algoritmus s lineární časovou složitostí O(M+N). To už je hodně dobré, protože stejný čas nám zabere i čtení vstupu. Zrychlovat už nejspíše není třeba.
Poslední, nad čím bychom se mohli zamyslet, je paměťová složitost. Nám stačí pouze čtyři pomocné proměnné. Vstup potřebujeme přečíst pouze jednou, a s drobnou modifikací bychom ho mohli číst průběžně a nemuseli bychom si ho pamatovat celý. Podobně výstup můžeme vypisovat průběžně. Náš algoritmus by pak mohl mít až konstantní paměťovou složitost.
30-Z1-6 Zuzčina první šifra (Zadání)
Naším úkolem je zjistit, na které z pozic je nejvíce položených písmen Zuzčiny šifry a kolik jich je. Avšak na vstupu jsme souřadnice nedostali přímo, ty musíme nejprve spočítat.
Zaveďme si ze začátku pár pojmů. Počet centimetrů na východ označíme x, na sever y, samotná poloha poté bude (x,y). Dále N bude počet všech písmen a K bude počet všech navzájem různých poloh. Pokud bychom měli deset písmen na jednom místě, pak N = 10, K = 1.
Každý záznam v Zuzčině seznamu je relativní posun aktuální pozice vůči té předchozí. Dále víme, že Zuzka začala na pozici (0,0) před prvním položením písmena. Tudíž například pro záznamy (1,3), (-2,5), (0,-4) jsou skutečné souřadnice písmen (1,3), (-1,8), (-1,4).
Algoritmus, jak tyto souřadnice spočítat, je tedy jednoduchý. Na začátku si nastavíme souřadnice aktuální pozice Zuzky P = (0,0). Nyní budeme postupně číst záznamy Z = (x,y) a každý z nich postupně přičteme k P. Tak získáme jak polohu jednoho z písmen, tak novou aktuální polohu P' pro následující záznam.
Nuže, nyní umíme spočítat skutečné souřadnice, pojďme najít tu s nejvyšším počtem výskytů.
Přímočaré řešení
Uložme si všech N souřadnic písmen do pole. Nyní se jako velmi jednoduché řešení nabízí pole pro každý prvek projít a spočítat, kolik souřadnic se tomuto prvku rovná, a vrátit tu s nejvyšší četností. Toto je potřeba provést, protože dvě stejné souřadnice můžou být na úplně různých místech v poli.
Tento způsob prohledávání je ale velmi pomalý. Pro každou souřadnici v poli procházíme celé pole znovu, provedeme tedy celkem O(N2) operací.
Pojďme tento postup vylepšit. Pole souřadnic tentokrát seřadíme, a to tak, že kdykoliv rozhodujeme o vzájemném pořadí dvou prvků, nejprve porovnáme x a v případě rovnosti ještě porovnáme y (Takové seřazení se nazývá lexikografické).
Toto seřazení nám způsobí, že se stejné souřadnice dostanou k sobě, tvoříce souvislý úsek. Můžeme proto projít pole zleva doprava a vždy počítat počet totožných sousedních souřadnic. Bude nás zajímat souřadnice se zatím nejvyšším počtem výskytů; tu si budeme spolu s tímto počtem udržovat a na konci obojí vrátíme.
Jak dlouho nám celý tento algoritmus potrvá? Samotné zjištění souřadnic písmen a jejich vložení do pole využije O(N) času. Následovné seřazení pole nás bude stát O(N log N) času a konečné procházení polem na zjištění nejčastějšího výskytu znovu potrvá O(N) času. Celkový strávený čas nám tedy vyjde O(N log N). Paměti spotřebujeme O(N) kvůli uloženému poli.
Takto efektivní řešení stačí pro plný počet bodů. Ukážeme si však, že tuto úlohu jde vyřešit i rychleji.
Využití jiných datových struktur
Náš problém nyní vyřešíme bez použití (setříděného) pole. Místo toho použijeme datovou strukturu, která nám na danou souřadnici odpoví, kolik je na ní písmen.
Zkusme nejprve použít tabulku, kde řádky odpovídají všem možným souřadnicím na východ, sloupce všem na sever a odpovídající buňka má uložený počet písmen s touto souřadnicí.
To bohužel vůbec nefunguje. Zahrada je nekonečně rozlehlá, souřadnice jednoho písmene může nabývat nesmírně vysokých hodnot. Taková tabulka se zcela jistě nevejde do paměti.
Tento nápad přesto nevede do slepé uličky. Místo tabulky uvažujme slovník (V běžných programovacích jazycích se se slovníkem můžete setkat pod názvem dictionary, případně map.). Takový slovník si pamatuje dvojice (klíč, hodnota), přičemž lze do něj klíče přidávat či odstraňovat v průběhu algoritmu. Dále slovník umí zjistit, zda klíč existuje a jakou má hodnotu, nebo tuto hodnotu změnit. Rovněž umí slovník projít všechny klíče v něm uložené.
V našem slovníku budou klíčem souřadnice písmen a hodnotou počet písmen s touto souřadnicí. Souřadnice, na kterých žádné písmeno není, nebudeme do slovníku vkládat. Celkový počet klíčů v tomto slovníku bude potom K.
V průběhu algoritmu nyní postupujme takto: Při počítání souřadnic se pro každou z nich vždy podíváme do slovníku, jestli se v něm jako klíč již vyskytuje. Pokud ne, přidáme ji a nastavíme počet výskytů na 1. Pokud ano, přičteme za ní výskyt. Nakonec projdeme všechny klíče a vrátíme ten s nejvyšší hodnotou.
Jak jsme na tom s časem a pamětí tentokrát? Nevyhneme se počítání souřadnic, to nám vždy zabere O(N) času. Existují různé vnitřní podoby slovníků. My budeme pro jednoduchost uvažovat vyhledávací stromy, o kterých se lze více dozvědět v naší kuchařce.
V takovém případě nám každé vyhledání i vložení souřadnice do vyhledávacího stromu potrvá O(log K) a celkem jich proběhne N. Přičtení počtu výskytu v již nalezeném klíči potrvá O(1). Nakonec projití všech klíčů nás bude stát O(K). Celková časová složitost nám v tomto případě vyjde jako O(N + K + N log K) a paměťová složitost bude O(K). Pro K výrazně nižší než N jsme si tedy pomohli.
Na závěr podotkněme, že se na slovníky častěji používají hešovací tabulky, které umí vkládat a vyhledávat až v čase O(1) v průměru. Ty jsou ale podstatně složitější než vyhledávací stromy.