12 - Hashovací tabulky II

Přednáška 13 v oddíle Přednášky.

Anglicky coalesced hashing, je hashování podobné otevřenému, kde vkládáme prvky do jedné tabulky a v případě kolizí je pak vkládáme odzadu. Každý prvek má navíc ještě ukazatel, který ukazuje na pozici dalšího prvku kde hledat v případě kolize. V tomto je srůstající hashování zase podobné zřetězenému. Jednotlivé metody můžeme dělit podle toho, zda je na konci pole tzv. sklep, tedy část pole kterou nelze adresovat pomocí hashovací funkce (lze do ní vkládat jen při kolizích).

• Bez sklepa
  • LISCH - Late Insert Standard Coalesced Hashing - na pozici právě přidaného prvku ukazuje poslední prvek se kterým byla kolize (poslední v řetězu)
  • EISCH - Early Insert Standard Coalesced Hashing - na pozici právě přidaného prvku ukazuje první prvek se kterým došlo ke kolizi, přidaný prvek ukazuje na ten co býval druhý v řetězu (pokud existuje).
• Se sklepem
  • LICH - Late Insert Coalesced Hashing - jako LISCH, ale nejprve vkládáme kolize do sklepa (protože je na konci)
  • EICH - Early Insert Coalesced Hashing - jako EISCH, ale nejprve vkládáme kolize do sklepa (protože je na konci)
  • VICH - Variable Insert Coalesced Hashing - dokud vkládáme kolize do sklepa, vkládáme je podle LICH. Jakmile je sklep plný, vkládáme těsně za poslední prvek v řetězu který je ve sklepě. Když žádný z řetězu ve sklepě není, vkládáme podle EICH.

Řešená úloha 1: Uvažujte hash funkci $h(x) = x \; \textrm{mod} \; 9$. Vložte do hashovací tabulky čísla z posloupnosti:

$9, 11, 18, 27, 29, 36, 43, 45, 50$

Jak bude tabulka vypadat pro EISCH a jak pro LISCH?

LISCH

EISCH

Řešená úloha 2: Uvažujte hash funkci $h(x) = x \; \textrm{mod} \; 7$ a sklep o velikosti 2. Vložte do hashovací tabulky čísla z (stejné) posloupnosti:

$9, 11, 18, 27, 29, 36, 43, 45, 50$

Jak bude tabulka vypadat pro EICH, LICH a jak pro VICH?

LICH

EICH

VICH

Úloha 3:

Uvažujte hash funkci $h(x) = x \; \textrm{mod} \; 10$. Vložte do hashovacích tabulek čísla z posloupnosti:

$10, 12, 20, 23, 32, 39, 40$

Jak bude tabulka vypadat pro EISCH a jak pro LISCH?

Úloha 4:

Uvažujte hash funkci $h(x) = x \; \textrm{mod} \; 8$ a sklep o velikosti 2. Vložte do hashovacích tabulek čísla z (té samé) posloupnosti:

$10, 12, 20, 23, 32, 39, 40$

Jak bude tabulka vypadat pro EICH, LICH a jak pro VICH?

Úloha 5:

Předpokládejme, že v tabulkách získaných v příkladech 1 a 2, (případně 3 a 4) vyhledáváme pouze klíče v nich uložené a každý klíč stejně často. Která z těchto tabulek je nejvýhodnější?

💻Úloha 6:

Projděte si implementaci srůstajícího hashování. Rozšiřte HashMap o implementace otevřeného a zřetězeného hashování.