¿De qué consta una tabla hash?

Una tabla hash consiste en un array de tamaño fijo (cubeta o ranura) y una función hash.

• Array (Cubetas/Ranuras): Representa una secuencia de celdas donde se almacenan pares "clave-valor". El tamaño del array determina la cantidad de lugares posibles para almacenar elementos.

• Función hash: Convierte la clave en un valor entero (código hash), que se usa para determinar el índice de la celda en el array (cubeta), donde se almacenará o se extraerá el valor correspondiente.

Además, puede haber:

• Estrategia de resolución de colisiones: Mecanismo para manejar situaciones en las que diferentes claves generan el mismo código hash y apuntan a la misma celda del array. Estrategias comunes:
  • Método de encadenamiento (Encadenamiento separado): Cada celda del array almacena un puntero a una lista enlazada (u otra estructura de datos), que contiene todos los pares "clave-valor" cuyos códigos hash apuntan a esa celda.
  • Método de direccionamiento abierto: En caso de colisión, se busca una celda libre en el array siguiendo una regla determinada (por ejemplo, sondeo lineal o cuadrático).