Tabla hash para niños

Una tabla hash es una forma especial de organizar información en una computadora. Imagina que tienes un montón de cosas (como nombres de personas y sus números de teléfono) y quieres guardarlas de una manera que sea muy fácil y rápida de encontrar. Una tabla hash hace exactamente eso.

Funciona como un diccionario: tienes una "clave" (por ejemplo, el nombre de una persona) y quieres encontrar su "valor" (su número de teléfono). La tabla hash usa una "función hash", que es como una fórmula mágica. Esta fórmula toma tu clave (el nombre) y la convierte en un número. Este número le dice a la tabla exactamente dónde está guardado el número de teléfono. Es como tener un índice súper rápido para encontrar lo que buscas.

Las tablas hash son muy eficientes para buscar información, casi siempre encuentran lo que necesitas al instante, sin importar cuántos datos tengas. Sin embargo, a veces, dos claves diferentes pueden generar el mismo número, lo que se llama una "colisión". Cuando esto pasa, la tabla tiene formas especiales de resolverlo para que toda la información se guarde y se encuentre correctamente.

Plantilla:Ficha de estructura de datos

¿Cómo funciona una tabla hash?

Las tablas hash se usan para guardar y encontrar datos rápidamente. Piensa en ellas como grandes estantes con muchos compartimentos. Cada compartimento tiene un número.

Guardar información (Inserción)

Para guardar algo en una tabla hash, sigues estos pasos:

1. Tienes una clave (por ejemplo, el nombre de un amigo) y un valor (su número de teléfono).
2. La clave se pasa por una "función hash". Esta función convierte el nombre en un número.
3. Ese número se ajusta para que encaje en uno de los compartimentos de la tabla. Esto te da la posición exacta donde guardar el número de teléfono.
4. Si el compartimento ya está ocupado (¡una colisión!), la tabla tiene trucos para encontrar otro lugar cercano o para guardar varios elementos en el mismo compartimento, como si fuera una lista.

Encontrar información (Búsqueda)

Para encontrar algo que ya guardaste:

1. Solo necesitas la clave (el nombre de tu amigo).
2. La clave se pasa por la misma función hash para obtener el número de compartimento.
3. Vas a ese compartimento. Si el elemento que está allí tiene la misma clave, ¡lo encontraste!
4. Si no es la misma clave (por una colisión anterior), la tabla sabe cómo buscar en los lugares cercanos hasta encontrarlo.

Para que una tabla hash funcione bien, necesitas:

• Un lugar donde guardar los datos, como una lista grande de compartimentos (un array).
• Los datos que quieres guardar, que siempre tienen una clave.
• Una "función hash" que convierta las claves en números para saber dónde guardar o buscar.

Ejemplo práctico de tabla hash

Imagina que tienes muchos periódicos que llegan cada día y quieres organizarlos para encontrarlos rápidamente.

• Haces una caja grande para todos los periódicos (esta es tu tabla).
• Divides la caja en 31 compartimentos más pequeños (ahora es una tabla hash).
• La clave para guardar los periódicos es el día de publicación.
• Cuando quieres buscar un periódico, miras el día en que se publicó y sabes en qué compartimento está.
• Puede que varios periódicos del mismo día queden en el mismo compartimento (una colisión). En ese caso, buscas en la pequeña lista de periódicos que hay dentro de ese compartimento.

De esta forma, no tienes que revisar todos los periódicos, solo los de un compartimento específico, lo que hace la búsqueda mucho más rápida.

Ejemplo de tabla hash.

Consejos para las funciones hash

Una buena función hash es muy importante para que la tabla funcione rápido. Si la función no es buena, puede que muchos datos terminen en el mismo compartimento, haciendo que las búsquedas sean lentas.

Una función hash ideal debería:

• Cambiar mucho el número resultante si la clave cambia un poquito.
• Distribuir los datos de manera uniforme en todos los compartimentos.

A menudo, el tamaño de la tabla hash (el número de compartimentos) se elige como un número primo. Esto ayuda a que las claves se distribuyan mejor y haya menos colisiones.

¿Cómo se resuelven las colisiones?

Cuando dos claves diferentes generan el mismo número de compartimento, se produce una colisión. Hay dos técnicas principales para resolverlas:

Encadenamiento (Listas enlazadas)

Ejemplo de encadenamiento.

En esta técnica, cada compartimento de la tabla no guarda un solo dato, sino una pequeña lista. Si varios datos quieren ir al mismo compartimento, se añaden a la lista de ese compartimento.

• Ventajas: Es fácil añadir y quitar datos. La tabla puede llenarse bastante antes de que se vuelva lenta.
• Desventajas: Si las listas se hacen muy largas, la búsqueda dentro de ellas puede ser un poco más lenta.

Direccionamiento abierto (Búsqueda de espacio)

Ejemplo de direccionamiento abierto.

Aquí, los datos se guardan directamente en los compartimentos de la tabla. Si un compartimento está ocupado, la tabla busca otro compartimento cercano siguiendo una "secuencia de sondeo" hasta encontrar uno vacío. Las formas más comunes de buscar un espacio son:

• Sondeo lineal: Busca en el siguiente compartimento, luego en el siguiente, y así sucesivamente. Es bueno para el rendimiento, pero puede agrupar los datos.
• Sondeo cuadrático: El salto entre compartimentos aumenta cada vez.
• Doble hashing: Usa otra función hash para calcular el tamaño del salto.

Es importante que la tabla no esté demasiado llena (normalmente no más del 80% de su capacidad) para que las búsquedas sigan siendo rápidas con el direccionamiento abierto.

Ventajas y desventajas de las tablas hash

Ventajas

• Búsqueda muy rápida: Si la tabla no está muy llena y la función hash es buena, encontrar un dato es casi instantáneo.

Desventajas

• Necesidad de crecer: Si se guardan muchos datos, la tabla puede llenarse y necesitar hacerse más grande, lo cual puede ser un proceso que toma tiempo.
• Dificultad para recorrer: No es fácil ver todos los elementos en orden, ya que se guardan en posiciones "aleatorias".
• Uso de memoria: A veces se reserva más espacio del que se usa, lo que puede desperdiciar memoria.

Implementación sencilla (Pseudocódigo)

Aquí te mostramos cómo se vería un algoritmo simple para una tabla hash con direccionamiento abierto:

registro par { llave, valor } var vector de pares casilla[0..numcasillas-1]

function buscacasilla(llave) { i := hash(llave) módulo de numcasillas loop { if casilla[i] esta libre or casilla[i].llave = llave return i i := (i + 1) módulo de numcasillas } }

function búsqueda(llave) i := buscacasilla(llave) if casilla[i] está ocupada // llave está en la tabla return casilla[i].valor else // llave no está en la tabla return no encontrada

function asignar(llave, valor) { i := buscacasilla(llave) if casilla[i] está ocupada casilla[i].valor := valor else { if tabla casi llena { hacer tabla más grande (nota 1) i := buscacasilla(llave) } casilla[i].llave := llave casilla[i].valor := valor } }

Tipos de funciones hash comunes

Las funciones hash transforman una clave en un número que sirve como índice. Aquí hay algunas ideas:

Restas sucesivas

Si tienes números de control de alumnos que son casi consecutivos, puedes restar el primer número de control a los demás para obtener un índice simple. Ejemplo:

• 05210800 - 05210800 → 0
• 05210801 - 05210800 → 1

Aritmética modular

Tomas un número y calculas el "resto" de dividirlo por otro número (preferiblemente primo). Este resto es tu índice. Ejemplo (si el número divisor es 7):

• 1679 → 6 (porque 1679 dividido por 7 da un resto de 6)
• 4567 → 3 (porque 4567 dividido por 7 da un resto de 3)

Mitad del cuadrado

Elevas la clave al cuadrado y tomas las cifras del medio del resultado. Ejemplo:

• 709^2 = 502681 → tomas el 26

Truncamiento

Ignoras algunas partes de la clave y usas las restantes como índice. Ejemplo (si tomas la segunda, cuarta y sexta cifra de un número de 7 cifras):

• 5700931 → 703

Plegamiento

Divides la clave en partes y las sumas (o multiplicas). Si el resultado es muy grande, puedes tomar solo las últimas cifras. Ejemplo (dividir en partes de 2, 2 y 3 cifras y sumar):

• 5700931 → 57 + 00 + 931 = 988

Tablas hash dinámicas

Las tablas hash normales tienen un tamaño fijo. Pero, ¿qué pasa si necesitas guardar más y más datos? Las tablas hash dinámicas pueden crecer o encogerse según sea necesario.

Métodos de expansión total

Cuando la tabla se llena demasiado, se duplica su tamaño. Por ejemplo, si tienes una tabla de tamaño N, se convierte en 2N, luego 4N, y así sucesivamente. Cada vez que la tabla crece, todos los datos deben ser reubicados usando la función hash para el nuevo tamaño.

Métodos de reducción total

Si la tabla se vacía mucho, puede reducir su tamaño a la mitad para ahorrar espacio.

Métodos de expansión parcial

En lugar de duplicar, la tabla aumenta su tamaño en un 50% cuando se llena.

Métodos de reducción parcial

Similar a la expansión parcial, la tabla reduce su tamaño en un 50% si se vacía mucho.

Tablas hash distribuidas

Las tablas hash distribuidas son una versión avanzada donde los datos no se guardan en una sola computadora, sino que se reparten entre muchas computadoras (llamadas nodos). Esto permite manejar cantidades gigantescas de información y encontrarla rápidamente, incluso si está dispersa en una red.

Véase también

En inglés: Hash table Facts for Kids