[C con Clase] administrador tabla hash con direccionamiento abierto

[Steven R. Davidson]

Hola Germán,

German Ponce wrote:
> me gustaria saber si hay dentro de la pagina cconclase o en otro lugar 
> un ejemplo de lo que tiene que tener una tabla hash con direccionamiento 
> abierto asi como la construccion de adminstrador de tablas hash, 
> cualquier ayuda sera bien recibida .
> 
> el motivo de esta consulta es para construir la tabla de simbolos de un 
> compilador
> 

Direccionamiento abierto o "háshing" cerrado se basa en crear una tabla 
hash cuyos elementos contienen la información interesada. Típicamente, 
usamos un cálculo sencillo para "hashear" los datos, como suele ser el 
módulo de la división. Por ejemplo,

h(k) = k mod m, donde

'k' es la clave (o dato numérico), y
'm' es la cantidad máxima de elementos en nuestra tabla. Uno suele usar 
un valor que sea una potencia de dos para 'm'.

Por ejemplo, tenemos el cálculo:

h(k) = k mod 16, y

los siguientes valores:

45, 32, 602, 1031, y 923

Aplicamos la función 'h(k)' a cada valor, obteniendo:

h(45)   =   45 mod 16 = 13
h(32)   =   32 mod 16 = 0
h(602)  =  602 mod 16 = 10
h(1031) = 1031 mod 16 = 7
h(923)  =  923 mod 16 = 11

La tabla hash sería la siguiente:

0  => 32
1  => --
2  => --
3  => --
4  => --
5  => --
6  => --
7  => 1031
8  => --
9  => --
10 => 602
11 => 923
12 => --
13 => 45
14 => --
15 => --

Sin embargo, tenemos un problema si quisiéramos agregar el valor de 
1024, ya que h(1024) = 0. Como la tabla hash ya contiene un valor en el 
índice 0, el número 32, nos encontramos con una colisión.

Para resolver colisiones en el direccionamiento abierto, tenemos algunos 
métodos que podemos implementar. Los métodos más populares se basan en 
modificar la función 'h(k)' para buscar otro "hueco" en la tabla. He 
aquí los más populares:


* Investigación o Búsqueda lineal  (linear probing)

Modificamos la función agregando un desplazamiento (lineal) al cálculo; 
esto es,

h(k,i) = (k + i) mod m, donde i=0,1,2,...

Inicialmente, aplicaríamos h(k,0) que es igual a la función original de 
h(k). Si ésta no da el resultado que queremos, entonces probamos con 
i=1. Si tampoco da resultado, entonces con i=1, i=2, i=3, etcétera hasta 
que algún valor de 'i' dé el resultado esperado. Si damos la vuelta 
completa: h(k,0) = h(k,i) entonces abandomos el intento, sin poder 
realizar el háshing.

Usando el ejemplo anterior, ingresamos 1024 de la siguiente manera:

h(1024) = 1024 mod 16 = 0    => colisión
h(1024,1) = 1025 mod 16 = 1  => sin colisiones


* Investigación o Búsqueda cuadrática  (quadratic probing)

El método anterior sufre de un problema importante: agrupamiento. Los 
valores se agruparán linealmente, si hubo colisiones. Para aminorar este 
problema, usamos otro cálculo:

h(k,i) = (k + a*i + b*i^2) mod m, donde i=0,1,2,... y b != 0

Usando el ejemplo, agregamos 1024 así:

h(k,i) = (k + i + 3*i^2) mod 16, donde a=1 y b=3.

Probanod con h(1024,0) sabemos que existe una colisión, por lo que 
pasamos a i=1:

h(1024,1) = (1024 + 1 + 3*1) mod 16 = 4

Si este índice también provocase una colisión, entonces pasaríamos a 
probar con i=2:

h(1024,2) = (1024 + 2 + 3*4) mod 16 = 14


* Doble Háshing  (double hashing)

Aquí básicamente usamos dos funciones de háshing. El ejemplo popular 
para hacer esto es,

h(k,i) = (f(k), + i*g(k)) mod m.

Ahora bien, para que este método sea práctico, el valor de 'g(k)' debe 
ser relativamente primo a 'm'. Podemos dejar que 'm' sea una potencia de 
dos y que 'g(k)' sea impar. Por ejemplo,

f(k) = k mod m,
g(k) = (2*k+1) mod m'.

Usando nuestro ejemplo, colocamos 1024 con m=16 y m'=15 así:

h(1024,1) = (f(1024) + g(1024)) mod 16.

f(1024) = 1024 mod 16 = 0
g(1024) = (2*1024+1) mod 15 = 9

Por lo que tenemos,
h(1024,1) = (0 + 9) mod 16 = 9


Otra forma es escoger números primos para los módulos. Por ejemplo,

f(k) = k mod m,
g(k) = 1 + (k mod m'),

Podríamos escoger m=13 y m'=11.


Espero que todo esto te ayude.

Steven