====== 12 - Hashovací tabulky II ======

/*
<WRAP info> Toto cvičení prochází úpravou, zatím využijte následující zdroje.

{{:courses:a4b33alg:cviceni_12.pdf| pdf}}, {{:courses:a4b33alg:cviceni12resene.pdf| pdf}} 

{{:courses:b4b33alg:hashmaps.py| kódy zřetězeného hashování}}
</WRAP>
*/

==== Připomenutí teorie ====

Přednáška 13 v oddíle [[courses:b4b33alg:prednasky|Přednášky]].

=== Srůstající hashování ===
Anglicky [[https://www.merriam-webster.com/dictionary/coalesce | coalesce]]d 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é úlohy ====

**Ř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|
| index       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
| hodnota     | **9** | **50** | **11** | **45** | **43** | **36** | **29** | **27** | **18** |
| následovník | 8 | - | 6 | 1 | 3 | 4 | - | 5 | 7 |

++++


++++ EISCH|

| index       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
| hodnota     | **9** | **50** | **11** | **45** | **43** | **36** | **29** | **27** | **18** |
| následovník | 3 | 7 | 6 | 5 | 8 | 1 | - | 4 | - |


++++

-----

**Ř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|

| index       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 
| hodnota     | **50** | **29** | **9** | **45** | **11** | **43** | **27** | | **36** | **18** |
| následovník | - | 7 | - | - | 8 | 0 | - | | 5 | - |

++++


++++ EICH|

| index       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 
| hodnota     | **50** | **29** | **9** | **45** | **11** | **43** | **27** | | **36** | **18** |
| následovník | 5 | 0 | - | - | 8 | 7 | - | | - | - |


++++


++++ VICH|

| index       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 
| hodnota     | **50** | **29** | **9** | **45** | **11** | **43** | **27** | | **36** | **18** |
| následovník | 5 | 7 | - | - | 8 | - | - | | 0 | - |

++++

-----

==== Další úlohy ====

**Ú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?

----

<wrap todo>**Úloha 4:**</wrap>

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?

----

<wrap todo>**Úloha 5:**</wrap>

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ší?

----

<wrap caution>💻**Úloha 6:**</wrap>

Projděte si {{:courses:b4b33alg:hashmaps.py|implementaci}} srůstajícího hashování. Rozšiřte ''HashMap'' o implementace otevřeného a zřetězeného hashování. 

----