Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

HASHING Y ESTRUCTURAS DE DATOS AVANZADAS by Mind Map: HASHING Y ESTRUCTURAS DE
DATOS AVANZADAS
5.0 stars - 1 reviews range from 0 to 5

HASHING Y ESTRUCTURAS DE DATOS AVANZADAS

Las tablas de dispersión o hashing es una tecnica que se utiliza para implementar inserciones, eliminaciones y busquedas en un tiempo medio constante.

Problemas que solucionan

Operaciones y descripcion de la estructura de datos y conceptos

Colision

En informática, una colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida

Los métodos más conocidos para resolver colisiones son:, Sondeo lineal, Doble hashing, sondeo cuadratico

Como se tratan las colisiones TECNICAS

Métodos para Resolver el Problema de las Colisiones K1 y K2 que son sinónimas para la función hash R. Si  K1 es almacenada primero en el archivo y su dirección es R(K1 ), entonces se dice que K1  esta almacenado en su dirección de origen. métodos básicos para determinar dónde debe ser alojado K2 :  direccionamiento abierto separacion de desborde(area de desborde)  

Direccionamiento abierto.

Separación de desborde (Área de desborde)

Algoritmos y analisis en peor, mejor y caso promedio

Funciones de hashing comunes

o Residuo de la división

La idea de este método es la de dividir el valor de la llave entre un número apropiado, y después utilizar el residuo de la división como dirección relativa para el registro  (dirección = llave mod divisor).

o Método de la Multiplicación

       En este caso, en que 0

o 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 la dirección relativa.

o Pliegue

En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la última) tiene el mismo número de dígitos que tiene la dirección relativa objetivo.

Otros Conceptos

A   bit vector is simply an array of bits (0's and 1's). A bit vector of length m takes much less space than an array of   m pointers. Describe how to use a bit vector to Represent a Dynamic

Universal Hashing

Uso de hashing universal (en una estructura de datos o algoritmo aleatorio ) se refiere a seleccionar al azar una función hash de una familia de funciones de hash con una cierta propiedad matemática

Perfect Hashing

Una función hash perfecto para un conjunto s es una función hash que asigna elementos distintos en s a enteros distintos, con ninguna de las colisiones. Una función hash perfecto con valores en un limitado rango puede utilizarse para las operaciones de búsqueda eficaz, mediante la colocación de las claves de S (o de otros valores asociados) en una tabla indizada por la salida de la función.

Red Black Trees

Es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables (como por ejemplo números).  

aplicaciones, Busqueda de datos comparables(numeros,letras del alfabetos,simbolos)

Usos y desventajas

Operaciones, Rotacion, Busqueda, Insercion, eliminacion

Bibliografia

TECNICAS DE CALCULO DE DIRECCIONES

Técnicas de almacenamiento disperso

Técnicas aleatorias

Métodos de transformación de llave-a-dirección

Técnicas de direccionamiento directo

Métodos de tabla Hash

Métodos de Hashing

Pero el término más usado es el de hashing. Al cálculo que se realiza para obtener una dirección a partir de una llave se le conoce como función hash.

HISTORIA