Dgdfgfjf
Páginas: 2 (441 palabras)
Publicado: 15 de noviembre de 2012
"Hashing" es una técnica que busca realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante. Esa característica es muy importante cuando se traba con almacenamientosecundario en disco, donde el acceso a una determinada dirección es bastante lento. Algunas aplicaciones que son beneficiadas por el uso de tablas hash son diccionarios y tablas de palabras reservadas de uncompilador.
En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma en cuenta solamente su valor absoluto, interpretado como un valor numérico.En pocas palabras Una función de Hash es una caja negra que tiene como entrada una llave y como salida una dirección
La idea básica de este método consiste en aplicar una función que traduce unconjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden noser todas únicas, cuando R(k1 )= R(k2)
Pero: K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.HASHING POR RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para elregistro (dirección = llave módulo divisor).
Ejemplo:
Numero de direcciones 996. La elección de m será 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO
En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir ladirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n...
En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma en cuenta solamente su valor absoluto, interpretado como un valor numérico.En pocas palabras Una función de Hash es una caja negra que tiene como entrada una llave y como salida una dirección
La idea básica de este método consiste en aplicar una función que traduce unconjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden noser todas únicas, cuando R(k1 )= R(k2)
Pero: K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.HASHING POR RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para elregistro (dirección = llave módulo divisor).
Ejemplo:
Numero de direcciones 996. La elección de m será 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO
En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir ladirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n...
Leer documento completo
Regístrate para leer el documento completo.