TEMA 3

TRANSFORMACIÓN DE CLAVES (HASHING)

…o como encontrar, con el mínimo esfuerzo, una clave dada dentro de un conjunto de elementos.

OBJETIVOS DE ESTE CAPITULO:

• Concepto de `Hashing' (Dispersión).

• Colisiones y su tratamiento

• Cómo puede convertirse una clave dada en otra con funciones de trasformación

• Cómo optimizar el concepto de trasformación de claves

INDICE TEMA 3.

3.1 Transformación de Claves

3.1.1 Hash

3.2 Manejo de Colisiones

3.2.1 Externo

Encadenamiento Directo

Overflow

Interno

Encadenamiento Directo

Encadenamiento Vacío

3.2.2.2.2 Inspección Cuadrática

3.3. Elección de la función de transformación

Método del centro de los cuadrados

Método de la división

Método de desplazamiento

Método de plegamiento

Factor de carga y efectividad

1. TRANSFORMACIÓN DE CLAVES

Sea un conjunto C: