Repository: TheAlgorithms/Java
Pull request #3902 (2023-02-24 09:07:49)

Fix Linear probing hash map implementation
Linear probing hash map. implementation is incorrect in the master branch. This PR fixes that issue.

<!-- 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.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapLinearProbing.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapLinearProbing.java
deleted file mode 100644
index c8ed333a..00000000
--- a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapLinearProbing.java
+++ /dev/null
@@ -1,203 +0,0 @@
-package com.thealgorithms.datastructures.hashmap.hashing;
-
-import java.util.*;
-
-/**
- * This class is an implementation of a hash table using linear probing It uses
- * a dynamic array to lengthen the size of the hash table when load factor > .7
- */
-public class HashMapLinearProbing {
-
-    private int hsize; // size of the hash table
-    private Integer[] buckets; // array representing the table
-    private Integer AVAILABLE;
-    private int size; // amount of elements in the hash table
-
-    /**
-     * Constructor initializes buckets array, hsize, and creates dummy object
-     * for AVAILABLE
-     *
-     * @param hsize the desired size of the hash map
-     */
-    public HashMapLinearProbing(int hsize) {
-        this.buckets = new Integer[hsize];
-        this.hsize = hsize;
-        this.AVAILABLE = Integer.MIN_VALUE;
-        this.size = 0;
-    }
-
-    /**
-     * The Hash Function takes a given key and finds an index based on its data
-     *
-     * @param key the desired key to be converted
-     * @return int an index corresponding to the key
-     */
-    public int hashing(int key) {
-        int hash = key % hsize;
-        if (hash < 0) {
-            hash += hsize;
-        }
-        return hash;
-    }
-
-    /**
-     * inserts the key into the hash map by wrapping it as an Integer object
-     *
-     * @param key the desired key to be inserted in the hash map
-     */
-    public void insertHash(int key) {
-        Integer wrappedInt = key;
-        int hash = hashing(key);
-
-        if (isFull()) {
-            System.out.println("Hash table is full");
-            return;
-        }
-
-        for (int i = 0; i < hsize; i++) {
-            if (buckets[hash] == null || buckets[hash] == AVAILABLE) {
-                buckets[hash] = wrappedInt;
-                size++;
-                return;
-            }
-
-            if (hash + 1 < hsize) {
-                hash++;
-            } else {
-                hash = 0;
-            }
-        }
-    }
-
-    /**
-     * deletes a key from the hash map and adds an available placeholder
-     *
-     * @param key the desired key to be deleted
-     */
-    public void deleteHash(int key) {
-        Integer wrappedInt = key;
-        int hash = hashing(key);
-
-        if (isEmpty()) {
-            System.out.println("Table is empty");
-            return;
-        }
-
-        for (int i = 0; i < hsize; i++) {
-            if (buckets[hash] != null && buckets[hash].equals(wrappedInt)) {
-                buckets[hash] = AVAILABLE;
-                size--;
-                return;
-            }
-
-            if (hash + 1 < hsize) {
-                hash++;
-            } else {
-                hash = 0;
-            }
-        }
-        System.out.println("Key " + key + " not found");
-    }
-
-    /**
-     * Displays the hash table line by line
-     */
-    public void displayHashtable() {
-        for (int i = 0; i < hsize; i++) {
-            if (buckets[i] == null || buckets[i] == AVAILABLE) {
-                System.out.println("Bucket " + i + ": Empty");
-            } else {
-                System.out.println(
-                    "Bucket " + i + ": " + buckets[i].toString()
-                );
-            }
-        }
-    }
-
-    /**
-     * Finds the index of location based on an inputed key
-     *
-     * @param key the desired key to be found
-     * @return int the index where the key is located
-     */
-    public int findHash(int key) {
-        Integer wrappedInt = key;
-        int hash = hashing(key);
-
-        if (isEmpty()) {
-            System.out.println("Table is empty");
-            return -1;
-        }
-
-        for (int i = 0; i < hsize; i++) {
-            try {
-                if (buckets[hash].equals(wrappedInt)) {
-                    buckets[hash] = AVAILABLE;
-                    return hash;
-                }
-            } catch (Exception E) {}
-
-            if (hash + 1 < hsize) {
-                hash++;
-            } else {
-                hash = 0;
-            }
-        }
-        System.out.println("Key " + key + " not found");
-        return -1;
-    }
-
-    private void lengthenTable() {
-        buckets = Arrays.copyOf(buckets, hsize * 2);
-        hsize *= 2;
-        System.out.println("Table size is now: " + hsize);
-    }
-
-    /**
-     * Checks the load factor of the hash table if greater than .7,
-     * automatically lengthens table to prevent further collisions
-     */
-    public void checkLoadFactor() {
-        double factor = (double) size / hsize;
-        if (factor > .7) {
-            System.out.println(
-                "Load factor is " + factor + ",  lengthening table"
-            );
-            lengthenTable();
-        } else {
-            System.out.println("Load factor is " + factor);
-        }
-    }
-
-    /**
-     * isFull returns true if the hash map is full and false if not full
-     *
-     * @return boolean is Empty
-     */
-    public boolean isFull() {
-        boolean response = true;
-        for (int i = 0; i < hsize; i++) {
-            if (buckets[i] == null || buckets[i] == AVAILABLE) {
-                response = false;
-                break;
-            }
-        }
-        return response;
-    }
-
-    /**
-     * isEmpty returns true if the hash map is empty and false if not empty
-     *
-     * @return boolean is Empty
-     */
-    public boolean isEmpty() {
-        boolean response = true;
-        for (int i = 0; i < hsize; i++) {
-            if (buckets[i] != null) {
-                response = false;
-                break;
-            }
-        }
-        return response;
-    }
-}
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMap.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMap.java
new file mode 100644
index 00000000..c96da27c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMap.java
@@ -0,0 +1,141 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+import java.util.ArrayList;
+
+/***
+ * This class is an implementation of a hash table using linear probing.
+ * @see <a href="https://en.wikipedia.org/wiki/Linear_probing">Linear Probing Hash Table</a>
+ *
+ * @param <Key> keys type.
+ * @param <Value> values type.
+ */
+public class LinearProbingHashMap<Key extends Comparable<Key>, Value> extends Map<Key, Value> {
+    private int hsize; // size of the hash table
+    private Key[] keys;
+    private Value[] values;
+    private int size; // amount of elements in the hash table
+
+    public LinearProbingHashMap() {
+        this(16);
+    }
+
+    @SuppressWarnings("unchecked")
+    public LinearProbingHashMap(int size) {
+        this.hsize = size;
+        keys = (Key[]) new Comparable[size];
+        values = (Value[]) new Object[size];
+    }
+
+    @Override
+    public boolean put(Key key, Value value) {
+        if (key == null) {
+            return false;
+        }
+
+        if (size > hsize / 2) {
+            resize(2 * hsize);
+        }
+
+        int keyIndex = hash(key, hsize);
+        for (; keys[keyIndex] != null; keyIndex = increment(keyIndex)) {
+            if (key.equals(keys[keyIndex])) {
+                values[keyIndex] = value;
+                return true;
+            }
+        }
+
+        keys[keyIndex] = key;
+        values[keyIndex] = value;
+        size++;
+        return true;
+    }
+
+    @Override
+    public Value get(Key key) {
+        if (key == null) {
+            return null;
+        }
+
+        for (int i = hash(key, hsize); keys[i] != null; i = increment(i)) {
+            if (key.equals(keys[i])) {
+                return values[i];
+            }
+        }
+
+        return null;
+    }
+
+    @Override
+    public boolean delete(Key key) {
+        if (key == null || !contains(key)) {
+            return false;
+        }
+
+        int i = hash(key, hsize);
+        while (!key.equals(keys[i])) {
+            i = increment(i);
+        }
+
+        keys[i] = null;
+        values[i] = null;
+
+        i = increment(i);
+        while (keys[i] != null) {
+            // delete keys[i] an vals[i] and reinsert
+            Key keyToRehash = keys[i];
+            Value valToRehash = values[i];
+            keys[i] = null;
+            values[i] = null;
+            size--;
+            put(keyToRehash, valToRehash);
+            i = increment(i);
+        }
+
+        size--;
+        if (size > 0 && size <= hsize / 8) {
+            resize(hsize / 2);
+        }
+
+        return true;
+    }
+
+    @Override
+    public boolean contains(Key key) {
+        return get(key) != null;
+    }
+
+    @Override
+    int size() {
+        return size;
+    }
+
+    @Override
+    Iterable<Key> keys() {
+        ArrayList<Key> listOfKeys = new ArrayList<>(size);
+        for (int i = 0; i < hsize; i++) {
+            if (keys[i] != null) {
+                listOfKeys.add(keys[i]);
+            }
+        }
+
+        listOfKeys.sort(Comparable::compareTo);
+        return listOfKeys;
+    }
+
+    private int increment(int i) {
+        return (i + 1) % hsize;
+    }
+
+    private void resize(int newSize) {
+        LinearProbingHashMap<Key, Value> tmp = new LinearProbingHashMap<>(newSize);
+        for (int i = 0; i < hsize; i++) {
+            if (keys[i] != null) {
+                tmp.put(keys[i], values[i]);
+            }
+        }
+
+        this.keys = tmp.keys;
+        this.values = tmp.values;
+        this.hsize = newSize;
+    }
+}
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainLinearProbing.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainLinearProbing.java
deleted file mode 100644
index bd75d171..00000000
--- a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainLinearProbing.java
+++ /dev/null
@@ -1,69 +0,0 @@
-package com.thealgorithms.datastructures.hashmap.hashing;
-
-import java.util.Scanner;
-
-public class MainLinearProbing {
-
-    public static void main(String[] args) {
-        int choice, key;
-
-        HashMapLinearProbing h = new HashMapLinearProbing(7);
-        Scanner In = 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");
-            System.out.println("5. Search and print key index");
-            System.out.println("6. Check load factor");
-
-            choice = In.nextInt();
-
-            switch (choice) {
-                case 1:
-                    {
-                        System.out.println("Enter the Key: ");
-                        key = In.nextInt();
-                        h.insertHash(key);
-                        break;
-                    }
-                case 2:
-                    {
-                        System.out.println("Enter the Key delete:  ");
-                        key = In.nextInt();
-                        h.deleteHash(key);
-                        break;
-                    }
-                case 3:
-                    {
-                        System.out.println("Print table");
-                        h.displayHashtable();
-                        break;
-                    }
-                case 4:
-                    {
-                        In.close();
-                        return;
-                    }
-                case 5:
-                    {
-                        System.out.println(
-                            "Enter the Key to find and print:  "
-                        );
-                        key = In.nextInt();
-                        System.out.println(
-                            "Key: " + key + " is at index: " + h.findHash(key)
-                        );
-                        break;
-                    }
-                case 6:
-                    {
-                        h.checkLoadFactor();
-                        break;
-                    }
-            }
-        }
-    }
-}
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Map.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Map.java
new file mode 100644
index 00000000..cd27b0a7
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Map.java
@@ -0,0 +1,23 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+public abstract class Map<Key, Value> {
+
+    abstract boolean put(Key key, Value value);
+
+    abstract Value get(Key key);
+
+    abstract boolean delete(Key key);
+
+    abstract Iterable<Key> keys();
+
+    abstract int size();
+
+    public boolean contains(Key key) {
+        return get(key) != null;
+    }
+
+    protected int hash(Key key, int size) {
+        return (key.hashCode() & Integer.MAX_VALUE) % size;
+    }
+
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMapTest.java b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMapTest.java
new file mode 100644
index 00000000..d0a72a15
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMapTest.java
@@ -0,0 +1,8 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+class LinearProbingHashMapTest extends MapTest {
+    @Override
+    <Key extends Comparable<Key>, Value> Map<Key, Value> getMap() {
+        return new LinearProbingHashMap<>();
+    }
+}
diff --git a/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/MapTest.java b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/MapTest.java
new file mode 100644
index 00000000..5ccbcc30
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/hashmap/hashing/MapTest.java
@@ -0,0 +1,129 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.Random;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+abstract class MapTest {
+    abstract <Key extends Comparable<Key>, Value> Map<Key, Value> getMap();
+
+    @Test
+    void putTest() {
+        Map<Integer, String> map = getMap();
+
+        assertFalse(map.put(null, "-25"));
+        assertFalse(map.put(null, null));
+        assertTrue(map.put(-25, "-25"));
+        assertTrue(map.put(33, "33"));
+        assertTrue(map.put(100, "100"));
+        assertTrue(map.put(100, "+100"));
+        assertTrue(map.put(100, null));
+    }
+
+    @Test
+    void getTest() {
+        Map<Integer, String> map = getMap();
+        for (int i = -100; i < 100; i++) {
+            map.put(i, String.valueOf(i));
+        }
+
+        for (int i = -100; i < 100; i++) {
+            assertEquals(map.get(i), String.valueOf(i));
+        }
+
+        for (int i = 100; i < 200; i++) {
+            assertNull(map.get(i));
+        }
+
+        assertNull(map.get(null));
+    }
+
+    @Test
+    void deleteTest() {
+        Map<Integer, String> map = getMap();
+        for (int i = -100; i < 100; i++) {
+            map.put(i, String.valueOf(i));
+        }
+
+        for (int i = 0; i < 100; i++) {
+            assertTrue(map.delete(i));
+        }
+
+        for (int i = 100; i < 200; i++) {
+            assertFalse(map.delete(i));
+        }
+
+        assertFalse(map.delete(null));
+    }
+
+    @Test
+    void containsTest() {
+        Map<Integer, String> map = getMap();
+        for (int i = -100; i < 100; i++) {
+            map.put(i, String.valueOf(i));
+        }
+
+        for (int i = -50; i < 50; i++) {
+            assertTrue(map.contains(i));
+        }
+
+        for (int i = 100; i < 200; i++) {
+            assertFalse(map.contains(i));
+        }
+
+        assertFalse(map.contains(null));
+    }
+
+    @Test
+    void sizeTest() {
+        Map<Integer, String> map = getMap();
+        assertEquals(map.size(), 0);
+
+        for (int i = -100; i < 100; i++) {
+            map.put(i, String.valueOf(i));
+        }
+
+        assertEquals(map.size(), 200);
+
+        for (int i = -50; i < 50; i++) {
+            map.delete(i);
+        }
+
+        assertEquals(map.size(), 100);
+    }
+
+    @Test
+    void keysTest() {
+        Map<Integer, String> map = getMap();
+        Iterable<Integer> keys = map.keys();
+        assertFalse(keys.iterator().hasNext());
+
+        for (int i = 100; i > -100; i--) {
+            map.put(i, String.valueOf(i));
+        }
+
+        keys = map.keys();
+        int i = -100;
+        for (Integer key : keys) {
+            assertEquals(key, ++i);
+        }
+    }
+
+    @Test
+    void hashTest() {
+        Map<Integer, String> map = getMap();
+        int testSize = 100;
+        Random random = new Random();
+        for (int i = 0; i < 1000; i++) {
+            int randomInt = random.nextInt();
+            int hashIndex = map.hash(randomInt, testSize);
+            int negateHashIndex = map.hash(-randomInt, testSize);
+            assertTrue(hashIndex >= 0);
+            assertTrue(hashIndex < testSize);
+            assertTrue(negateHashIndex >= 0);
+            assertTrue(negateHashIndex < testSize);
+        }
+    }
+}