Funciones de dispersion

Funciones de Dispersión

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 < tam ;i++) { valor += Character.getNumericValue( Clave.charAt(i)); } return (valor % N); }


Método de la División


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.


Suma de ASCII


Es la función de dispersión clásica para claves de tipo cadena. Consiste en sumar los valores ASCII de la clave.

Ejemplo: “HOLA” => (‘H’+’O’+’L’+’A’) % B
§
Codigo:
for (int i=0; i
x = (x + clave.charAt(i)) % B;
}
Como ventajas citar que es una función fácil de implementar y que se ejecuta con rapidez.
Como inconvenientes podemos citar que no distribuye bien las claves si el tamaño de la tabla es grande, ya que las claves se van a situar en la
parte superior de la tabla.