Add HashTable class and demonstration in Main

Lord-of-Algorithms · Lord-of-Algorithms · commit dfe1b6204591 · 2024-03-11T20:54:59.000+02:00
diff --git a/src/hashtable/HashFunctionType.java b/src/hashtable/HashFunctionType.java
@@ -0,0 +1,6 @@
+package hashtable;
+
+public enum HashFunctionType {
+    Division,
+    Multiplication
+}
diff --git a/src/hashtable/HashTable.java b/src/hashtable/HashTable.java
@@ -0,0 +1,259 @@
+package hashtable;
+
+/**
+ * A hash table implementation using chaining with linked lists to resolve collisions.
+ * This class provides methods for inserting, retrieving, and removing key-value pairs,
+ * where keys are strings and values are double precision numbers.
+ */
+public class HashTable {
+
+    private HashTableBucket[] bucketArray;
+    private int size; // Number of key-value pairs in the hash table
+    private HashFunctionType hashFunctionType;
+    private static final double A = (Math.sqrt(5) - 1) / 2; // Constant for Multiplication Method
+
+    private static final double MAX_LOAD_FACTOR = 0.75;
+
+    public HashTable(int capacity, HashFunctionType hashFunctionType) {
+        if (capacity < 1) {
+            throw new IllegalArgumentException("Initial capacity must be >= 1");
+        }
+        // Adjust capacity to the next prime number if it's not already prime
+        capacity = isPrime(capacity) ? capacity : nextPrime(capacity);
+        bucketArray = new HashTableBucket[capacity];
+        this.hashFunctionType = hashFunctionType;
+    }
+
+    // Computes the hash value for a given key
+    private int hash(String key) {
+        int hashCode = key.hashCode();
+
+        switch (hashFunctionType) {
+            case Division:
+                return Math.abs(hashCode) % bucketArray.length;
+
+            case Multiplication:
+                double fractionalPart = (Math.abs(hashCode) * A) % 1;
+                return (int) Math.floor(bucketArray.length * fractionalPart);
+
+            default:
+                throw new IllegalStateException("Unknown Hash Function Type");
+        }
+    }
+
+    /**
+     * Inserts or updates a key-value pair in the hash table.
+     *
+     * @param key   the key to insert or update
+     * @param value the value associated with the key
+     */
+    public void put(String key, double value) {
+        // Compute the index for this key using the hash function
+        int index = hash(key);
+        if (bucketArray[index] == null) {
+            bucketArray[index] = new HashTableBucket();
+        }
+
+        HashTableBucket bucket = bucketArray[index];
+        HashTableEntry existingEntry = bucket.find(key);
+        if (existingEntry != null) {
+            // Key found, update value
+            existingEntry.value = value;
+        } else {
+            // Check if adding a new entry would exceed the load factor and trigger rehashing if necessary
+            if ((double) (size + 1) / bucketArray.length >= MAX_LOAD_FACTOR) {
+                rehash();
+
+                // Recompute the index since the bucketArray length has changed after rehashing
+                index = hash(key);
+                if (bucketArray[index] == null) {
+                    bucketArray[index] = new HashTableBucket();
+                }
+                bucket = bucketArray[index];
+            }
+
+            bucket.insertAtBeginning(key, value);
+            size++;
+        }
+    }
+
+    // Doubles the size of the hash table and rehashes all existing entries
+    private void rehash() {
+        HashTableBucket[] oldTable = bucketArray;
+        int newCapacity = nextPrime(oldTable.length * 2); // Find the next prime number greater than double the current length
+        bucketArray = new HashTableBucket[newCapacity];
+        size = 0;
+        for (HashTableBucket bucket : oldTable) {
+            if (bucket != null) {
+                HashTableEntry current = bucket.head;
+                while (current != null) {
+                    // Re-add each entry to the new table
+                    put(current.key, current.value);
+                    current = current.next;
+                }
+            }
+        }
+    }
+
+    // Utility method to find the next prime number greater than a given number
+    private int nextPrime(int start) {
+        for (int n = start; true; n++) {
+            if (isPrime(n)) {
+                return n;
+            }
+        }
+    }
+
+    // Utility method to check if a number is prime
+    private boolean isPrime(int number) {
+        if (number <= 1) {
+            return false;
+        }
+        for (int i = 2; i * i <= number; i++) {
+            if (number % i == 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Retrieves the value associated with a given key.
+     *
+     * @param key the key whose value is to be retrieved
+     * @return the value associated with the key, or null if the key is not found
+     */
+    public Double get(String key) {
+        int index = hash(key);
+        HashTableBucket bucket = bucketArray[index];
+        if (bucket == null) {
+            return null;
+        }
+        HashTableEntry entry = bucket.find(key);
+        return entry != null ? entry.value : null; // Return value if key found, otherwise null
+    }
+
+    /**
+     * Removes a key-value pair from the hash table.
+     *
+     * @param key the key of the pair to be removed
+     * @return true if the pair was successfully removed, false if the key was not found
+     */
+    public boolean remove(String key) {
+        int index = hash(key);
+        if (bucketArray[index] == null) {
+            return false; // No list exists at this index, so the key is not in the table
+        }
+
+        HashTableBucket bucket = bucketArray[index];
+        if (bucket.delete(key)) {
+            size--;
+            return true;
+        }
+        return false;
+    }
+
+    // Returns the number of key-value pairs in the hash table
+    public int size() {
+        return size;
+    }
+
+    /**
+     * Prints the entire contents of the hash table.
+     */
+    public void print() {
+        for (int i = 0; i < bucketArray.length; i++) {
+            System.out.print("[" + i + "]");
+            HashTableBucket bucket = bucketArray[i];
+            if (bucket != null) {
+                bucket.print();
+            }
+            System.out.println();
+        }
+    }
+
+    /**
+     * HashTableBucket class represents the linked list used in chaining
+     */
+    private static class HashTableBucket {
+        HashTableEntry head; // Head of the linked list
+
+        // Inserts a new entry at the beginning of the list
+        void insertAtBeginning(String key, double value) {
+            HashTableEntry newEntry = new HashTableEntry(key, value);
+            newEntry.next = head;
+            head = newEntry;
+        }
+
+        /**
+         * Deletes an entry with the specified key from the list.
+         *
+         * @param key The key of the entry to be deleted.
+         * @return true if the entry was found and successfully deleted, false otherwise.
+         */
+        boolean delete(String key) {
+            HashTableEntry current = head;
+            HashTableEntry prev = null;
+
+            while (current != null) {
+                if (current.key.equals(key)) {
+                    // Key found, delete the entry
+                    if (prev == null) {
+                        head = current.next; // Deleting the first entry
+                    } else {
+                        prev.next = current.next; // Deleting a subsequent entry
+                    }
+                    return true; // Entry successfully deleted
+                }
+                prev = current;
+                current = current.next;
+            }
+
+            return false; // Key not found
+        }
+
+        // Finds an entry by key in the list
+        HashTableEntry find(String key) {
+            HashTableEntry current = head;
+            while (current != null) {
+                if (current.key.equals(key)) {
+                    return current;
+                }
+                current = current.next;
+            }
+            return null; // Return null if key not found
+        }
+
+        /**
+         * Prints all the entries in this hash table bucket.
+         */
+        void print() {
+            HashTableEntry current = head;
+            while (current != null) {
+                current.print();
+                current = current.next;
+            }
+        }
+    }
+
+    /**
+     * HashTableEntry class represents a key-value pair in the hash table
+     */
+    private static class HashTableEntry {
+        String key;
+        double value;
+        HashTableEntry next; // Reference to the next entry (node) in the linked list
+
+        HashTableEntry(String key, double value) {
+            this.key = key;
+            this.value = value;
+        }
+
+        /**
+         * Prints the key-value pair represented by this entry.
+         */
+        void print() {
+            System.out.print("->|" + key + ", " + value + "|");
+        }
+    }
+}
diff --git a/src/hashtable/HashTableMain.java b/src/hashtable/HashTableMain.java
@@ -0,0 +1,50 @@
+package hashtable;
+
+public class HashTableMain {
+    /**
+     * Demonstrates the usage of the HashTable class, including key operations
+     * such as insertion, retrieval, removal, and automatic rehashing.
+     */
+    public static void main(String[] args) {
+        // Initialize the hash table with a small capacity of 5 for demonstration purposes.
+        // This small initial capacity is chosen to illustrate how rehashing operates
+        // when the hash table becomes full. In a practical application, especially for a dataset
+        // like the chemical elements with a well-defined and relatively small set of items (118 confirmed elements),
+        // an initial capacity between 150 and 200 could be more appropriate.
+        // This provides ample space for all elements and minimizes the need for rehashing, enhancing performance.
+        HashTable hashTable = new HashTable(5, HashFunctionType.Division);
+
+        // Insert key-value pairs into the hash table
+        hashTable.put("Hydrogen", 1.008);
+        hashTable.put("Helium", 4.0026);
+        hashTable.put("Lithium", 6.94);
+
+        // Print the hash table's contents
+        System.out.println("Initial Hash Table:");
+        hashTable.print();
+
+        // Retrieve and print a specific value
+        Double heliumWeight = hashTable.get("Helium");
+        System.out.println("\nAtomic weight of Helium: " + heliumWeight);
+
+        // Update an existing key with a new value and print the hash table
+        hashTable.put("Helium", 4.002602);
+        System.out.println("\nAfter updating Helium's atomic weight:");
+        hashTable.print();
+
+        // Remove an entry and print the hash table
+        hashTable.remove("Lithium");
+        System.out.println("\nAfter removing Lithium:");
+        hashTable.print();
+
+        // Insert more entries to trigger rehashing
+        hashTable.put("Beryllium", 9.0122);
+        hashTable.put("Boron", 10.81);
+        hashTable.put("Carbon", 12.011);
+        hashTable.put("Nitrogen", 14.007);
+        hashTable.put("Oxygen", 15.999);
+
+        System.out.println("\nAfter adding more elements and triggering rehashing:");
+        hashTable.print();
+    }
+}
