Implementujte dvě hašovací tabulky a dva systémy hašovacích funkcích. Následně je srovnejte na dvou variantách operací složených z vložení a vyhledávání. Operace Insert vytváří množinu, tedy Insert s duplicitním klíčem nezmění tabulku, jen se započítá do statistik. První varianta operací, Insert, je zvolena tak, že vyhledávání tvoří 20 % operací. Druhá varianta, Find, tak, že vyhledání tvoří 80 % operací.
Implementujte lineární přidávávaní (linear probing) dle prědnášky. Implementujte variantu kukaččího hašování z přednášky s jedinou tabulkou. Velikost tabulky zvolte rovnou parametru M, který je popsán v sekci o generování dat. Pro generovaní dat pro kukačkové hašování použijte parametr C, který omezí faktor naplnění.
Tabulační funkce. Nechť x je prvek univerza U, představme si jej jako bitový řetězec rozdělený na c stejně dlouhých částí, t.j. x = x1x2...xc. Pro každou z těchto c částí uniformně náhodně inicializujme její tabulku, která obsahuje 2u/c bitových řetězců délky k. Pak h(x) = T1(x1) ⊕ T2(x2) ⊕ ... ⊕ Tc(xc). Tedy pro každou část získáme index do tabulky, kde je uloženo číslo z množiny {0, ..., m - 1}. Výsledek hašovací funkce je XOR takhle získaných hodnot. Rychlá implementace spoléhá na fixní volbu c, například c = 4.
Multiplikativní funkce. Nechť x je prvek z univerza U, a nechť a ∈ U - {0} je uniformně náhodně zvolené číslo. Pak h(x) = ((a * x) mod |U|) / (|U| / m).. Pro 32-bitové univerzum lze tutu funkci implementovat efektivně pomocí posunů a zanedbání přetečení při násobení.
Pro každou variantu dat udělejte dva grafy. První graf bude ukazovat průměrný počet operací na jednu operaci Insert nebo Find vzhledem k faktoru naplnění, druhý graf bude ukazovat průměrný čas (zvolte milisekundy nebo mikrosekundy tak, aby byl graf přehledný) na operaci Insert nebo Find vzhledem k faktoru naplnění.
Sepište zprávu, v níž bude:
Pro vygenerování testovacích dat použijte už zkompilovaný generátor
/afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw5/hashgen
dostupný v unixové laboratoři Rotunda.
Spusťte ho s následujícími parametry:
-s XX
, kde XX jsou poslední dvě číslice
vašeho studentského čísla;--short
, pro kratší data;I
, pokud chcete vygenerovat data, v kterých převládá operace Insert;F
, pokud chcete vygenerovat data, v kterých převládá operace Find;C
, pokud chcete generovat data pro Cuckoo Hashing přidejte tenhle argument, maximální faktor naplnění bude omezen na 55 %.Generátor produkuje textový výstup, každý řádek je tvaru:
# N M
: začátek běhu pro množinu velikosti N uložené do tabulky velikosti M –
zrušte starou tabulku a založte novou. Velikost množin se vám může hodit při kreslení grafů. Navíc velikost M bude během generovaní dat pořád stejná a bude to mocnina dvojky. N určuje velikost množiny, kterou tenhle běh vytvoří, t.j. počet úspěšných Insert operací v běhu.I X
: vložení klíče X do tabulky;F X
: vyhledání klíče X v tabulce.Na jedno spuštění generátor vytvoří sadu testů s faktorem naplnění od 30 do 90% (nebo 55 %, pokud jste zadali i parameter C). Pro každý faktor naplnění jsou vygenerovány čtyři běhy. Výsledky zakreslete zprůměrovány přes tyto běhy.
# 2 4 I 1 I 2 I 1 I 3 F 1 # 3 4 I 2 I 3 I 7 I 3 I 2 F 2 F 0
Pošlete e-mail s předmětem tvaru 'HW5-55973318' (t.j. HW5-studentské číslo) s těmito přílohami:
Tělo e-mailu nechť obsahuje údaje podle tohoto vzoru:
Jmeno: Martin Babka
Pseudonym pro vysledky na webu: Babočka Admirál
Cviceni: pondeli-12:20-lichy