#!/usr/bin/env python
# coding: utf-8
# # Hash Taulak ( _Associative array_ , _Elkartze Arrayak_ )
#
# * _gako_ -etatik _balio_ -etarako aplikazioa
# * Python-eko `dict` eta `set` objektuak
# * _gako_ -aren gain _Hash funtzio_ bat aplikatzean, arrayari dagokion indize bat lortu.
#
# 
# ## Hash Funtzioa
#
# * Edozein informazioren gain aplikatzean, tamaina finkoko balio bat (zenbaki bat) lortu.
# * Informazio baten _sinadura_ (laburpen) digitala.
# * Propietateak:
# * Hash balioen banaketa uniformea
# * Berdinak diren bi objektuen hash balioak berdinak dira
# * Kontrakoak ez du zertan egia izan behar.
# * Adibide bat:
# * [SHA256:](https://andersbrownworth.com/blockchain/hash) _informazioa_ → 256 bit
# ## Hash Taulen bi erabilpen
#
# * **Hash Map** (hiztegiak) : `gako` → `(gako,balio)`
# * **Hash Set** (multzoak) : `gako` → `(gako,)`
#
# ## Hash Taulen inplementazioa
#
# * $N$ tamainako Taula/Array/Zerrenda bat erabili.
# * Okupazio faktorea (*load factor*): $LF : {n_{stored}}/{N}$
# * $g$ gako bati taulan dagokion posizioa: $i \; = \; hash(g)\; \% \; N$
# * *Talkak* edo *kolisioak* gerta daitezke
# * **Kolisioa**: Bi $g_1 , g_2$ gako ezberdinei $i_1 = i_2$ posizio berdina esleitzea
# * $hash(g_1) = hash(g_2)$ balio berdina izan dezakete.
# * $hash(g_1) \ne hash(g_2)$ izanda ere, $(hash(g_1)\, \% \, N) = (hash(g_2)\, \% \, N)$ gerta daiteke.
# In[34]:
N=17
T = [None]*N
print(T)
g,b = "Ane",656354364
i = hash(g)%N
T[i] = (g,b)
print(T)
g,b = "Unai",656455384
i = hash(g)%N
T[i] = (g,b)
print(T)
g,b = "Raul",656455384
i = hash(g)%N
T[i] = (g,b)
print(T)
# In[10]:
print(hash("kaixo"), hash("kaixo") % 10)
print(hash("kaixoooooooooooooooo"), hash("kaixoooooooooooooooo") % 10)
# ### Kolisioen ebazpena I : Taula berdimentsionatu
#
# * Kolisio bat ematen den bakoitzean, taularen tamaina handitu dezakegu.
# * Tamaina handitzean, talka berri baten probabilitatea txikiagoa da.
# * Baina... zenbatekoa da probabilitate hori?
# * 2450 gako baditugu 1.000.000 tamaina duen taula batetan (400-etik gelaxka bakarra okupatua), guztiz uniformea den hash funtzio bat erabilita ere, talka bat gertatzeko probabilitatea 95% da
# * _Birthday Problem_ edo [Urtebetetzeen Ebazkizuna](https://eu.wikipedia.org/wiki/Urtebetetzeen_ebazkizuna)
# * $LF \; \ll \; 1$
# * Memoriaren erabilpen **oso kaxkarra**
# ### Kolisioen ebazpena II : Helbideratze Irekia (*Open addressing*)
#
# * $g$ gako bati taulan dagokion posizioa ez da $i \; = \; hash(g)\; \% \; N$ izango
# * $i$ posiziotik abiatuko gara
# * elementua topatu arte
# * gelaxka huts bat topatu arte
#
# 
#
# In[36]:
N=10
T = [None]*N
print(T)
g,b = "Ane",656354364
i = hash(g)%N
T[i] = (g,b)
print(T)
g,b = "Unai",656455384
i = hash(g)%N
T[i] = (g,b)
print(T)
g,b = "Raul",656455384
i = hash(g)%N
# behar adina aldiz...
i = (i+1)%N
T[i] = (g,b)
print(T)
# **Helbideratze Irekia**-ren ezaugarriak:
#
# * Hash balioen banaketa uniformeak garrantzi handia du
# * $LF \; <= \; 1$
# * $LF \; > 0.7$ → **errendimendu eskasa** → Taula berdimentsionatu
#
# 
#
#
# ### Kolisioen ebazpena III : Kateatze Banatua (*Separate Chaining*)
#
# * $g$ gako bati taulako $i \; = \; hash(g)\; \% \; N$ posizioko **zerrenda** dagokio
#
# 
#
# In[42]:
N=3
T = [[] for _ in range(N)]
print(T)
g,b = "Ane",656354364
i = hash(g)%N
T[i].append((g,b))
print(T)
g,b = "Unai",656455384
i = hash(g)%N
T[i].append((g,b))
print(T)
g,b = "Raul",656455384
i = hash(g)%N
T[i].append((g,b))
print(T)
# **Kateatze Banatua**-ren ezaugarriak:
#
# * $LF \; > \; 1$ izan daiteke
# * $LF \; \gg 1$ → **errendimendu eskasa** → Taula berdimentsionatu