Explicación de tablas HASH.

[kamui23]

Como veo que la gente pregunta por las tablas hash, voy a explicar un poco en que consisten.

Una tabla hash es básicamente un asociación entre keys y datos. Esto quiere decir lo siguiente:

PEPE::::>1
JUAN::::>2

etc...


Se compone de:
 

    * Un vector direccionable mediante número de posición ( un array ) capaz de almacenar N elementos.
       
    * Una función de dispersión que nos permita a partir de la clave obtener el índice donde estará el dato asociado            a esa clave.Es frecuente que existan dos claves distintas para las que la función de dispersión produzca el mismo indice.Esto se denomina colisión, y las dos claves distintas que dieron lugar al mismo índice, se dicen sinónimas respecto a la función de dispersión utilizada.
       
    * Una función de resolución de colisiones.


Ahora bien, existen muchas formas de implementar una tabla de dispersión. La forma global de distinguirlas es:

tabla de dispersión cerrada

tabla de dispersión abierta

tablas de dispersión cerrada

los datos se almacenan dentro de la tabla. Esto provoca que en caso de colisión, se tenga que buscar una posición libre dentro de ésta. Como ventaja, no necesita de una estructura de datos auxiliar. Como desventaja, es posible que se produzcan colisiones en cadena.

tablas de dispersión abierta

Los elementos se almacenan en una segunda estructura de datos. Imaginaos una fila de bolsas (el array), donde en cada posición se pueden ir almacenando otra bolsa (segunda estructura de datos); que es donde finalmente se insertará el elemento. Ésta forma de implementar las tablas hash tiene mas uso y a mi gusto es la que mas utilidad tiene (dependiendo del caso, obviamente).

¿Cómo se implementa?.

Vamos a pensar un poco: es necesario que el elemento tenga una función de dispersión para decidir en que posición del array se insertará. Es  aquí donde se pueden producir las colisiones. Si la función de dispersión es buena, el problema se planteará pocas veces, pero si por el contrario es mala, la gestión de colisiones es un problema preocupante. Por lo tanto, la función de dispersión es algo vital en una tabla hash.


Ahora, un ejemplo de lo que he explicado:


Para ver este enlace Registrate o Inicia Sesion

http://www.lfcia.org/~valderru/alg/tablas_de_dispersion.pdf

Con esto y ese material, lo entendéis a la primera.

Saludos.

[Mrhappiness]

Kamui23, gracias por la explicación
tengo la siguiente tabla hash

Código:

public int hash(int codi){
        int cont1=codi;
        int cont2=codi;
        int cont3=codi;
        int posi=0;
        cont1=cont1/10000;
        cont2=(cont2-cont1*10000)/100;
        cont3=(cont3-(cont1*10000))-cont2*100;
        posi=cont1+cont2+cont3;
        return posi;
    }

codi es el codigo que ingreso en este caso el codigo son 6 digitos y al hacer la tecnica de hash me genera una posicion o clave, bien ahora como puedo evitar que exista una colision en el caso de que al ingresar otro codico el valor de posi se repita.

[kamui23]

Las colisiones son casi inevitables en las tablas hash. Lo que tendrías que hacer es optimizar la función de hashing para que el número de colisiones sea mínimo.

Si te colisionan, tienes varios métodos de gestión de colisiones. Desde buscar la primera posición vacía e insertarlo ahí, a todo lo complicado que quieras.

Dime para que es tu aplicación y yo te diré que te conviene mas.

Saludos.

[CHR0N05]

Y si haces una clase que haga comparaciones, y en el caso de que sean iguales las cambie ... De esa forma estarías evitando las colisiones, tan fastidiosas que salen...

[Mrhappiness]

La aplicacion consiste en las notas de un curso, donde el codigo va a ser la clave y esta se va a pasar por la funcion hash para generar una posicion dentro de un arreglo, pero en el caso de que la posicion se repita como evito esta colision, necesariamente debo cambiar la tecnica??

[Mrhappiness]

chrono5 no entiendo lo que me quieres decir, bueno o lo que entiendo es lo siguiente crear otra clase que me compare las 2 claves pero para cambiarlas deberia generar otra tecnica de hash para cambiar la posicion??

[CHR0N05]

Yeap!...

Bueno, yo estoy reciente con JAVA, aún estoy gateando con este lenguaje... pero es una idea, comprendiendo el funcionamiento de un HASH, por ello te doy esa idea...

Saludos...

Ps. No hagas doble post, ahy un ícono que sirve para Modificar los mensajes

[Mrhappiness]

mmm bueno gracias CHR0N05, voy a probar como dices, sin embargo me gustaria crear un metodo de dispersion para mi código pero ni idea de como hacerlo

[kamui23]

No, no tienes que crear ningún tipo de clase; debes gestionar las colisiones, una vez optmizada la función de hash. La tabla de hash ha de tener tamaño primo, para una mayor optimización.

La gestión de colisiones, pues la tienes cuadrática, ,lineal...

Te pongo un ejemplo: Tu función da como resultado la posición R. Si R está ocupada, has de buscar R+1^2, R+2^2, R+3^2... Del exponencial, el 2, viene lo de dar tamaño primo a la tabla, para no entrar en un bucle de búsquedas.

Si no lo entiendes, pregunta lo que sea.

Las notas se insertan en un array, para leerlas luego, supongo. ¿Por qué en una tabla de hash?. Además, la tabla de hash no puede hacerse por la nota, será imposible que la función de dispersión sea buena, a la larga, se repetirán, por fuerza.

[Mrhappiness]

Si la nota la inserto en un array, pero esta va amarrada con los demas datos, la clave que me da la posicion en el arreglo es el codigo del alumno luego de que se le aplica la tecnica hash.

Voy a probar con la funcion exponencial a ver que tal

[kamui23]

No se lo que es un arreglo, ¿podrías explicarlo?.