Repository: TheAlgorithms/Java
Pull request #5973 (2024-10-24 05:59:05)

refactor: Enhance docs, fix & add tests in `GenericHashMapUsingArrayL…
…ist`

<!--
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/5973?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 `90.00000%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 68.15%. Comparing base [(`5246f63`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/5246f635797194f5f0d7ac93af61099a5764fa4f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`62a236c`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/62a236c5bcfdece2231d268c0b6aad34491aeac8?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/5973?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [.../hashmap/hashing/GenericHashMapUsingArrayList.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5973?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fhashmap%2Fhashing%2FGenericHashMapUsingArrayList.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9oYXNobWFwL2hhc2hpbmcvR2VuZXJpY0hhc2hNYXBVc2luZ0FycmF5TGlzdC5qYXZh) | 90.00% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5973?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    #5973      +/-   ##
============================================
+ Coverage     67.98%   68.15%   +0.17%     
- Complexity     4586     4598      +12     
============================================
  Files           620      620              
  Lines         17116    17119       +3     
  Branches       3305     3307       +2     
============================================
+ Hits          11636    11668      +32     
+ Misses         5035     5007      -28     
+ Partials        445      444       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5973?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/GenericHashMapUsingArrayList.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayList.java
index a1ef457f..89e25f4e 100644
--- a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayList.java
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayList.java
@@ -3,12 +3,34 @@ package com.thealgorithms.datastructures.hashmap.hashing;
 import java.util.ArrayList;
 import java.util.LinkedList;
 
+/**
+ * A generic implementation of a hash map using an array list of linked lists for collision resolution.
+ * This class allows storage of key-value pairs with average-case constant time complexity for insertion,
+ * deletion, and retrieval operations.
+ *
+ * <p>
+ * The hash map uses separate chaining to handle collisions. Each bucket in the hash map is represented
+ * by a linked list that holds nodes containing key-value pairs. When multiple keys hash to the same index,
+ * they are stored in the same linked list.
+ * </p>
+ *
+ * <p>
+ * The hash map automatically resizes itself when the load factor exceeds 0.5. The load factor is defined
+ * as the ratio of the number of entries to the number of buckets. When resizing occurs, all existing entries
+ * are rehashed and inserted into the new buckets.
+ * </p>
+ *
+ * @param <K> the type of keys maintained by this hash map
+ * @param <V> the type of mapped values
+ */
 public class GenericHashMapUsingArrayList<K, V> {
 
-    ArrayList<LinkedList<Node>> buckets;
-    private float lf = 0.5f;
-    private int size;
+    private ArrayList<LinkedList<Node>> buckets; // Array list of buckets (linked lists)
+    private int size; // Number of key-value pairs in the hash map
 
+    /**
+     * Constructs a new empty hash map with an initial capacity of 10 buckets.
+     */
     public GenericHashMapUsingArrayList() {
         buckets = new ArrayList<>();
         for (int i = 0; i < 10; i++) {
@@ -17,6 +39,13 @@ public class GenericHashMapUsingArrayList<K, V> {
         size = 0;
     }
 
+    /**
+     * Associates the specified value with the specified key in this map.
+     * If the map previously contained a mapping for the key, the old value is replaced.
+     *
+     * @param key the key with which the specified value is to be associated
+     * @param value the value to be associated with the specified key
+     */
     public void put(K key, V value) {
         int hash = Math.abs(key.hashCode() % buckets.size());
         LinkedList<Node> nodes = buckets.get(hash);
@@ -31,25 +60,36 @@ public class GenericHashMapUsingArrayList<K, V> {
         nodes.add(new Node(key, value));
         size++;
 
-        if ((float) size / buckets.size() > lf) {
+        // Load factor threshold for resizing
+        float loadFactorThreshold = 0.5f;
+        if ((float) size / buckets.size() > loadFactorThreshold) {
             reHash();
         }
     }
 
+    /**
+     * Resizes the hash map by doubling the number of buckets and rehashing existing entries.
+     */
     private void reHash() {
-        ArrayList<LinkedList<Node>> old = buckets;
+        ArrayList<LinkedList<Node>> oldBuckets = buckets;
         buckets = new ArrayList<>();
         size = 0;
-        for (int i = 0; i < old.size() * 2; i++) {
+        for (int i = 0; i < oldBuckets.size() * 2; i++) {
             buckets.add(new LinkedList<>());
         }
-        for (LinkedList<Node> nodes : buckets) {
+        for (LinkedList<Node> nodes : oldBuckets) {
             for (Node node : nodes) {
                 put(node.key, node.val);
             }
         }
     }
 
+    /**
+     * Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
+     *
+     * @param key the key whose associated value is to be returned
+     * @return the value associated with the specified key, or null if no mapping exists
+     */
     public V get(K key) {
         int hash = Math.abs(key.hashCode() % buckets.size());
         LinkedList<Node> nodes = buckets.get(hash);
@@ -61,6 +101,11 @@ public class GenericHashMapUsingArrayList<K, V> {
         return null;
     }
 
+    /**
+     * Removes the mapping for the specified key from this map if present.
+     *
+     * @param key the key whose mapping is to be removed from the map
+     */
     public void remove(K key) {
         int hash = Math.abs(key.hashCode() % buckets.size());
         LinkedList<Node> nodes = buckets.get(hash);
@@ -72,18 +117,36 @@ public class GenericHashMapUsingArrayList<K, V> {
                 break;
             }
         }
-        nodes.remove(target);
-        size--;
+        if (target != null) {
+            nodes.remove(target);
+            size--;
+        }
     }
 
+    /**
+     * Returns true if this map contains a mapping for the specified key.
+     *
+     * @param key the key whose presence in this map is to be tested
+     * @return true if this map contains a mapping for the specified key
+     */
     public boolean containsKey(K key) {
         return get(key) != null;
     }
 
+    /**
+     * Returns the number of key-value pairs in this map.
+     *
+     * @return the number of key-value pairs
+     */
     public int size() {
         return this.size;
     }
 
+    /**
+     * Returns a string representation of the map, containing all key-value pairs.
+     *
+     * @return a string representation of the map
+     */
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
@@ -96,15 +159,27 @@ public class GenericHashMapUsingArrayList<K, V> {
                 builder.append(", ");
             }
         }
+        // Remove trailing comma and space if there are any elements
+        if (builder.length() > 1) {
+            builder.setLength(builder.length() - 2);
+        }
         builder.append("}");
         return builder.toString();
     }
 
+    /**
+     * A private inner class representing a key-value pair (node) in the hash map.
+     */
     private class Node {
-
         K key;
         V val;
 
+        /**
+         * Constructs a new Node with the specified key and value.
+         *
+         * @param key the key of the key-value pair
+         * @param val the value of the key-value pair
+         */
         Node(K key, V val) {
             this.key = key;
             this.val = val;


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayListTest.java b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayListTest.java
index 37e43d2a..629aaae9 100644
--- a/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayListTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayListTest.java
@@ -50,4 +50,47 @@ class GenericHashMapUsingArrayListTest {
         assertEquals("Washington DC", map.get(101));
         assertTrue(map.containsKey(46));
     }
+
+    @Test
+    void testRemoveNonExistentKey() {
+        GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
+        map.put("USA", "Washington DC");
+        map.remove("Nepal"); // Attempting to remove a non-existent key
+        assertEquals(1, map.size()); // Size should remain the same
+    }
+
+    @Test
+    void testRehashing() {
+        GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
+        for (int i = 0; i < 20; i++) {
+            map.put("Key" + i, "Value" + i);
+        }
+        assertEquals(20, map.size()); // Ensure all items were added
+        assertEquals("Value5", map.get("Key5")); // Check retrieval after rehash
+    }
+
+    @Test
+    void testUpdateValueForExistingKey() {
+        GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
+        map.put("USA", "Washington DC");
+        map.put("USA", "New Washington DC"); // Updating value for existing key
+        assertEquals("New Washington DC", map.get("USA"));
+    }
+
+    @Test
+    void testToStringMethod() {
+        GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
+        map.put("USA", "Washington DC");
+        map.put("Nepal", "Kathmandu");
+        String expected = "{USA : Washington DC, Nepal : Kathmandu}";
+        assertEquals(expected, map.toString());
+    }
+
+    @Test
+    void testContainsKey() {
+        GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
+        map.put("USA", "Washington DC");
+        assertTrue(map.containsKey("USA"));
+        assertFalse(map.containsKey("Nepal"));
+    }
 }