Metodo de mediante transformacion de clave
Páginas: 4 (775 palabras)
Publicado: 7 de octubre de 2010
Búsqueda Mediante Transformación De Claves (“Hashing”)
El Método de Búsqueda Mediante Transformación de Clave (Hashing), es un método que no necesita del ordenamiento de los elementos y aumentala velocidad de búsqueda, a diferencia de otros métodos como lo hemos visto anteriormente.
Este consiste en convertir la clave dada (numérica o alfanumérica) en una dirección (índice) dentro delarray. La correspondencia entre las claves y la dirección en el medio de almacenamiento o en el array se establece por una función de conversión (hash).
Es decir que se dará la relaciónsiguiente para la conversión de clave:
Clave: x función de conversión H( dirección.
Métodos de la trasformación de clave:
Existen diversos métodos de trasformación de claves, los cualestienen en común la necesidad de convertir claves en direcciones. Este proceso se denotara de la forma siguiente:
X(
Truncamiento
Ignora parte de la clave y se utiliza la parte restantedirectamente como índice (considerando campos no numéricos y sus códigos numéricos).
Si por ejemplo tenemos un entero de 8 dígitos y una tabla de 100 posiciones entonces el primero y quinto numero desdela derecha, pueden formar la función de conversión. Por ejemplo 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.
Estose debe a que puede generar la misma dirección y generar colisiones.
Plegamiento
La técnica de plegamiento consiste en la partición de la clave en diferentes partes y la combinación de laspartes en un modo conveniente(a menudo utilizamos suma o multiplicación) para obtener el índice.
La clave x se divide en varias partes x1, x2,…..,xn, donde cada parte, con la única posibleexcepción de la ultima parte, tiene el mismo número de dígitos que la dirección especificada.
A continuación, se suman todas las partes:
H(x)= x1+x2+,…..,+xn
En esta se desprecian los dígitos más...
El Método de Búsqueda Mediante Transformación de Clave (Hashing), es un método que no necesita del ordenamiento de los elementos y aumentala velocidad de búsqueda, a diferencia de otros métodos como lo hemos visto anteriormente.
Este consiste en convertir la clave dada (numérica o alfanumérica) en una dirección (índice) dentro delarray. La correspondencia entre las claves y la dirección en el medio de almacenamiento o en el array se establece por una función de conversión (hash).
Es decir que se dará la relaciónsiguiente para la conversión de clave:
Clave: x función de conversión H( dirección.
Métodos de la trasformación de clave:
Existen diversos métodos de trasformación de claves, los cualestienen en común la necesidad de convertir claves en direcciones. Este proceso se denotara de la forma siguiente:
X(
Truncamiento
Ignora parte de la clave y se utiliza la parte restantedirectamente como índice (considerando campos no numéricos y sus códigos numéricos).
Si por ejemplo tenemos un entero de 8 dígitos y una tabla de 100 posiciones entonces el primero y quinto numero desdela derecha, pueden formar la función de conversión. Por ejemplo 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.
Estose debe a que puede generar la misma dirección y generar colisiones.
Plegamiento
La técnica de plegamiento consiste en la partición de la clave en diferentes partes y la combinación de laspartes en un modo conveniente(a menudo utilizamos suma o multiplicación) para obtener el índice.
La clave x se divide en varias partes x1, x2,…..,xn, donde cada parte, con la única posibleexcepción de la ultima parte, tiene el mismo número de dígitos que la dirección especificada.
A continuación, se suman todas las partes:
H(x)= x1+x2+,…..,+xn
En esta se desprecian los dígitos más...
Leer documento completo
Regístrate para leer el documento completo.