Hashing
Jérémy Barbay 30 Sep 201030/09/10 a las 15:19 hrs.2010-09-30 15:19:30
Hashing
=======
Author: Jérémy Barbay
Date: 2010-09-30 19:17:05 XXX
SCHEDULED: <2010-09-30 Thu 12:00-13:30>
Table of Contents
=================
1 Introduccion
2 Hashing Abierto
3 Hashing Cerrado
4 Universal Hashing
5 Hashing en memoria externa
1 Introduccion
~~~~~~~~~~~~~~~
* Motivaciones
- Mejor tiempo *en promedio*
- Uso de todos la herramientas que tenemos
- dominio de las valores
- distribuciones de probabilidades de las valores
* Terminologia
- Tabla de Hash
- Arreglo de tamaño $N$
- que contiene $n$ elementos a dentro de un universo [1..U]
- Funccion de Hash $h(K)$
- $h:[1..U] \rightarrow [0..N-1]$
- se calcula rapidamente
- distribue uniformemente (mas o menos) las llaves en la tabla
en el caso ideal, $P[h(K)=i] = 1/N, \, \forall K,i$
- Collision
- cuando $h(K_{1))= h(K_{2})$
- la probabilidad es alta: "Paradoxe del cumpleanos"
- Cual es la probabilidad que en una pieca de $n$ personas,
dos tiene la misma fecha de cumpleaños (a dentro de $365$
dias)?
- probabilidad que cada cumpleaños es unico:
$ 364! \over {(365 - n)!} \over { 365^{n-1} }$
- Probabilidad que hay al menos un cumpleanos compartido:
$ 1 - 364! \over {(365 - n)!} \over { 365^{n-1} }$
n Proba
-----+----------
10 .12
23 .5
50 .97
100 .9999996
2 Hashing Abierto
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisions con caldenas
2) Ejemplo: (muy irealistico)
- h(K) = K mod 10
- Secuencia de insercion 52,18,70,22,44,38,62
- Insertando al final (si hay que probar por repeticiones)
0 70
1
2 52,22,62
3
4 44
5
6
7
8 18,38
9
- Insertando al final (si no hay que probar por repeticiones)
0 70
1
2 62,22,52
3
4 44
5
6
7
8 38,18
9
3) Analisis:
- factor de carga es $\lambda= {n \over N}$
- Rendimiento en el peor caso: $\Oh(n)$
3 Hashing Cerrado
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisiones con busqueda, i.e.
- ( h(K)+f(i) ) mod N
- differentes tipos de busqueda:
- lineal f(i) = i
- primary "clustering" (formacion de secuencias largas)
- cuadratica f(i) = i^2
- secundario "clustering" (si h(K_1)=h(K2), la
secuencias son las mismas.
- doble hashing f(i) = i . h'(K)
- h'(K) debe ser prima con N
2) Ideal Hashing
- Imagina una funcion de hash que genera una secuencia que
parece aleatoria.
- cada posicion tiene la misma probabilidad de ser la
proxima
- Probabilidad $\lambda$ de elegir una posicion ocupada
- Probabilidad $1-\lambda$ de elegir une posicion libre
- OJO! la secuencia de prueba puede tocar la misma
posicion mas que una vez.
- OJO! llaves identicas todavia siguen la misma
secuencia.
- Cual es el costo promedio $u_j$ de una busqueda negativa
con $j$ llaves en la tabla?
- $\lambda= \frac{j}{N}$
- $u_j = 1 (1-\lambda) + 2\lambda(1-\lambda)+r\lambda^2(1-\lambda)+....$
- = 1 + \lambda + \lambda^2 + ...
- = \frac{1}{1-\lambda}
- = \frac{1}{1-j/N}
- = \frac{N}{N-j} \in[1..N]
- Cual es el costo promedio de una busqueda positiva $s_i$
para el $i$-th elemento insertado?
- $s_i = \frac{1}{1- i/N} = \frac{N}{N-i}$
- $s_n = 1/n \sum \frac{N}{N-i} $
- = \frac{N}{n} \sum_{i=0}^{n-1} \frac{1}{N-i}
- = \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{N-i}
con $\alpha = \frac{n}{N}$
- < \frac{1}{\alpha} \integral_{N-n}^{N} 1/x dx
- = 1/\alpha \ln\frac{N}{N-n}
- = 1/\alpha \ln\frac{1}{\alpha}
- Para $\alpha = 1/2$, el costo promedio es $1.387$
- Para $\alpha = 0.9$, el costo promedio es $2.559
4 Universal Hashing
~~~~~~~~~~~~~~~~~~~~
- h(K) = ( (aK+b) mod p) mod N
- a \in [1..p-1] elegido al azar
- b \in [0..p-1] elegido al azar
- p es primo y mas grande que N
- N no es necesaramente primo
5 Hashing en memoria externa
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Que pasa si la tabla de hashing no queda en memoria?
- IDEA: Simula un B-arbol de altura dos
- organiza el dato con valores de hash
- guarda un index en el nodo raiz
- usa solamente *una parte* de la valor de hash para elegir
el sobre-arbol
- extiende el index cuando mas dato es agregado
2) Descripción
- B - cantidad de elementos en una pagina
- h - funcion de hash -> [0..2^k-1]
- D - *profundidad general*, con D\leq k
- la raiz tiene $2^D$ punteros a las paginas horas
- la raiz es indexada con los $D$ primeros bits de cada
valor de hash.
- $d_l$ - *profundidad local* de cada hora $l$
- Las valores de hash en $l$ tienen en comun los primeros
$d_l$ bits.
- Hay $2^{D-d_l}$ punteros a la hora $l$
- Siempre, $d_l\leq D$
3) Ejemplo
- $B=4, k=6, D=2$
$d_l=2$ 000100
001000
001011
001100
$d_l=2$ 010101
011100
$d_l=1$ 100100
101101
110001
111100
4) Algoritmos
- Buscar
- Insertar
- Remover
5) Analisis
- Buscar, insertar remover
- 1 acceso a la memoria secundariaa si el index se queda
- cantidad Promedio de paginas para tener $n$ llaves
- $\frac{n}{B\lg 2}\approx 1.44 \frac{n}{B}$
- paginas son llenas a 69% mas o menos.
=======
Author: Jérémy Barbay
Date: 2010-09-30 19:17:05 XXX
SCHEDULED: <2010-09-30 Thu 12:00-13:30>
Table of Contents
=================
1 Introduccion
2 Hashing Abierto
3 Hashing Cerrado
4 Universal Hashing
5 Hashing en memoria externa
1 Introduccion
~~~~~~~~~~~~~~~
* Motivaciones
- Mejor tiempo *en promedio*
- Uso de todos la herramientas que tenemos
- dominio de las valores
- distribuciones de probabilidades de las valores
* Terminologia
- Tabla de Hash
- Arreglo de tamaño $N$
- que contiene $n$ elementos a dentro de un universo [1..U]
- Funccion de Hash $h(K)$
- $h:[1..U] \rightarrow [0..N-1]$
- se calcula rapidamente
- distribue uniformemente (mas o menos) las llaves en la tabla
en el caso ideal, $P[h(K)=i] = 1/N, \, \forall K,i$
- Collision
- cuando $h(K_{1))= h(K_{2})$
- la probabilidad es alta: "Paradoxe del cumpleanos"
- Cual es la probabilidad que en una pieca de $n$ personas,
dos tiene la misma fecha de cumpleaños (a dentro de $365$
dias)?
- probabilidad que cada cumpleaños es unico:
$ 364! \over {(365 - n)!} \over { 365^{n-1} }$
- Probabilidad que hay al menos un cumpleanos compartido:
$ 1 - 364! \over {(365 - n)!} \over { 365^{n-1} }$
n Proba
-----+----------
10 .12
23 .5
50 .97
100 .9999996
2 Hashing Abierto
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisions con caldenas
2) Ejemplo: (muy irealistico)
- h(K) = K mod 10
- Secuencia de insercion 52,18,70,22,44,38,62
- Insertando al final (si hay que probar por repeticiones)
0 70
1
2 52,22,62
3
4 44
5
6
7
8 18,38
9
- Insertando al final (si no hay que probar por repeticiones)
0 70
1
2 62,22,52
3
4 44
5
6
7
8 38,18
9
3) Analisis:
- factor de carga es $\lambda= {n \over N}$
- Rendimiento en el peor caso: $\Oh(n)$
3 Hashing Cerrado
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisiones con busqueda, i.e.
- ( h(K)+f(i) ) mod N
- differentes tipos de busqueda:
- lineal f(i) = i
- primary "clustering" (formacion de secuencias largas)
- cuadratica f(i) = i^2
- secundario "clustering" (si h(K_1)=h(K2), la
secuencias son las mismas.
- doble hashing f(i) = i . h'(K)
- h'(K) debe ser prima con N
2) Ideal Hashing
- Imagina una funcion de hash que genera una secuencia que
parece aleatoria.
- cada posicion tiene la misma probabilidad de ser la
proxima
- Probabilidad $\lambda$ de elegir una posicion ocupada
- Probabilidad $1-\lambda$ de elegir une posicion libre
- OJO! la secuencia de prueba puede tocar la misma
posicion mas que una vez.
- OJO! llaves identicas todavia siguen la misma
secuencia.
- Cual es el costo promedio $u_j$ de una busqueda negativa
con $j$ llaves en la tabla?
- $\lambda= \frac{j}{N}$
- $u_j = 1 (1-\lambda) + 2\lambda(1-\lambda)+r\lambda^2(1-\lambda)+....$
- = 1 + \lambda + \lambda^2 + ...
- = \frac{1}{1-\lambda}
- = \frac{1}{1-j/N}
- = \frac{N}{N-j} \in[1..N]
- Cual es el costo promedio de una busqueda positiva $s_i$
para el $i$-th elemento insertado?
- $s_i = \frac{1}{1- i/N} = \frac{N}{N-i}$
- $s_n = 1/n \sum \frac{N}{N-i} $
- = \frac{N}{n} \sum_{i=0}^{n-1} \frac{1}{N-i}
- = \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{N-i}
con $\alpha = \frac{n}{N}$
- < \frac{1}{\alpha} \integral_{N-n}^{N} 1/x dx
- = 1/\alpha \ln\frac{N}{N-n}
- = 1/\alpha \ln\frac{1}{\alpha}
- Para $\alpha = 1/2$, el costo promedio es $1.387$
- Para $\alpha = 0.9$, el costo promedio es $2.559
4 Universal Hashing
~~~~~~~~~~~~~~~~~~~~
- h(K) = ( (aK+b) mod p) mod N
- a \in [1..p-1] elegido al azar
- b \in [0..p-1] elegido al azar
- p es primo y mas grande que N
- N no es necesaramente primo
5 Hashing en memoria externa
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Que pasa si la tabla de hashing no queda en memoria?
- IDEA: Simula un B-arbol de altura dos
- organiza el dato con valores de hash
- guarda un index en el nodo raiz
- usa solamente *una parte* de la valor de hash para elegir
el sobre-arbol
- extiende el index cuando mas dato es agregado
2) Descripción
- B - cantidad de elementos en una pagina
- h - funcion de hash -> [0..2^k-1]
- D - *profundidad general*, con D\leq k
- la raiz tiene $2^D$ punteros a las paginas horas
- la raiz es indexada con los $D$ primeros bits de cada
valor de hash.
- $d_l$ - *profundidad local* de cada hora $l$
- Las valores de hash en $l$ tienen en comun los primeros
$d_l$ bits.
- Hay $2^{D-d_l}$ punteros a la hora $l$
- Siempre, $d_l\leq D$
3) Ejemplo
- $B=4, k=6, D=2$
$d_l=2$ 000100
001000
001011
001100
$d_l=2$ 010101
011100
$d_l=1$ 100100
101101
110001
111100
4) Algoritmos
- Buscar
- Insertar
- Remover
5) Analisis
- Buscar, insertar remover
- 1 acceso a la memoria secundariaa si el index se queda
- cantidad Promedio de paginas para tener $n$ llaves
- $\frac{n}{B\lg 2}\approx 1.44 \frac{n}{B}$
- paginas son llenas a 69% mas o menos.
| Última Modificación | 30 Sep 201030/09/10 a las 15:19 hrs.2010-09-30 15:19:30 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
