Add dynamic hash table functionality

Ray · Ray · commit ed1273a35d25 · 2020-08-17T19:22:32.000-04:00
diff --git a/DataStructures/HashMap/Hashing/HashMapLinearProbing.java b/DataStructures/HashMap/Hashing/HashMapLinearProbing.java
@@ -1,22 +1,27 @@
 package 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;
-    private Integer[] buckets;
+    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) {
-        buckets = new Integer[hsize];
+        this.buckets = new Integer[hsize];
         this.hsize = hsize;
-        AVAILABLE = new Integer(Integer.MIN_VALUE);
+        this.AVAILABLE = new Integer(Integer.MIN_VALUE);
+        this.size = 0;
     }
     
     /**
@@ -48,6 +53,7 @@ public void insertHash(int key) {
         for (int i = 0;i < hsize; i++) {
     		if(buckets[hash] == null || buckets[hash] == AVAILABLE) {
     			buckets[hash] = wrappedInt;
+    	        size++;
     			return;
     		}
     		
@@ -56,7 +62,7 @@ public void insertHash(int key) {
         	} else {
         		hash = 0;
         	} 
-    	}	
+    	}
     }
     
     /**
@@ -75,6 +81,7 @@ public void deleteHash(int key) {
         for(int i = 0;i < hsize; i++) {
         	if(buckets[hash] != null && buckets[hash].equals(wrappedInt)) {
             	buckets[hash] = AVAILABLE;
+            	size--;
             	return;
             }
         	
@@ -116,10 +123,12 @@ public int findHash(int key) {
         }
         
         for(int i = 0;i < hsize; i++) {
-        	if(buckets[hash].equals(wrappedInt)) {
-            	buckets[hash] = AVAILABLE;
-            	return hash;
-            }
+        	try {
+        		if(buckets[hash].equals(wrappedInt)) {
+                	buckets[hash] = AVAILABLE;
+                	return hash;
+                }
+        	} catch (Exception E) {}
         	
         	if(hash + 1 < hsize) {
         		hash++;
@@ -131,6 +140,27 @@ public int findHash(int key) {
     	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
diff --git a/DataStructures/HashMap/Hashing/MainLinearProbing.java b/DataStructures/HashMap/Hashing/MainLinearProbing.java
@@ -17,6 +17,7 @@ public static void main(String[] args) {
 			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();
 
@@ -46,7 +47,12 @@ public static void main(String[] args) {
 					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;
+				}
 			}
 			
 		}

Original file line number	Diff line number	Diff line change
`@@ -17,6 +17,7 @@ public static void main(String[] args) {`
`17`	`17`	`System.out.println("3. Print Table");`
`18`	`18`	`System.out.println("4. Exit");`
`19`	`19`	`System.out.println("5. Search and print key index");`
	`20`	`+ System.out.println("6. Check load factor");`
`20`	`21`
`21`	`22`	`choice = In.nextInt();`
`22`	`23`
`@@ -46,7 +47,12 @@ public static void main(String[] args) {`
`46`	`47`	`System.out.println("Enter the Key to find and print: ");`
`47`	`48`	`key = In.nextInt();`
`48`	`49`	`System.out.println("Key: "+ key + " is at index: "+ h.findHash(key));`
	`50`	`+ break;`
`49`	`51`	`}`
	`52`	`+ case 6: {`
	`53`	`+ h.checkLoadFactor();`
	`54`	`+ break;`
	`55`	`+ }`
`50`	`56`	`}`
`51`	`57`
`52`	`58`	`}`