Fix universal hashing, implement ohter haching functions

benaich · benaich · commit 271bcd0beda1 · 2015-01-05T21:43:24.000Z
diff --git a/HashTable/HashTableInterface.java b/HashTable/HashTableInterface.java
@@ -5,6 +5,10 @@
 
 public interface HashTableInterface<K, V> {
 
+    public static enum HASH_FUNCTION {
+
+        UNIVERSAL, MODULO, MULTIPLICATIF
+    };
     public static final int INITIAL_TABLE_SIZE = 10;
     public static final double LOAD_FACTOR = 0.5;
     public static final int BIGNUMBER = 9161;
@@ -13,7 +17,7 @@ public interface HashTableInterface<K, V> {
 
     /* get the position of key */
     int indexOf(K key);
-    
+
     /* check whether the specified key exist in the hashtable */
     boolean contains(K key);
 
@@ -43,7 +47,7 @@ public interface HashTableInterface<K, V> {
 
     /* get the number of resizes */
     int getNumResizes();
-    
+
     /* get the current load factor */
     default float loadFactor() {
         return getSize() / (float) getTableSize();
@@ -65,13 +69,26 @@ default void printStatus() {
     }
 
     /* return a random universal hashing function */
-    default Function<K, Integer> getHashingFunction() {
-        int a, b, p;
-        a = r.nextInt();
-        b = r.nextInt();
-        p = HashTableInterface.nextPrime(BIGNUMBER);
-
-        return (x) -> Math.abs(((a * x.hashCode() + b * x.hashCode()) * p) % getTableSize());
+    default Function<K, Integer> getHashingFunction(){
+        return getHashingFunction(HASH_FUNCTION.UNIVERSAL);
+    }
+    default Function<K, Integer> getHashingFunction(HASH_FUNCTION type) {
+        Function<K, Integer> f;
+        if (type == HASH_FUNCTION.MODULO) {
+            f = x -> Math.abs(x.hashCode()) % getTableSize();
+        } else if (type == HASH_FUNCTION.UNIVERSAL) {
+            int a, b, p;
+            a = r.nextInt();
+            b = r.nextInt();
+            p = HashTableInterface.nextPrime(BIGNUMBER);
+            f = x -> Math.abs(((a * x.hashCode() + b) % p) % getTableSize());
+        } else {
+            f = x -> {
+                double c = 0.618;
+                return (int) Math.floor(((Math.abs(x.hashCode()) * c) % 1) * getTableSize());
+            };
+        }
+        return f;
     }
 
     /* get the next prime number after a*/
diff --git a/HashTable/SeparateChaining/SCHashTable.java b/HashTable/SeparateChaining/SCHashTable.java
@@ -17,9 +17,9 @@ public SCHashTable() {
         foh = getHashingFunction();
     }
 
-    public SCHashTable(Function<K, Integer> f) {
+    public SCHashTable(HASH_FUNCTION type) {
         array = new Node[tableSize];
-        foh = f;
+        foh = getHashingFunction(type);
     }
 
     @Override
@@ -175,6 +175,9 @@ public static void main(String[] args) {
         ht.put("walter", "white");
         ht.put("arys", "startk");
         ht.put("dextr", "red");
+        ht.put("benaich", "white");
+        ht.put("med", "startk");
+        ht.put("real", "red");
 
         ht.print();
 
@@ -188,11 +191,20 @@ public static void main(String[] args) {
         ht.printGraph();
         ht.printStatus();
         
-        // Testing
-        SCHashTable<String, String> table = new SCHashTable<>();
-        for (int i = 0; i < 100000; i++) {
+        // Testing Modulo
+        testing(HASH_FUNCTION.UNIVERSAL);
+        testing(HASH_FUNCTION.MULTIPLICATIF);
+        testing(HASH_FUNCTION.MODULO);
+    }    
+    
+    private static void testing(HASH_FUNCTION type) {
+        System.out.println("============ "+type+" ============");
+        SCHashTable<String, String> table = new SCHashTable<>(type);
+        for (int i = 0; i < 100; i++) {
             table.put(HashTableInterface.randomString(), HashTableInterface.randomString());
         }
         table.printStatus();
+        table.printGraph();
     }
+    
 }
