jueves, 21 de mayo de 2009

Funciones de dispersion



FUNCIONES DE DISPERSION



Consiste en la elección de una clave, para el buen funcionamiento de la estructura, debe cumplir las siguientes características:
• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.


En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. Hay que cuenta que N (el tamaño de la tabla) ha de ser un número primo.
El código seria:

prívate static int Hash1(String Clave) {

int valor = Clave.charAt(0);

int tam = Clave.length();

for (int i = 1; i <>

valor += Character.getNumericValue( Clave.charAt(i));

}

return (valor % N); }

METODO DE DIVISION


§Es la función de dispersión clásica para claves enteras.
§Consiste en tomar el resto de la división de la clave por el número de entradas de la tabla (B).
§Código: x = x % B;
§Como ventajas citar que es una función fácil de calcular y que se puede utilizar para tablas de cualquier tamaño, aunque se recomienda elegir B con cuidado.
§Como inconvenientes podemos citar que el rango de valores es limitado.

No hay comentarios:

Publicar un comentario en la entrada