Programa Java para implementar el enstringmiento de tablas hash con listas doblemente enlazadas

Las tablas hash (similares a las tablas en general) proporcionan un subconjunto de las operaciones de conjuntos dinámicos. Por lo general, un conjunto de claves se asignan con algunos valores en función de ciertas relaciones. Sin embargo, puede haber situaciones en las que diferentes teclas se asignen a la misma posición proporcionada por la función Hash, lo que conduce a una colisión.

Una de las formas de superar esta situación es Hash Table Chaining

El enfoque de enstringmiento para resolver colisiones se ocupa de ello avanzando y colocando todas las claves que se asignan a una ranura en esa ranura pero representándolas como una lista enlazada.

El enstringmiento de tablas hash en Java es posible tanto con la lista de enlaces individuales como con la lista de enlaces dobles . Aunque la implementación es la misma, la única diferencia es que la lista doblemente enlazada permite el recorrido bidireccional, es decir, el Node contiene un puntero al siguiente Node así como al anterior. Por lo tanto, la complejidad de la inserción y eliminación en una posición conocida se reduce a O(1) en comparación con la Lista de enlace simple (O(n)).

Ejemplo :

In Singly Linked List : g -> e -> e -> k -> s
Here, each node contains a pointer to the next node only.

In Doubly Linked List : g <-> e <-> e <-> k <-> s
Each node contains pointer to the next as well as previous node.

Acercarse :

  1. Inserción: para insertar, simplemente se aplica hash a una clave para obtener la posición en la tabla (la lista en la que se debe insertar esta nueva clave), y luego se inserta la clave en el encabezado de la lista doblemente enlazada utilizando los procedimientos de lista enlazada estándar ( dado en el código).
  2. Eliminación: solo revise la lista a la que se asigna la clave a través de la función hash y elimine la clave de esa lista utilizando los procedimientos de lista enlazada estándar (que se proporcionan en el código).

A continuación se muestra la implementación del enfoque anterior:

Java

// Java implementation of Hashtable chaining
// using doubly linked list
  
import java.util.*;
  
class DoublyLinkedListNode {
    // Declaration of Nodes
    DoublyLinkedListNode next, prev;
    int data;
  
    // constructor
    DoublyLinkedListNode(int data)
    {
        this.data = data;
        next = null;
        prev = null;
    }
}
class HashTableChainingDoublyLinkedList {
    // Declaration of Hash Table
    DoublyLinkedListNode[] hashTable;
  
    // stores the size of HashTable
    int size;
  
    // Constructor
    HashTableChainingDoublyLinkedList(int hashTableSize)
    {
        // Creating an empty Hash Table
        hashTable = new DoublyLinkedListNode[hashTableSize];
        size = 0;
    }
  
    // Function to check if hash table is empty
    public boolean isEmpty() { return size == 0; }
  
    // Function to clear/delete all elements from Hash table
    public void clear()
    {
        // Capacity of Hash Table
        int len = hashTable.length;
  
        // Creating new empty Hash Table
        // of same initial capacity
        hashTable = new DoublyLinkedListNode[len];
        size = 0;
    }
  
    // Function that returns size of Hash Table
    public int getSize() { return size; }
  
    // Function to insert a value/element
    public void insert(int value)
    {
        size++;
  
        // gets the position/index where the value should be
        // stored
        int position = hash(value);
  
        // creates a node for storing value
        DoublyLinkedListNode node
            = new DoublyLinkedListNode(value);
  
        DoublyLinkedListNode start = hashTable[position];
  
        if (hashTable[position] == null)
            hashTable[position] = node;
        else {
            node.next = start;
            start.prev = node;
            hashTable[position] = node;
        }
    }
  
    // Function to remove an element
    public void remove(int value)
    {
        try {
            // gets the position where the value to
            // be deleted exists
            int position = hash(value);
  
            DoublyLinkedListNode start
                = hashTable[position];
  
            DoublyLinkedListNode end = start;
  
            // if value is found at start
            if (start.data == value) {
                size--;
                if (start.next == null) {
                    // removing the value
                    hashTable[position] = null;
                    return;
                }
  
                start = start.next;
                start.prev = null;
                hashTable[position] = start;
  
                return;
            }
  
            // traversing the list
            // until the value is found
            while (end.next != null
                   && end.next.data != value)
                end = end.next;
  
            // if reached at the end without finding the
            // value
            if (end.next == null) {
                System.out.println("\nElement not found\n");
                return;
            }
  
            size--;
  
            if (end.next.next == null) {
                end.next = null;
                return;
            }
  
            end.next.next.prev = end;
            end.next = end.next.next;
  
            hashTable[position] = start;
        }
        catch (Exception e) {
            System.out.println("\nElement not found\n");
        }
    }
  
    // Definition of Hash function
    private int hash(Integer x)
    {
        int hashValue = x.hashCode();
  
        hashValue %= hashTable.length;
  
        if (hashValue < 0)
            hashValue += hashTable.length;
  
        return hashValue;
    }
  
    // Function to print hash table
    public void printHashTable()
    {
        System.out.println();
        for (int i = 0; i < hashTable.length; i++) {
            System.out.print("At " + i + ":  ");
  
            DoublyLinkedListNode start = hashTable[i];
  
            while (start != null) {
                System.out.print(start.data + " ");
                start = start.next;
            }
  
            System.out.println();
        }
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        HashTableChainingDoublyLinkedList hashTab
            = new HashTableChainingDoublyLinkedList(5);
  
        hashTab.insert(99);
        hashTab.insert(23);
        hashTab.insert(36);
        hashTab.insert(47);
        hashTab.insert(80);
  
        hashTab.printHashTable();
  
        hashTab.insert(92);
        hashTab.insert(49);
  
        hashTab.printHashTable();
  
        hashTab.remove(99);
  
        hashTab.printHashTable();
  
        hashTab.clear();
  
        hashTab.printHashTable();
  
        System.out.println(hashTab.isEmpty());
    }
}
Producción

At 0:  80 
At 1:  36 
At 2:  47 
At 3:  23 
At 4:  99 

At 0:  80 
At 1:  36 
At 2:  92 47 
At 3:  23 
At 4:  49 99 

At 0:  80 
At 1:  36 
At 2:  92 47 
At 3:  23 
At 4:  49 

At 0:  
At 1:  
At 2:  
At 3:  
At 4:  
true

 

Publicación traducida automáticamente

Artículo escrito por vanshitatwr620 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *