EQUIPO 3
MARTINEZ CORONA VALERIA CRISTINA
GONZALEZ ROJAS VICTOR IVAN
HERNANDEZ CRUZ ARANTZA
INTRODUCCIÓN
conceptos basicos
COLISIONES EN HASHING
conceptos
tipos de colisiones
PRUEBA LINEAL
conceptos
ejemplo
PRUEBA CUADRADA
INDICE conceptos
ejemplo
PRUEBA ALEATORIA
conceptos
ejemplo
COMPARATIVA DE METODOS DE SONDEO
conceptos
ventajas y desventajas
CONCLUSIONES
EJERCICIO DE HASHING
INTRODUCCIÓN COLISIONES PRUEBA LINEAL
DEFINICIÓN: OBJETIVOS: CONCEPTOS
BASICOS:
ACCESO RÁPIDO:
EL HASHING ES UNA FUNCIÓN HASH:
BÚSQUEDA Y
CONVIERTE CLAVES EN
TÉCNICA QUE TRANSFORMA ALMACENAMIENTO ÍNDICES.
DATOS EN UN EFICIENTES. TABLA HASH: ALMACENA
MENOS COLISIONES: ELEMENTOS USANDO ESOS
IDENTIFICADOR ÚNICO ÍNDICES.
DISTRIBUIR DATOS
MEDIANTE UNA FUNCIÓN COLISIÓN: OCURRE
UNIFORMEMENTE. CUANDO DOS CLAVES
HASH, GENERANDO UN EFICIENCIA EN TIENEN EL MISMO ÍNDICE.
MEMORIA: USO SONDEO: MÉTODO PARA
VALOR FIJO
RESOLVER COLISIONES.
ÓPTIMO DEL
(GENERALMENTE UN FACTOR DE CARGA:
ESPACIO. RELACIÓN ENTRE
NÚMERO ENTERO) QUE VERSATILIDAD: USOS ELEMENTOS Y TAMAÑO DE
ACTÚA COMO ÍNDICE EN EN BASES DE DATOS, LA TABLA.
DISTRIBUCIÓN UNIFORME:
CRIPTOGRAFÍA Y
UNA TABLA HASH. EVITA COLISIONES Y
REDES. MEJORA LA EFICIENCIA.
V-A
ALGORITMO BASICO
LA FUNCIÓN DE HASH BÁSICA SERÁ
HASH_FUNCTION(KEY) = KEY % TABLE_SIZE
PARA SIMPLIFICAR.
V
INTRODUCCIÓN COLISIONES PRUEBA LINEAL
¿ QUE ES ?
AFECTAN EL
METODOS
RENDIMIENTO Y LA DE
EFICIENCIA DE LAS RESOLUCIÓN:
BÚSQUEDAS EN
ESTRUCTURAS PRUEBAS DE
COMO LAS TABLAS SONDEO
HASH.
IMPORTANCIA DE
RESOLVER UNA COLISION:
GESTIONAR COLISIONES MANTIENE
LA EFICIENCIA, VELOCIDAD Y
CAPACIDAD DE LA ESTRUCTURA HASH.
A
TIPOS DE 0 -- NULL
COLISIONES
1 -- NULL
2 -- NULL
NÚMEROS A INSERTAR : 31, 41, 13: 3 -- NULL
POSICION 1 2 3 4 5 6
4 31 -- 45 -- NULL
31 41 13
5 --
6 --
A
HASHING
Utiliza una
En caso de Incremento
función hash
colisión, se cuadrático en
secundaria para
prueba el el índice
generar saltos
siguiente índice cuando hay
aleatorios en
una colisión.
secuencialmente. caso de
colisión.
I-V-A
ALGORITMO BASICO
INTRODUCCIÓN COLISIONES PRUEBA LINEAL
I
INTENTAREMOS
INSERTAR LAS
CLAVES
[12, 22, 32].
I
I
ALGORITMO BASICO
PRUEBA CUADRADA PRUEBA ALEATORIA COMPARATIVA
V
INTENTAREMOS
INSERTAR LAS
CLAVES
[12, 22, 32].
V
V
ALGORITMO BASICO
PRUEBA CUADRADA PRUEBA ALEATORIA COMPARATIVA
A
INTENTAREMOS
INSERTAR LAS
CLAVES
[12, 22, 32].
A
A
METODOS DE SONDEO
PRUEBA CUADRADA PRUEBA ALEATORIA COMPARATIVA
ES EFICIENTE EN TABLAS
PEQUEÑAS O CON POCAS
COLISIONES, PERO EL
BRINDA LA MEJOR
CLUSTERING PRIMARIO PUEDE
RALENTIZAR DISPERSIÓN, REDUCIENDO
CONSIDERABLEMENTE EL TANTO CLUSTERING
RENDIMIENTO. PRIMARIO COMO
SECUNDARIO, A CAMBIO
MEJORA LA DISPERSIÓN EN DE UNA MAYOR
COMPARACIÓN CON LA COMPLEJIDAD Y DE UN
PRUEBA LINEAL Y REDUCE POSIBLE TIEMPO
EL CLUSTERING PRIMARIO,
ADICIONAL DEBIDO A LA
AUNQUE PUEDE SUFRIR
CLUSTERING SECUNDARIO GENERACIÓN DE NÚMEROS
SI EL TAMAÑO DE LA ALEATORIOS.
TABLA NO ES PRIMO.
A
VENTAJAS Y DESVENTAJAS
DE CADA METODO
VENTAJAS:
Menor agrupamiento
primario, buen rendimiento VENTAJAS:
VENTAJAS:
con cargas moderadas. Reduce significativamente
Fácil de implementar,
el agrupamiento y mejora
aprovecha la localidad
la dispersión de datos.
de memoria. DESVENTAJAS:
Más complejidad y pérdida DESVENTAJAS:
DESVENTAJAS:
de eficiencia en altas Generador aleatorio
Agrupamiento primario,
cargas. costoso y menor eficiencia
rendimiento decreciente
con tablas llenas. comparada con otros
métodos.
I
CONCLUSIONES EJERCICIO
Conclusion
En la elección de un método de sondeo para
resolver colisiones en tablas hash, es crucial
considerar el equilibrio entre simplicidad,
dispersión y eficiencia.
V
CONCLUSIONES EJERCICIO
IMPLEMENTAR LOS MÉTODOS DE SONDEO
INSERTAR CLAVES CON COLISIONES: USANDO LOS TRES
MÉTODOS,
INSERTA LAS MISMAS CLAVES EN TRES TABLAS DE HASH
INDEPENDIENTES.
ELIGE CLAVES QUE GENEREN COLISIONES EN LA
TABLA, COMO
[10, 20, 30, 40, 50] EN UNA TABLA DE TAMAÑO 10.
I-V-A
CODIGO
I-V-A
CODIGO FINAL
I-V-A
