Programa Java para implementar tablas de direccionamiento directo

Las estructuras de datos se utilizan principalmente para almacenar datos y administrar una gran cantidad de datos, y las estructuras de datos eficientes son útiles para desarrollar mejores algoritmos. Las principales operaciones realizadas en una estructura de datos son Insertar, Buscar, Actualizar y Eliminar. Con cantidades crecientes de datos, todas estas operaciones tienden a tomar una gran cantidad de tiempo. 

Puede haber escenarios en los que queramos que todas estas operaciones se realicen en tiempo O(1), es decir, en tiempo constante. Para implementar esto, tenemos una estructura de datos llamada tabla de direccionamiento directo.

La tabla de direccionamiento directo es una estructura de datos aleatorios que mapea registros con sus claves únicas correspondientes mediante arrays. En Direct Address Tables, las claves de los registros se utilizan directamente como índices. Esto ayuda en las operaciones de inserción, búsqueda y eliminación rápidas y eficientes.

Las siguientes operaciones se pueden realizar en tiempo O(1):

1. Inserción: insertar un elemento en un índice en una array lleva O (1) tiempo. Aquí también, para la inserción de un elemento, la clave se utiliza como índice.
2. Búsqueda: el uso de valores clave como índices proporciona una búsqueda más rápida para buscar cualquier registro.
3. Eliminación: para eliminar un elemento de la tabla de direcciones directas, configure el índice/ubicación para que apunte a nulo.

Ejemplo 

Consideremos que se nos da la tarea de crear y mantener un catálogo de datos de estudiantes universitarios de una división en particular con una capacidad máxima de 70 estudiantes por división. Cada estudiante tiene un número de registro único asignado a él/ella. La tarea es almacenar la información completa de cada estudiante de manera eficiente. Ahora, podemos usar el número de registro de un estudiante como clave para poner sus datos en ese índice. En primer lugar, creamos una array arr de tamaño 70 que actuará como nuestra tabla de direcciones directas.

Supongamos que insertamos los datos del estudiante con el número de lista 13, usamos 13 como índice e insertamos los datos de ese estudiante en arr[13]. Inserte los datos de otro estudiante con el número de registro 18, usamos 18 como índice e insertamos los datos de ese estudiante en arr[18]. La siguiente imagen es una representación de la operación de inserción que se está realizando.

Tabla de direccionamiento directo usando arrays

Ahora, considere que queremos recuperar la información sobre el estudiante con el número de lista 18, podemos usar directamente 18 como índice y obtener los datos de ese estudiante en arr[18]. Este método de búsqueda en la tabla de direcciones da acceso a los datos en tiempo O(1). Supongamos que queremos eliminar la información sobre el estudiante con el número de lista 13 (tal vez porque dejó la universidad), usar 13 como índice y eliminar los datos de ese estudiante en arr[13] estableciéndolo en nulo.

Pero existen algunas limitaciones en el uso de esta estructura de datos:

1. Las claves deben ser números enteros/pueden convertirse a números enteros.
2. Todas las claves deben ser únicas.
3. El rango de claves enteras debe ser relativamente pequeño (de lo contrario, necesitaremos una gran cantidad de memoria)
4. Las claves enteras deben estar lo suficientemente cerca (de lo contrario, habrá más ranuras vacías y se desperdiciará memoria)

Implementación:

Veamos la implementación del ejemplo anterior: 

// Java program to implement Direct Addressing Table 
  
import java.util.*;
  
class Student {
    int rollNumber;
    String name, gender;
    
    Student(int rollNumber, String name, String gender)
    {
        this.rollNumber = rollNumber;
        this.name = name;
        this.gender = gender;
    }
}
  
class DirectAddressingTable {
    public static void main(String[] args)
    {
        // We want to create a catalogue of college students of some division 
          // Each division has atmost 70 students and roll number starts from 1 
        // Create "Direct Addressing Table" (catalogue) for the students' data 
        
        Student[] catalogue = new Student[71];
  
        // Insert some students' data into the catalogue
        insert(catalogue, new Student(11, "Rahul", "Male"));
        insert(catalogue, new Student(18, "Joe", "Male"));
        insert(catalogue, new Student(15, "Kavya", "Female"));
        insert(catalogue, new Student(13, "Julia", "Female"));
  
        // if the student with given rollnumber exists,
        // then "search" function returns the record
        // else returns null
          
        Student student = search(catalogue, 18);
        printInformation(18, student);
  
        // delete student record with roll number 36
        delete(catalogue, 13);
        
        student = search(catalogue, 13);
        
        // This will print "No student found" as we deleted
        // the record
        printInformation(13, student);
    }
  
    // Insert function to add student in the catalogue
    public static void insert(Student[] catalogue,
                              Student student)
    {
        catalogue[student.rollNumber] = student;
    }
  
    // Search function to get the record of student from the
    // catalogue
    public static Student search(Student[] catalogue,
                                 int rollNumber)
    {
        return catalogue[rollNumber];
    }
  
    // Delete function to remove the record of student from
    // the catalogue
    public static void delete(Student[] catalogue,
                              int rollNumber)
    {
        // As we are using arrays, we just will this
        // location to point to null
        catalogue[rollNumber] = null;
    }
  
    // Function to print student's information
    public static void printInformation(int rollNumber,
                                             Student student)
    {
        // print student information if record exists
        if (student != null)
            System.out.println( "Student with roll number " + rollNumber
                + " - Name: " + student.name
                + ", Gender: " + student.gender);
        else
            System.out.println( "No student found with roll number "
                + rollNumber);
    }
}

Student with roll number 18 - Name: Joe, Gender: Male
No student found with roll number 13