Repository: TheAlgorithms/Java
Pull request #3191 (2022-07-13 10:43:37)

Added Hash Table with Cuckoo Hashing
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

Fixing Issue: #3188

### **Checklist:**

<!-- Remove items that do not apply. 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.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapCuckooHashing.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapCuckooHashing.java
new file mode 100644
index 00000000..eeb01857
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapCuckooHashing.java
@@ -0,0 +1,254 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+
+import java.lang.Math;
+import java.util.Objects;
+
+/**
+ * This class is an implementation of a hash table using Cuckoo Hashing It uses
+ * a dynamic array to lengthen the size of the hash table when load factor > .7
+ *
+ * <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">...</a>
+ */
+public class HashMapCuckooHashing {
+
+    private int tableSize; // size of the hash table
+    private Integer[] buckets; // array representing the table
+    private final Integer AVAILABLE;
+    private int size; // number of elements in the hash table
+
+    private int thresh; // threshold for infinite loop checking
+
+    /**
+     * Constructor initializes buckets array, hsize, and creates dummy object
+     * for AVAILABLE
+     *
+     * @param tableSize the desired size of the hash map
+     */
+    public HashMapCuckooHashing(int tableSize) {
+        this.buckets = new Integer[tableSize];
+        this.tableSize = tableSize;
+        this.AVAILABLE = Integer.MIN_VALUE;
+        this.size = 0;
+        this.thresh = (int) (Math.log(tableSize) / Math.log(2)) + 2;
+    }
+
+    /**
+     * The 2 Hash Functions takes a given key and finds an index based on its data, 2 distinctive ways to minimize collisions
+     *
+     * @param key the desired key to be converted
+     * @return int an index corresponding to the key
+     */
+
+    public int hashFunction1(int key) {
+        int hash = key % tableSize;
+        if (hash < 0) {
+            hash += tableSize;
+        }
+        return hash;
+    }
+
+    public int hashFunction2(int key) {
+        int hash = key / tableSize;
+        hash %= tableSize;
+        if (hash < 0) {
+            hash += tableSize;
+        }
+        return hash;
+    }
+
+    /**
+     * inserts the key into the hash map by wrapping it as an Integer object, then uses while loop to insert new key
+     * if desired place is empty, return.
+     * if already occupied, continue while loop over the new key that has just been pushed out.
+     * if while loop continues more than Thresh, rehash table to new size, then push again.
+     *
+     * @param key the desired key to be inserted in the hash map
+     */
+
+    public void insertKey2HashTable(int key) {
+        Integer wrappedInt = key, temp;
+        int hash, loopCounter = 0;
+
+        if (isFull()) {
+            System.out.println("Hash table is full, lengthening & rehashing table");
+            reHashTableIncreasesTableSize();
+        }
+
+        if (checkTableContainsKey(key)) {
+            throw new IllegalArgumentException("Key already inside, no duplicates allowed");
+        }
+
+        while (loopCounter <= thresh) {
+            loopCounter++;
+            hash = hashFunction1(key);
+
+            if ((buckets[hash] == null) || Objects.equals(buckets[hash], AVAILABLE)) {
+                buckets[hash] = wrappedInt;
+                size++;
+                checkLoadFactor();
+                return;
+            }
+
+            temp = buckets[hash];
+            buckets[hash] = wrappedInt;
+            wrappedInt = temp;
+            hash = hashFunction2(temp);
+            if (Objects.equals(buckets[hash], AVAILABLE)) {
+                buckets[hash] = wrappedInt;
+                size++;
+                checkLoadFactor();
+                return;
+            } else if (buckets[hash] == null) {
+                buckets[hash] = wrappedInt;
+                size++;
+                checkLoadFactor();
+                return;
+            }
+
+            temp = buckets[hash];
+            buckets[hash] = wrappedInt;
+            wrappedInt = temp;
+        }
+        System.out.println("Infinite loop occurred, lengthening & rehashing table");
+        reHashTableIncreasesTableSize();
+        insertKey2HashTable(key);
+    }
+
+    /**
+     * creates new HashMapCuckooHashing object, then inserts each of the elements in the previous table to it with its new hash functions.
+     * then refers current array to new table.
+     *
+     */
+    public void reHashTableIncreasesTableSize() {
+        HashMapCuckooHashing newT = new HashMapCuckooHashing(tableSize * 2);
+        for (int i = 0; i < tableSize; i++) {
+            if (buckets[i] != null && !Objects.equals(buckets[i], AVAILABLE)) {
+                newT.insertKey2HashTable(this.buckets[i]);
+            }
+        }
+        this.tableSize *= 2;
+        this.buckets = newT.buckets;
+        this.thresh = (int) (Math.log(tableSize) / Math.log(2)) + 2;
+    }
+
+
+    /**
+     * deletes a key from the hash map and adds an available placeholder
+     *
+     * @param key the desired key to be deleted
+     */
+    public void deleteKeyFromHashTable(int key) {
+        Integer wrappedInt = key;
+        int hash = hashFunction1(key);
+        if (isEmpty()) {
+            throw new IllegalArgumentException("Table is empty");
+        }
+
+        if (Objects.equals(buckets[hash], wrappedInt)) {
+            buckets[hash] = AVAILABLE;
+            size--;
+            return;
+        }
+
+        hash = hashFunction2(key);
+        if (Objects.equals(buckets[hash], wrappedInt)) {
+            buckets[hash] = AVAILABLE;
+            size--;
+            return;
+        }
+        throw new IllegalArgumentException("Key " + key + " already inside, no duplicates allowed");
+    }
+
+    /**
+     * Displays the hash table line by line
+     */
+    public void displayHashtable() {
+        for (int i = 0; i < tableSize; i++) {
+            if ((buckets[i] == null) || Objects.equals(buckets[i], AVAILABLE)) {
+                System.out.println("Bucket " + i + ": Empty");
+            } else {
+                System.out.println("Bucket " + i + ": " + buckets[i].toString());
+            }
+        }
+        System.out.println();
+    }
+
+    /**
+     * Finds the index of location based on an inputted key
+     *
+     * @param key the desired key to be found
+     * @return int the index where the key is located
+     */
+    public int findKeyInTable(int key) {
+        Integer wrappedInt = key;
+        int hash = hashFunction1(key);
+
+        if (isEmpty()) {
+            throw new IllegalArgumentException("Table is empty");
+        }
+
+        if (Objects.equals(buckets[hash], wrappedInt)) return hash;
+
+        hash = hashFunction2(key);
+        if (!Objects.equals(buckets[hash], wrappedInt))
+            throw new IllegalArgumentException("Key " + key + " not found in table");
+        else {
+            return hash;
+        }
+    }
+    /**
+     * checks if key is inside without any output other than returned boolean.
+     *
+     * @param key the desired key to be found
+     * @return int the index where the key is located
+     */
+    public boolean checkTableContainsKey(int key){
+        return  ((buckets[hashFunction1(key)] != null && buckets[hashFunction1(key)].equals(key)) || (buckets[hashFunction2(key)] != null && buckets[hashFunction2(key)] == key));
+    }
+
+    /**
+     * Checks the load factor of the hash table if greater than .7,
+     * automatically lengthens table to prevent further collisions
+     */
+    public double checkLoadFactor() {
+        double factor = (double) size / tableSize;
+        if (factor > .7) {
+            System.out.printf("Load factor is %.2f , rehashing table\n", factor);
+            reHashTableIncreasesTableSize();
+        }
+        return 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 < tableSize; i++) {
+            if (buckets[i] == null || Objects.equals(buckets[i], AVAILABLE)) {
+                return false;
+            }
+        }
+        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 < tableSize; i++) {
+            if (buckets[i] != null) {
+                response = false;
+                break;
+            }
+        }
+        return response;
+    }
+    public int getNumberOfKeysInTable(){return size;}
+}
diff --git a/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainCuckooHashing.java b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainCuckooHashing.java
new file mode 100644
index 00000000..d38ff7d0
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainCuckooHashing.java
@@ -0,0 +1,65 @@
+package com.thealgorithms.datastructures.hashmap.hashing;
+
+import java.util.Scanner;
+
+public class MainCuckooHashing {
+    public static void main(String[] args) {
+
+        int choice, key;
+
+        HashMapCuckooHashing h = new HashMapCuckooHashing(7);
+        Scanner In = new Scanner(System.in);
+
+        while (true) {
+            System.out.println("_________________________");
+            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");
+            System.out.println("7. Rehash Current Table");
+
+            choice = In.nextInt();
+
+            switch (choice) {
+                case 1: {
+                    System.out.println("Enter the Key: ");
+                    key = In.nextInt();
+                    h.insertKey2HashTable(key);
+                    break;
+                }
+                case 2: {
+                    System.out.println("Enter the Key delete:  ");
+                    key = In.nextInt();
+                    h.deleteKeyFromHashTable(key);
+                    break;
+                }
+                case 3: {
+                    System.out.println("Print table:\n");
+                    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.findKeyInTable(key) + "\n");
+                    break;
+                }
+                case 6: {
+                    System.out.printf("Load factor is: %.2f\n", h.checkLoadFactor());
+                    break;
+                }
+                case 7: {
+                    h.reHashTableIncreasesTableSize();
+                    break;
+                }
+            }
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/hashmap/HashMapCuckooHashingTest.java b/src/test/java/com/thealgorithms/datastructures/hashmap/HashMapCuckooHashingTest.java
new file mode 100644
index 00000000..797db6cb
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/hashmap/HashMapCuckooHashingTest.java
@@ -0,0 +1,104 @@
+package com.thealgorithms.datastructures.hashmap;
+
+import com.thealgorithms.datastructures.hashmap.hashing.HashMapCuckooHashing;
+import org.junit.jupiter.api.Test;
+
+import java.util.*;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class HashMapCuckooHashingTest {
+
+    @Test
+    void insertKey() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        assertEquals(0, hashTable.getNumberOfKeysInTable());
+
+        hashTable.insertKey2HashTable(3);
+
+        assertEquals(1, hashTable.getNumberOfKeysInTable());
+    }
+
+    @Test
+    void getKeyIndex() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        hashTable.insertKey2HashTable(8);
+        hashTable.insertKey2HashTable(4);
+
+        assertNotEquals(-1, hashTable.findKeyInTable(8));
+    }
+
+    @Test
+    void containsKey() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        hashTable.insertKey2HashTable(8);
+        boolean contains = hashTable.checkTableContainsKey(8);
+
+        assertTrue(contains);
+    }
+
+    @Test
+    void removeKey() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        hashTable.insertKey2HashTable(3);
+
+        int initialSize = hashTable.getNumberOfKeysInTable();
+
+        hashTable.deleteKeyFromHashTable(3);
+
+        assertEquals(initialSize - 1, hashTable.getNumberOfKeysInTable());
+    }
+
+    @Test
+    void removeNone() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        int initialSize = hashTable.getNumberOfKeysInTable();
+        try {
+            hashTable.deleteKeyFromHashTable(3);
+        }
+        catch (Exception e){
+            assertTrue(true);
+            return;
+        }
+        fail();
+    }
+
+    @Test
+    void reHashTableIncreasesTableSize() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        int initialSize = hashTable.getNumberOfKeysInTable();
+
+        hashTable.reHashTableIncreasesTableSize();
+
+        assertEquals(initialSize * 2, hashTable.getNumberOfKeysInTable());
+    }
+
+    @Test
+    void hashFunctionsAreDifferent() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        hashTable.insertKey2HashTable(33);
+
+        assertNotEquals(hashTable.hashFunction1(3), hashTable.hashFunction2(3));
+    }
+
+    @Test
+    void avoidInfiniteLoops() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        hashTable.insertKey2HashTable(0);
+        hashTable.insertKey2HashTable(10);
+        hashTable.insertKey2HashTable(100);
+
+        assertTrue(hashTable.checkTableContainsKey(0));
+        assertTrue(hashTable.checkTableContainsKey(10));
+        assertTrue(hashTable.checkTableContainsKey(100));
+    }
+
+
+    private HashMapCuckooHashing createHashMapCuckooHashing() {
+        HashMapCuckooHashing hashTable = new HashMapCuckooHashing(10);
+        int[] values = {11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222};
+        Arrays.stream(values).forEach(hashTable::insertKey2HashTable);
+        return hashTable;
+    }
+
+}
\ No newline at end of file