Implementación de una Tabla Hash Abierta en Java

Este proyecto consiste en la implementación manual de una Tabla Hash Abierta en Java, diseñada para un problema de concurrencia en re dispersión (directa e inversa). El problema real que podemos llevar a Java y esta implementación es la gestión de pedidos y entrega de un sistema de cocina hipotética. El sistema simula el flujo de entrada (recepción) y salida (entrega) de pedidos, gestionando la memoria dinámicamente para mantener la eficiencia. Decimos orientar el problema de la gestión de cocina, porque consideramos estas 3 principales características.

• Tienen un volumen impredecible
• Entrada y salida constante de ciclos muy cortos.
• La velocidad es critica

Si usáramos una lista simple o un arreglo estático para gestionar esto, enfrentaríamos dos fallos graves.

• Una búsqueda muy lenta
• Desperdicio de memoria

Por consiguiente, decimos implementar las siguientes características alineadas a la rúbrica.

1.- Acceso Instantáneo, al usar el ID del pedido como clave (Key), el sistema calcula matemáticamente la ubicación exacta en memoria, no busca el pedido, viaja directamente a él.

2.- Redispersión, el sistema reduce o expande (directa e inversa) la memoria.

Cuando empieza la carga (muchas inserciones), la tabla detecta que se está llenando (Factor de carga > 0.90) y se expande automáticamete. Cuando los pedidos se entregan (muchas entregas eliminadas), la tabla detecta el vacío (Factor de carga < 0.50) y libera memoria, compactándose o reduciendose en tamaño y capacidad.

Aqui podemos jugar con el facto de carga para distintos comportamientos, optamos por 0.90, y por 0.50 para un dinamismo mas activo e equilibrado a nuestro punto de vista.

Factor de Carga	Velocidad (Tiempo)	Memoria (Espacio)	Acción
Bajo (< 0.25)	⚡ Muy Rápido	🗑 Desperdicia mucho	redimensionar(tamaño / 2)
Medio (0.75)	✅ Rápido	⚖️ Eficiente	(Estado ideal)
Alto (> 0.80)	🐢 Lento	📦 Ahorra espacio (demasiado)	redimensionar(tamaño * 2)

Idealmente una configuración equilibrada seria lo mejor ya que

• Eficiencia de Tiempo - garantizamos búsquedas cercanas a $O(1)$ orden de uno o tiempo constante significa que el tiempo que tarda una operación no depende de la cantidad de datos que haya en la estructura, porque evitas que las listas se llenen al crecer en 0.75.
• Eficiencia de Espacio- garantizamos no desperdiciar recursos indefinidamente (al encoger en 0.25).
• Estabilidad - evitamos el thrashing (el ciclo de crecer/encoger a lo loco) gracias al margen de seguridad entre el 0.70 directa y el 0.20 inversamente.

1. Empezemos por Pedido.java, aquí solo definimos que la información que va tener cada orden de comida en el sistema, en lugar de pasar 4 variables por separado a tus funciones, pasamos un solo objeto Pedido que lleva todo dentro:
   • idPedido: El código único (que usamos como clave).
   • nombreCliente: Quién lo pidió.
   • montoTotal: Cuánto cuesta.
   • platillos: Qué van a comer.

/**
 * Pedido.java
 */
public class Pedido {
    public static final String ANSI_GREEN = "\u001B[32m";
    public static final String ANSI_RESET = "\u001B[0m";
    private final String idPedido; // Esta es la Clave (Key)
    private final String nombreCliente;
    private final double montoTotal;
    private final String platillos;

    public Pedido(
        String idPedido,
        String nombreCliente,
        double montoTotal,
        String platillos
    ) {
        this.idPedido = idPedido;
        this.nombreCliente = nombreCliente;
        this.montoTotal = montoTotal;
        this.platillos = platillos;
    }
    // Getters necesarios
    public String getIdPedido() {
        return idPedido;
    }
 /**
  * El método @Override toString() es vital para cuando mostramos EstadoCocina    imprimes el pedido, Java no imprime una dirección de memoria rara (como *Pedido@45a877), sino que imprime el texto legible que definimos.
  */
    @Override
    public String toString() {
        return String.format( ANSI_GREEN +
            "[ID: %s  ▍ Cliente: %s  ▍ $%.2f  ▍ %s]",
            idPedido,
            nombreCliente,
            montoTotal,
            platillos
        + ANSI_RESET);
    }
}

2. Seguimos con NodoPedido.java, es la estructura de soporte como la tabla es abierta usamos nodos enlazados para manejar las colisiones.

/**
 * NodoPedido.java
 * clase de Soporte: Nodo para la lista enlazada.
 * se usa para manejar las colisiones dentro de cada índice de la tabla hash.
 */
public class NodoPedido {
    String clave;       // Guardamos la clave por separado para búsquedas rápidas
    Pedido valor;       // El objeto Pedido
    NodoPedido siguiente; // Puntero al siguiente nodo (Manejo de colisiones)

    public NodoPedido(String clave, Pedido valor) {
        this.clave = clave;
        this.valor = valor;
        this.siguiente = null;
    }
}

3. TablaHashCocina.java aquí está el cerebro de la actividad, implementa el cálculo de factor de carga y la re dispersión, como puntos importantes a comentar.

• Contiene una estructura hibrida entre Array + Lista Enlazada que demuestra que es una tabla hash abierta que utiliza estructuras de soporte (la lista enlazada) para manejar las colisiones , permitiendo que múltiples pedidos coexistan en el mismo índice.
• Aquí se define el comportamiento de la tabla en re dispersión directa y inversa.
• Se implementa el Re hashing o Recálculo de Índices, cada vez que se supera el umbral, se vuelve a dispersar los datos o órdenes.
• La función hash y valor absoluto se implementó una protección con Math.abs() dentro de la función generadora de índices muy especial, esto evita que el desbordamiento de enteros (overflow) genere índices negativos, lo cual lanzaría una excepción en Java
• Se implementa de manera basica un algoritmo conocido como FNV-1ª Fowler-Noll-Vo rápido y de gran dispersión muy bien documentado en https://www.ietf.org/archive/id/draft-eastlake-fnv-21.html ↗ ya que reduce dramáticamente las colisiones de las claves secuenciales además de utilizar multiplicaciones y operaciones XOR, mantiene la complejidad computacional baja.

/**
 * TablaHashCocina.java
 * Gestiona la inserción, búsqueda, eliminación y redimensionamiento dinámico.
*/
 public class TablaHashCocina {

     //Definiendo los colores que utilizamos en la visulización de programa
     public static final String ANSI_RESET = "\u001B[0m";
     public static final String ANSI_RED = "\u001B[31m";
     public static final String ANSI_BOLD = "\u001B[1m";
     public static final String BLUE = "\u001B[34m";
     public static final String YELLOW = "\u001B[33m";

     // Atributos de configuraciónb
     private NodoPedido[] tabla; // El arreglo principal
     private int tamanioTabla; // Capacidad actual (M)
     private int numElementos; // Cantidad real de pedidos (n)

     // Factores de carga para activar la redispersión
     // Esto definira el comportamiento de la dinamica de la expansión y reducción
     private final double FACTOR_CARGA_MAX = 0.90;
     private final double FACTOR_CARGA_MIN = 0.50;
     private final int TAMANIO_INICIAL = 5; // Empezamos pequeño para forzar colisiones y se expanda en horizontal

     public TablaHashCocina() {
         this.tamanioTabla = TAMANIO_INICIAL;
         this.tabla = new NodoPedido[TAMANIO_INICIAL];
         this.numElementos = 0;
     }
     /**
      * Función Hash (Algoritmo FNV-1a)
      * Genera un índice usando el algoritmo Fowler–Noll–Vo (FNV-1a).
      * Este algoritmo logra una dispersión "caótica" y muy aleatoria
      */
     private int generarIndice(String clave) {
         // Constantes del algoritmo FNV para 32 bits
         final int FNV_PRIME = 16777619;
         final int FNV_OFFSET_BASIS = -2128831035;

         int hash = FNV_OFFSET_BASIS;

         for (int i = 0; i < clave.length(); i++) {
             // Paso 1: XOR (Mezcla los bits de la letra actual con el hash)
             hash = hash ^ clave.charAt(i);

             // Paso 2: Multiplicación por Primo (Dispersa el resultado)
             hash = hash * FNV_PRIME;
         }
         // Paso 3: Ajustar al tamaño de la tabla (Siempre positivo)
         return Math.abs(hash) % tamanioTabla;
     }

     // Insercion(PUT)
     public void recibirPedido(String clave, Pedido pedido) {
         // A. Verificar si necesitamos crecer (Redispersión Directa)
         if ((double) numElementos / tamanioTabla >= FACTOR_CARGA_MAX) {
             System.out.println(
                     ANSI_RED +
                             ANSI_BOLD +
                             "\n🟥[AVISO] Factor de Carga supera " +
                             FACTOR_CARGA_MAX +
                             ". Redimensionando tabla (Expandiendo)..." +
                             ANSI_RESET
             );
             redimensionar(tamanioTabla * 2);
         }

         int indice = generarIndice(clave);
         NodoPedido nuevoNodo = new NodoPedido(clave, pedido);

         // B. Inserción en la lista enlazada (Manejo de colisiones)
         if (tabla[indice] == null) {
             tabla[indice] = nuevoNodo;
             numElementos++;
         } else {
             // En caso de colisión -> Recorrer la lista
             NodoPedido actual = tabla[indice];
             while (actual != null) {
                 if (actual.clave.equals(clave)) {
                     actual.valor = pedido; // Actualizar pedido existente
                     return;
                 }
                 if (actual.siguiente == null) break; // Llegamos al final
                 actual = actual.siguiente;
             }
             // Agregamos al final de la lista
             actual.siguiente = nuevoNodo;
             numElementos++;
         }
     }

     //Operación (Eliminar)
     public boolean entregarPedido(String clave) {
         int indice = generarIndice(clave);
         NodoPedido actual = tabla[indice];
         NodoPedido anterior = null;

         while (actual != null) {
             if (actual.clave.equals(clave)) {
                 // Encontrado: Eliminar nodo
                 if (anterior == null) {
                     tabla[indice] = actual.siguiente; // Era el primero de la lista
                 } else {
                     anterior.siguiente = actual.siguiente; // Saltamos el nodo
                 }
                 numElementos--;

                 // Verificar si necesitamos reducir6
                 //  (Redispersión Inversa)
                 if (
                         numElementos > 0 &&
                                 (double) numElementos / tamanioTabla <= FACTOR_CARGA_MIN &&
                                 tamanioTabla > TAMANIO_INICIAL
                 ) {
                     System.out.println(
                             ANSI_RED +
                                     ANSI_BOLD +
                                     "\n🟥[AVISO] Factor de Carga bajo " +
                                     FACTOR_CARGA_MIN +
                                     ". Compactando memoria (Reducir)..." +
                                     ANSI_RESET
                     );
                     redimensionar(tamanioTabla / 2);
                 }
                 return true; // Éxito
             }
             anterior = actual;
             actual = actual.siguiente;
         }
         return false; // No encontrado
     }

     // Operación GET
     public Pedido buscarPedido(String clave) {
         int indice = generarIndice(clave);
         NodoPedido actual = tabla[indice];
         int pasos = 0; // Para fines didácticos

         while (actual != null) {
             pasos++;
             if (actual.clave.equals(clave)) {
                 System.out.println(
                         "(Busqueda tomó " + pasos + " pasos en la lista)"
                 );
                 return actual.valor;
             }
             actual = actual.siguiente;
         }
         return null;
     }
     // Redispersión(Rehashing)
     /**
      * Crea una nueva tabla y reubica TODOS los elementos existentes.
      * Es costoso, pero necesario para mantener la eficiencia.
      */
     private void redimensionar(int nuevoTamano) {
         NodoPedido[] tablaAntigua = tabla;
         tabla = new NodoPedido[nuevoTamano];
         tamanioTabla = nuevoTamano;
         numElementos = 0; // Se recalculará al reinsertar

         // Recorrer la tabla vieja completa
         for (NodoPedido nodo : tablaAntigua) {
             while (nodo != null) {
                 // Insertar en la nueva tabla (esto recalcula el hash con el nuevo tamaño)
                 recibirPedido(nodo.clave, nodo.valor);
                 nodo = nodo.siguiente;
             }
         }
         System.out.println(
                 BLUE +
                         ANSI_BOLD +
                         "🔷[SISTEMA] Tabla redimensionada. Nueva capacidad: " +
                         tamanioTabla +
                         ANSI_RESET
         );
     }

     //  Visuzlización
     public void mostrarEstadoCocina() {
         double fc = (double) numElementos / tamanioTabla;
         System.out.println(
                 BLUE +
                         "\n⬥⬥⬥ ESTADO VISUAL DE LA COCINA (TABLA HASH ABIERTA) ⬥⬥⬥" +
                         ANSI_RESET
         );
         System.out.printf(
                 "Capacidad: %d ▍ Pedidos Activos: %d ▍ Factor de Carga: %.2f\n",
                 tamanioTabla,
                 numElementos,
                 fc
         );
         System.out.println(
                 "▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄"
         );

         for (int i = 0; i < tamanioTabla; i++) {
             System.out.printf("[Indice %2d] ", i);
             NodoPedido actual = tabla[i];
             if (actual == null) {
                 System.out.print("(Vacio)");
             } else {
                 while (actual != null) {
                     System.out.print(
                             BLUE +
                                     " → [" +
                                     actual.valor.getIdPedido() +
                                     "]" +
                                     ANSI_RESET
                     );
                     actual = actual.siguiente;
                 }
                 System.out.print(
                         YELLOW + " ◾ (Fin de la lista)" + ANSI_RESET
                 );
             }
             System.out.println();
         }
         System.out.println(
                 "▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄"
         );
     }
 }

4. Por último SistemaCocina.Java la clase principal encapsula la lógica técnica de la Tabla Hash (put, remove, get) y la expone mediante operaciones de la cocina comprensibles Recibir Pedido, Entregar Pedido, Consultar se implementó un módulo de generación automática muy simple de carga que inserta múltiples pedidos aleatorios automáticos, esta funcionalidad es crítica para saturar rápidamente la tabla y demostrar empíricamente la re dispersión directa (crecimiento del array) y el recálculo de índices sin necesidad de entrada manual tediosa, ademas que se siguen buenas prácticas de diseño de software, la clase SistemaCocina.java se limita exclusivamente a la interacción (Entrada/Salida) y delega toda la gestión de memoria y lógica algorítmica a la clase TablaHashCocina.Java.

/**
 * SisetmaCocina.Java
 */
 import java.util.Scanner;
public class SistemaCocina {

    // Colores
    public static final String ANSI_RESET = "\u001B[0m";
    public static final String ANSI_RED = "\u001B[31m";
    public static final String ANSI_GREEN = "\u001B[32m";
    public static final String ANSI_BOLD = "\u001B[1m";
    public static final String BLUE = "\u001B[34m";
    public static final String CYAN = "\u001B[36m";
    public static final String ANSI_ITALIC = "\u001B[3m";
    public static final String YELLOW = "\u001B[33m";



    public static void main(String[] args) {
        TablaHashCocina cocina = new TablaHashCocina();
        Scanner scanner = new Scanner(System.in);
        boolean salir = false;

        System.out.println(
            CYAN +
                ANSI_BOLD +
                "█ Implementación de una Tabla Hash --- Gestión de pedidos y entrega de Cocina " +
                ANSI_RESET
        );
        System.out.println(
            ANSI_GREEN +
                ANSI_BOLD +
                "█ Desarrollado por el equipo --- B61" +
                ANSI_RESET
        );
        System.out.println(
                YELLOW +
                        ANSI_ITALIC +
                        "✱ Miguel Angel Jasso Robledo \n✱ Diego Alberto Rojas Sánchez  \n✱ Giovanni Ruiz Benitez" +
                        ANSI_RESET
        );

        while (!salir) {
            System.out.println(BLUE + "\n◆◆◆ MENÚ PRINCIPAL ◆◆◆" + ANSI_RESET);
            System.out.println("1. Recibir nuevo pedido → (Insertar)");
            System.out.println("2. Entregar pedido al repartidor → (Eliminar)");
            System.out.println("3. Buscar detalles de un pedido");
            System.out.println(
                "4. Ver estado de la cocina → (Estructura Hash)"
            );
            System.out.println("5. Simulación Masiva → (Carga rápida)");
            System.out.println("6. Salir");
            System.out.print("Seleccione una opción: ");

            String opcion = scanner.nextLine();

            switch (opcion) {
                case "1":
                    System.out.print(
                        "Ingrese ID del Pedido (ej. Tacos-01,Enchiladas-02,Sushi-03,Tlacoyos-542,Quesadilla-41212,Elotes-542341,etc...): "
                    );
                    String id = scanner.nextLine();
                    System.out.print("Nombre del Cliente: ");
                    String cliente = scanner.nextLine();
                    System.out.print("Platillos: ");
                    String platos = scanner.nextLine();
                    // Simulamos precio aleatorio
                    double precio = Math.random() * 50 + 10;

                    Pedido nuevo = new Pedido(id, cliente, precio, platos);
                    cocina.recibirPedido(id, nuevo);
                    System.out.println(
                        ANSI_GREEN +
                            ANSI_BOLD +
                            "▶ Pedido ingresado correctamente." +
                            ANSI_RESET
                    );
                    break;
                case "2":
                    System.out.print("Ingrese ID del Pedido a entregar: ");
                    String idBorrar = scanner.nextLine();
                    boolean eliminado = cocina.entregarPedido(idBorrar);
                    if (eliminado) {
                        System.out.println(
                            ANSI_GREEN +
                                ANSI_BOLD +
                                "▶ Pedido " +
                                idBorrar +
                                " entregado y eliminado del sistema." +
                                ANSI_RESET
                        );
                    } else {
                        System.out.println(
                            ANSI_RED +
                                "❌ Error: El pedido no existe." +
                                ANSI_RESET
                        );
                    }
                    break;
                case "3":
                    System.out.print("Ingrese ID a buscar: ");
                    String idBuscar = scanner.nextLine();
                    Pedido encontrado = cocina.buscarPedido(idBuscar);
                    if (encontrado != null) {
                        System.out.println("🔍 DATOS ➔ " + encontrado);
                    } else {
                        System.out.println(
                            ANSI_RED + "❌ Pedido no encontrado." + ANSI_RESET
                        );
                    }
                    break;
                case "4":
                    cocina.mostrarEstadoCocina();
                    break;
                case "5":
                    System.out.println(
                        "Generando 10 pedidos automáticos para probar redispersión..."
                    );
                    for (int z = 1; z <= 10; z++) {
                        String autoId = "AUTO-" + z;
                        cocina.recibirPedido(
                            autoId,
                            new Pedido(autoId, "ClienteAuto", 100, "ComboAuto")
                        );
                    }
                    System.out.println(
                        ANSI_GREEN +
                            "✅ Carga masiva completada. Revise el estado de la cocina." +
                            ANSI_RESET
                    );
                    break;
                case "6":
                    salir = true;
                    System.out.println(
                        BLUE + "Cerrando sistema..." + ANSI_RESET
                    );
                    break;
                default:
                    System.out.println(
                        ANSI_RED + "Opción no válida." + ANSI_RESET
                    );
            }
        }
        scanner.close();
    }
}

---

Este proyecto nos ha permitido ir más allá de la teoría de las estructuras de datos. Al construir nuestra propia Tabla Hash desde cero para gestionar una cocina hipotética, entendimos que programar no es solo guardar datos, sino saber organizarlos inteligentemente para recuperarlos al instante, lo más valioso fue comprender la importancia de la adaptabilidad. A través del escenario de los pedidos de comida, vimos que un buen software debe comportarse como un organismo vivo: debe ser capaz de crecer automáticamente cuando la demanda sube y reducirse cuando el trabajo baja, optimizando así los recursos del sistema, en resumen, esta actividad cumplió con el objetivo de valorar el esfuerzo que hay detrás de las herramientas que usamos a diario, ahora sabemos que detrás de una búsqueda instantánea en una aplicación, hay una estructura matemática y lógica cuidadosamente diseñada para ofrecer velocidad y eficiencia.

Accede al Repositorio en GitHub 🚀

— Equipo B61

1. Miguel Angel Jasso Robledo
2. Diego Alberto Rojas Sanchez
3. Giovanni Ruiz Benitez

🖼️ Imágenes del proyecto