Tema5 Tabla Hash

Tema 5

Tablas hash

Gabriel Navarro

Estructuras de Datos

Grado en Ingeniera Informatica

Gabriel Navarro Tema 5 Tablas hash

Indice

Diseno de funciones hash

Encadenamiento separado

Direccionamiento cerrado


Tablas Hash

Una tabla Hash es un contenedor asociativo (ejemplo: diccionario).

Almacena valores clave en una tabla (vector o matrizhabitualmente).

Cada valor clave tiene asociado una componente de la matrizunvocamente.

Una tabla Hash ideal permite acceder a los valores clave en tiempoO(1).


Tablas Hash


Tablas Hash: Funciones hash

Llamamos funcion hash a la funcion que asocia un valor clave consu posicion en la tabla hash.

Esta funcion debe ser inyectiva. Sin embargo, encontrar talfuncion es complicado.

Si conseguimos encontrar una funcion hash biyectiva, decimosque es perfecta. Para ello, el conjunto de datos debe ser fijo yconocido a priori.

Usualmente, las funciones hash son sobreyectivas (para dosclaves se asocia la misma posicion de la tabla).

Si la funcion hash obtenida es sobreyectiva, debemos resolvercolisiones entre claves utilizando mecanismos para ello.


Tablas Hash: Funciones hash

Algunas caractersticas deseables de las funciones hash:

Deben proporcionar como salida la mayor parte de posicionesen la tabla.

Deben distribuir las claves lo mas aleatoriamente posible porla tabla.

Debe intentar minimizar el numero de colisiones.

Si suponemos que la tabla hash se implementa en un vector de Mcomponentes,existen varios metodos para disenar una funcion hash.


Tablas Hash: Diseno de funciones hash

Metodos para disenar una funcion hash:

Metodo de multiplicacion. Consiste en multiplicar la clave poralgun valor y luego quedarnos con algunos bits del resultado.Tiene el inconveniente de que M debe ser potencia de 2.

Metodo de division. Consiste en calcular el valor de la clavemodulo M, con M primo.

Metodo de multiplicacion y division. La funcion hash h(x) secalcula como la combinacion de los metodos anteriores:h(x) = (a x + b)%M , donde x es el valor de la clave, detipo entero, M es un numero primo no superior al tamano dela tabla hash, y a y b dos valores enteros, con a%M ! = 0.


Tablas Hash: Diseno de funciones hash

Dependiendo del tipo de dato de la clave, se puede calcular suvalor de varias formas:

Si es de tipo entero, utilizando ese mismo valor (por ejemplo:h(x) = x%M .

Si es de tipo cadena, utilizando la suma de los codigos ASCIIde sus caracteres (por ejemplo:h(x) = (x[0] + x[1] + ... + x[strlen(x) 1])%M .

etc.


Tablas Hash: Resolucion de colisiones

Dado que la mayor parte de las funciones hash son sobreyectivas,se debe establecer un mecanismo para resolver las colisiones entrevalores hash de claves diferentes:

Metodo de encadenamiento separado. Cada celda de la tablahash es una lista que contiene las claves con el mismo valorhash.

Metodo de direccionamiento cerrado. Si se produce unacolision, se le asigna un nuevo valor hash a la clave hasta quese encuentre una posicion de la tabla vaca.


Resolucion de colisiones: Encadenamiento separado

la tabla se representa como un vector de listas de claves.

Denominamos factor de carga al numero medio de claves por lista.Una buena funcion hash debera tender a que el factor de cargaeste proximo a 1.


Resolucion de colisiones: Encadenamiento separado

Ejemplo: Insertar claves 23, 45, 16, 26, 40, 14, 5, 12, 9, 25 con h(x)=x%13

Posicion valor

0 1 2 < >3 4 < >5 6 7 < >8 < >9 10 11 < >12


Resolucion de colisiones: Direccionamiento cerrado

La complejidad de la tabla hash aumenta, ya que cada posiciondebe contener, ademas, un flag que indique:

Posicion libre: Valor L.

Posicion ocupada: Valor O.

Posicion borrada: Valor B.

La insercion unicamente podra realizarse sobre posiciones libres(marcadas con L) o eliminadas (marcadas con B).

Si la funcion hash sobre una clave da como resultado una posicionque ya esta ocupada, el direccionamiento cerrado resuelve lascolisiones haciendo que la funcion hash dependa del numero deintento realizado para la insercion.



La funcion hash secundaria se puede disenar atendiendo a variasposibilidades:

Prueba lineal: hi(x) = (h(x) + i)%M , donde i es el numerode intento de insercion de la clave.

Prueba cuadratica: hi(x) = (h(x) + i2)%M .

hashing doble: hi(x) = (h(x) + i h(x))%M , donde h(x) es

otra funcion hash, llamada funcion hash secundaria, cuyorequisito es que nunca pueda tomar el valor 0. Un ejemplopuede ser h(x) = q (x%q), con q un numero primo menorque M.



Las busquedas de una clave en la tabla hash se realizan en elmismo orden que se siguio para la insercion.

Los borrados marcan las posiciones de la tabla con un valordistinto de libre u ocupado, para facilitar las nuevasinserciones y la busqueda de elementos.

Si la tabla se llena, se debe ampliar y seleccionar otro valor M, quesera el primo mas grande inferior al tamano de la tabla. A esteproceso se llama rehashing.

Normalmente, por motivos de eficiencia no se suele esperar a quela tabla este llena para redimencionarla (por ejemplo: Un objetoHashtable de Java se redimensiona cuando la tabla se llena en un75%).


Resolucion de colisiones: Direccionamiento cerrado.

Ejemplo.

Insercion de claves 23, 45, 16, 26, 40, 14, 5, 12, 9, 25 conhi(x) = (x + i

2)%13.

Posicion valor Estado

0 26 O1 40 O2 14 O3 16 O4 L5 5 O6 45 O7 L8 25 O9 9 O10 23 O11 L12 12 O

h0(14) = 1; ocupado.h1(14) = 2.h0(25) = 12; ocupado.h1(25) = 0; ocupado.h2(25) = 3; ocupado.h3(25) = 8.



Ejemplo.

Borrado de 26.


0 26 B1 40 O2 14 O3 16 O4 L5 5 O6 45 O7 L8 25 O9 9 O10 23 O11 L12 12 O



Ejemplo.

Busqueda de 25.


0 26 B1 40 O2 14 O3 16 O4 L5 5 O6 45 O7 L8 25 O9 9 O10 23 O11 L12 12 O

h0(25) = 12; no esta.h1(25) = 0; no esta.h2(25) = 3;no esta.h3(25) = 8. Encontrado.



Ejemplo.

Busqueda de 39.


0 26 B1 40 O2 14 O3 16 O4 L5 5 O6 45 O7 L8 25 O9 9 O10 23 O11 L12 12 O

h0(39) = 0. No esta.h1(39) = 1. No esta.h2(39) = 4. Esta libre, porlo que paramos de buscar y39 no esta en la tabla.



Ejemplo.

Insercion de 39.


0 39 O1 40 O2 14 O3 16 O4 L5 5 O6 45 O7 L8 25 O9 9 O10 23 O11 L12 12 O

h0(39) = 0. Noesta ocupada, se inserta en0.


Tema5 Tabla Hash

Documents

Transcript of Tema5 Tabla Hash