Habla sobre las tablas hash y su principio de…

La tabla hash (mapa hash) es una estructura de datos que implementa un array asociativo, mapeando claves a valores.

Principio de funcionamiento:

Hashing: Para cada clave, se calcula un código hash, un valor numérico de tamaño fijo mediante una función hash. Una buena función hash distribuye los códigos hash de manera uniforme en todo el rango de salidas.
Indexación: El código hash calculado se usa para determinar el índice (posición) en el array donde se almacenará el valor correspondiente. Frecuentemente, el código hash módulo el tamaño del array (hash(key) % array_size) da el índice final.
Almacenamiento: En el array, en el índice calculado, se guarda un par (clave, valor).
Búsqueda: Para encontrar un valor por clave, se vuelve a calcular el código hash de la clave, se determina el índice, y en ese índice se extrae el valor.
Colisiones: Ocurren cuando diferentes claves tienen el mismo código hash. Existen varios métodos para resolver colisiones:
- Método de encadenamiento (Separate Chaining): En cada índice del array se mantiene una lista (u otra estructura de datos) que contiene todos los pares (clave, valor) cuyos códigos hash conducen a ese índice.
- Método de direccionamiento abierto (Open Addressing): Cuando ocurre una colisión, se busca otro lugar libre en el array según una regla determinada (sondeo lineal, sondeo cuadrático, doble hashing).

Ventajas:

En promedio, las operaciones de inserción, eliminación y búsqueda tienen complejidad O(1), si la función hash es buena y las colisiones son raras.

Desventajas:

La peor situación en rendimiento puede ser O(n), si todas las claves se hash en el mismo índice (por ejemplo, con una mala función hash o muchas colisiones).
Se requiere memoria adicional para el array y, posiblemente, para resolver colisiones.

En Swift, las tablas hash están implementadas con el tipo Dictionary.

// Ejemplo de uso de Dictionary en Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Acceso por clave
let value = myDictionary["banana"] // Obtiene Optional(2)

// Añadir/actualizar
myDictionary["grape"] = 4 // Añade un nuevo par
myDictionary["apple"] = 10 // Actualiza el valor para la clave "apple"

// Eliminación
myDictionary["orange"] = nil // Elimina el par con clave "orange"

Habla sobre las tablas hash y su principio de funcionamiento principal.