Repository: TheAlgorithms/Java
Pull request #5426 (2024-08-28 20:06:16)

refactor: `HashMap`
Class cleanup.
Readability improvements.
Added tests.

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5426?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `88.52459%` with `7 lines` in your changes missing coverage. Please review.
> Project coverage is 50.46%. Comparing base [(`203d544`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/203d54466897201b9d832afec5f4120f6d6dcbcd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`6324d48`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/6324d489257f885478387aa1103c6a7e492a93b1?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5426?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...rithms/datastructures/hashmap/hashing/HashMap.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5426?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fhashmap%2Fhashing%2FHashMap.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9oYXNobWFwL2hhc2hpbmcvSGFzaE1hcC5qYXZh) | 88.52% | [1 Missing and 6 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5426?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5426      +/-   ##
============================================
+ Coverage     49.97%   50.46%   +0.49%     
- Complexity     3108     3118      +10     
============================================
  Files           524      523       -1     
  Lines         15166    15149      -17     
  Branches       2884     2886       +2     
============================================
+ Hits           7579     7645      +66     
+ Misses         7271     7182      -89     
- Partials        316      322       +6     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5426?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java
index e0b394b1..1aae122b 100644
--- a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java
@@ -1,146 +1,275 @@
 package com.thealgorithms.datastructures.hashmap.hashing;
 
-public class HashMap {
+/**
+ * A generic HashMap implementation that uses separate chaining with linked lists
+ * to handle collisions. The class supports basic operations such as insert, delete,
+ * and search, as well as displaying the contents of the hash map.
+ *
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
+ */
+public class HashMap<K, V> {
+    private final int hashSize;
+    private final LinkedList<K, V>[] buckets;
 
-    private final int hsize;
-    private final LinkedList[] buckets;
-
-    public HashMap(int hsize) {
-        buckets = new LinkedList[hsize];
-        for (int i = 0; i < hsize; i++) {
-            buckets[i] = new LinkedList();
-            // Java requires explicit initialization of each object
+    /**
+     * Constructs a HashMap with the specified hash size.
+     *
+     * @param hashSize the number of buckets in the hash map
+     */
+    @SuppressWarnings("unchecked")
+    public HashMap(int hashSize) {
+        this.hashSize = hashSize;
+        // Safe to suppress warning because we are creating an array of generic type
+        this.buckets = new LinkedList[hashSize];
+        for (int i = 0; i < hashSize; i++) {
+            buckets[i] = new LinkedList<>();
         }
-        this.hsize = hsize;
     }
 
-    public int hashing(int key) {
-        int hash = key % hsize;
-        if (hash < 0) {
-            hash += hsize;
+    /**
+     * Computes the hash code for the specified key.
+     * Null keys are hashed to bucket 0.
+     *
+     * @param key the key for which the hash code is to be computed
+     * @return the hash code corresponding to the key
+     */
+    private int computeHash(K key) {
+        if (key == null) {
+            return 0; // Use a special bucket (e.g., bucket 0) for null keys
         }
-        return hash;
+        int hash = key.hashCode() % hashSize;
+        return hash < 0 ? hash + hashSize : hash;
     }
 
-    public void insertHash(int key) {
-        int hash = hashing(key);
-        buckets[hash].insert(key);
+    /**
+     * Inserts the specified key-value pair into the hash map.
+     * If the key already exists, the value is updated.
+     *
+     * @param key   the key to be inserted
+     * @param value the value to be associated with the key
+     */
+    public void insert(K key, V value) {
+        int hash = computeHash(key);
+        buckets[hash].insert(key, value);
     }
 
-    public void deleteHash(int key) {
-        int hash = hashing(key);
-
+    /**
+     * Deletes the key-value pair associated with the specified key from the hash map.
+     *
+     * @param key the key whose key-value pair is to be deleted
+     */
+    public void delete(K key) {
+        int hash = computeHash(key);
         buckets[hash].delete(key);
     }
 
-    public void displayHashtable() {
-        for (int i = 0; i < hsize; i++) {
-            System.out.printf("Bucket %d :", i);
-            System.out.println(buckets[i].display());
-        }
+    /**
+     * Searches for the value associated with the specified key in the hash map.
+     *
+     * @param key the key whose associated value is to be returned
+     * @return the value associated with the specified key, or null if the key does not exist
+     */
+    public V search(K key) {
+        int hash = computeHash(key);
+        Node<K, V> node = buckets[hash].findKey(key);
+        return node != null ? node.getValue() : null;
     }
 
-    public static class LinkedList {
-
-        private Node first;
-
-        public LinkedList() {
-            first = null;
+    /**
+     * Displays the contents of the hash map, showing each bucket and its key-value pairs.
+     */
+    public void display() {
+        for (int i = 0; i < hashSize; i++) {
+            System.out.printf("Bucket %d: %s%n", i, buckets[i].display());
         }
+    }
 
-        public void insert(int key) {
-            if (isEmpty()) {
-                first = new Node(key);
-                return;
-            }
+    /**
+     * A nested static class that represents a linked list used for separate chaining in the hash map.
+     *
+     * @param <K> the type of keys maintained by this linked list
+     * @param <V> the type of mapped values
+     */
+    public static class LinkedList<K, V> {
+        private Node<K, V> head;
 
-            Node temp = findEnd(first);
-            temp.setNext(new Node(key));
+        /**
+         * Inserts the specified key-value pair into the linked list.
+         * If the linked list is empty, the pair becomes the head.
+         * Otherwise, the pair is added to the end of the list.
+         *
+         * @param key   the key to be inserted
+         * @param value the value to be associated with the key
+         */
+        public void insert(K key, V value) {
+            Node<K, V> existingNode = findKey(key);
+            if (existingNode != null) {
+                existingNode.setValue(value); // Update the value, even if it's null
+            } else {
+                if (isEmpty()) {
+                    head = new Node<>(key, value);
+                } else {
+                    Node<K, V> temp = findEnd(head);
+                    temp.setNext(new Node<>(key, value));
+                }
+            }
         }
 
-        private Node findEnd(Node n) {
-            while (n.getNext() != null) {
-                n = n.getNext();
+        /**
+         * Finds the last node in the linked list.
+         *
+         * @param node the starting node
+         * @return the last node in the linked list
+         */
+        private Node<K, V> findEnd(Node<K, V> node) {
+            while (node.getNext() != null) {
+                node = node.getNext();
             }
-            return n;
+            return node;
         }
 
-        public Node findKey(int key) {
-            if (!isEmpty()) {
-                Node temp = first;
-                if (temp.getKey() == key) {
+        /**
+         * Finds the node associated with the specified key in the linked list.
+         *
+         * @param key the key to search for
+         * @return the node associated with the specified key, or null if not found
+         */
+        public Node<K, V> findKey(K key) {
+            Node<K, V> temp = head;
+            while (temp != null) {
+                if ((key == null && temp.getKey() == null) || (temp.getKey() != null && temp.getKey().equals(key))) {
                     return temp;
                 }
-
-                while ((temp = temp.getNext()) != null) {
-                    if (temp.getKey() == key) {
-                        return temp;
-                    }
-                }
+                temp = temp.getNext();
             }
             return null;
         }
 
-        public void delete(int key) {
-            if (!isEmpty()) {
-                if (first.getKey() == key) {
-                    Node next = first.next;
-                    first.next = null; // help GC
-                    first = next;
-                } else {
-                    delete(first, key);
-                }
+        /**
+         * Deletes the node associated with the specified key from the linked list.
+         * Handles the case where the key could be null.
+         *
+         * @param key the key whose associated node is to be deleted
+         */
+        public void delete(K key) {
+            if (isEmpty()) {
+                return;
             }
-        }
 
-        private void delete(Node n, int key) {
-            if (n.getNext().getKey() == key) {
-                if (n.getNext().getNext() == null) {
-                    n.setNext(null);
-                } else {
-                    n.setNext(n.getNext().getNext());
+            // Handle the case where the head node has the key to delete
+            if ((key == null && head.getKey() == null) || (head.getKey() != null && head.getKey().equals(key))) {
+                head = head.getNext();
+                return;
+            }
+
+            // Traverse the list to find and delete the node
+            Node<K, V> current = head;
+            while (current.getNext() != null) {
+                if ((key == null && current.getNext().getKey() == null) || (current.getNext().getKey() != null && current.getNext().getKey().equals(key))) {
+                    current.setNext(current.getNext().getNext());
+                    return;
                 }
-            } else {
-                delete(n.getNext(), key);
+                current = current.getNext();
             }
         }
 
+        /**
+         * Displays the contents of the linked list as a string.
+         *
+         * @return a string representation of the linked list
+         */
         public String display() {
-            return display(first);
+            return display(head);
         }
 
-        private String display(Node n) {
-            if (n == null) {
-                return "null";
-            } else {
-                return n.getKey() + "->" + display(n.getNext());
+        /**
+         * Constructs a string representation of the linked list non-recursively.
+         *
+         * @param node the starting node
+         * @return a string representation of the linked list starting from the given node
+         */
+        private String display(Node<K, V> node) {
+            StringBuilder sb = new StringBuilder();
+            while (node != null) {
+                sb.append(node.getKey()).append("=").append(node.getValue());
+                node = node.getNext();
+                if (node != null) {
+                    sb.append(" -> ");
+                }
             }
+            return sb.toString().isEmpty() ? "null" : sb.toString();
         }
 
+        /**
+         * Checks if the linked list is empty.
+         *
+         * @return true if the linked list is empty, false otherwise
+         */
         public boolean isEmpty() {
-            return first == null;
+            return head == null;
         }
     }
 
-    public static class Node {
+    /**
+     * A nested static class representing a node in the linked list.
+     *
+     * @param <K> the type of key maintained by this node
+     * @param <V> the type of value maintained by this node
+     */
+    public static class Node<K, V> {
+        private final K key;
+        private V value;
+        private Node<K, V> next;
 
-        private Node next;
-        private final int key;
-
-        public Node(int key) {
-            next = null;
+        /**
+         * Constructs a Node with the specified key and value.
+         *
+         * @param key   the key associated with this node
+         * @param value the value associated with this node
+         */
+        public Node(K key, V value) {
             this.key = key;
+            this.value = value;
         }
 
-        public Node getNext() {
-            return next;
+        /**
+         * Gets the key associated with this node.
+         *
+         * @return the key associated with this node
+         */
+        public K getKey() {
+            return key;
         }
 
-        public int getKey() {
-            return key;
+        /**
+         * Gets the value associated with this node.
+         *
+         * @return the value associated with this node
+         */
+        public V getValue() {
+            return value;
+        }
+
+        public void setValue(V value) { // This method allows updating the value
+            this.value = value;
+        }
+
+        /**
+         * Gets the next node in the linked list.
+         *
+         * @return the next node in the linked list
+         */
+        public Node<K, V> getNext() {
+            return next;
         }
 
-        public void setNext(Node next) {
+        /**
+         * Sets the next node in the linked list.
+         *
+         * @param next the next node to be linked
+         */
+        public void setNext(Node<K, V> next) {
             this.next = next;
         }
     }
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Main.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Main.java
deleted file mode 100644
index 4d9b33b1..00000000
--- a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Main.java
+++ /dev/null
@@ -1,52 +0,0 @@
-package com.thealgorithms.datastructures.hashmap.hashing;
-
-import java.util.Scanner;
-
-public final class Main {
-    private Main() {
-    }
-
-    public static void main(String[] args) {
-        int choice;
-        int key;
-
-        HashMap h = new HashMap(7);
-        Scanner scan = new Scanner(System.in);
-
-        while (true) {
-            System.out.println("Enter your Choice :");
-            System.out.println("1. Add Key");
-            System.out.println("2. Delete Key");
-            System.out.println("3. Print Table");
-            System.out.println("4. Exit");
-
-            choice = scan.nextInt();
-
-            switch (choice) {
-            case 1:
-                System.out.println("Enter the Key: ");
-                key = scan.nextInt();
-                h.insertHash(key);
-                break;
-
-            case 2:
-                System.out.println("Enter the Key delete:  ");
-                key = scan.nextInt();
-                h.deleteHash(key);
-                break;
-
-            case 3:
-                System.out.println("Print table");
-                h.displayHashtable();
-                break;
-
-            case 4:
-                scan.close();
-                return;
-
-            default:
-                throw new IllegalArgumentException("Unexpected value: " + choice);
-            }
-        }
-    }
-}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapTest.java b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapTest.java
new file mode 100644
index 00000000..3552bc1a
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapTest.java
@@ -0,0 +1,146 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import org.junit.jupiter.api.Test;
+
+public class HashMapTest {
+
+    @Test
+    public void testInsertAndSearch() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(15, "Value15");
+        hashMap.insert(25, "Value25");
+        hashMap.insert(35, "Value35");
+
+        assertEquals("Value15", hashMap.search(15));
+        assertEquals("Value25", hashMap.search(25));
+        assertEquals("Value35", hashMap.search(35));
+        assertNull(hashMap.search(45));
+    }
+
+    @Test
+    public void testDelete() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(15, "Value15");
+        hashMap.insert(25, "Value25");
+        hashMap.insert(35, "Value35");
+
+        assertEquals("Value25", hashMap.search(25));
+        hashMap.delete(25);
+        assertNull(hashMap.search(25));
+    }
+
+    @Test
+    public void testDisplay() {
+        HashMap<Integer, String> hashMap = new HashMap<>(5);
+        hashMap.insert(15, "Value15");
+        hashMap.insert(25, "Value25");
+        hashMap.insert(35, "Value35");
+        hashMap.display();
+    }
+
+    @Test
+    public void testInsertNullKey() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(null, "NullValue");
+        assertEquals("NullValue", hashMap.search(null));
+    }
+
+    @Test
+    public void testInsertNullValue() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(15, null);
+        assertNull(hashMap.search(15));
+    }
+
+    @Test
+    public void testUpdateExistingKey() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(15, "Value15");
+        hashMap.insert(15, "UpdatedValue15");
+
+        assertEquals("UpdatedValue15", hashMap.search(15));
+    }
+
+    @Test
+    public void testHandleCollisions() {
+        HashMap<Integer, String> hashMap = new HashMap<>(3);
+        // These keys should collide if the hash function is modulo 3
+        hashMap.insert(1, "Value1");
+        hashMap.insert(4, "Value4");
+        hashMap.insert(7, "Value7");
+
+        assertEquals("Value1", hashMap.search(1));
+        assertEquals("Value4", hashMap.search(4));
+        assertEquals("Value7", hashMap.search(7));
+    }
+
+    @Test
+    public void testSearchInEmptyHashMap() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        assertNull(hashMap.search(10));
+    }
+
+    @Test
+    public void testDeleteNonExistentKey() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        hashMap.insert(15, "Value15");
+        hashMap.delete(25);
+
+        assertEquals("Value15", hashMap.search(15));
+        assertNull(hashMap.search(25));
+    }
+
+    @Test
+    public void testInsertLargeNumberOfElements() {
+        HashMap<Integer, String> hashMap = new HashMap<>(10);
+        for (int i = 0; i < 100; i++) {
+            hashMap.insert(i, "Value" + i);
+        }
+
+        for (int i = 0; i < 100; i++) {
+            assertEquals("Value" + i, hashMap.search(i));
+        }
+    }
+
+    @Test
+    public void testDeleteHeadOfBucket() {
+        HashMap<Integer, String> hashMap = new HashMap<>(3);
+        hashMap.insert(1, "Value1");
+        hashMap.insert(4, "Value4");
+        hashMap.insert(7, "Value7");
+
+        hashMap.delete(1);
+        assertNull(hashMap.search(1));
+        assertEquals("Value4", hashMap.search(4));
+        assertEquals("Value7", hashMap.search(7));
+    }
+
+    @Test
+    public void testDeleteTailOfBucket() {
+        HashMap<Integer, String> hashMap = new HashMap<>(3);
+        hashMap.insert(1, "Value1");
+        hashMap.insert(4, "Value4");
+        hashMap.insert(7, "Value7");
+
+        hashMap.delete(7);
+        assertNull(hashMap.search(7));
+        assertEquals("Value1", hashMap.search(1));
+        assertEquals("Value4", hashMap.search(4));
+    }
+
+    @Test
+    public void testDeleteMiddleElementOfBucket() {
+        HashMap<Integer, String> hashMap = new HashMap<>(3);
+        hashMap.insert(1, "Value1");
+        hashMap.insert(4, "Value4");
+        hashMap.insert(7, "Value7");
+
+        hashMap.delete(4);
+        assertNull(hashMap.search(4));
+        assertEquals("Value1", hashMap.search(1));
+        assertEquals("Value7", hashMap.search(7));
+    }
+}