Advertisement
Guest User

separate chaining

a guest
Apr 1st, 2015
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.08 KB | None | 0 0
  1. package assignment10;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Collection;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8.  
  9. public class ChainingHashTable implements Set<String> {
  10.  
  11.     int capacity;
  12.     int oldCapacity;
  13.     HashFunctor functor;
  14.     double λThreshold = 0.5;
  15.     int size = 0;
  16.     private LinkedList<String>[] storage;
  17.  
  18.     @SuppressWarnings("unchecked")
  19.     public ChainingHashTable(int capacity, HashFunctor functor) {
  20.         this.capacity = capacity;
  21.         this.oldCapacity = capacity;
  22.         this.functor = functor;
  23.         storage = (LinkedList<String>[]) new LinkedList[capacity];
  24.     }
  25.  
  26.     @SuppressWarnings("unchecked")
  27.     @Override
  28.     public boolean add(String item) {
  29.         // return false if item is already in the hash table
  30.         if (contains(item) == true) {
  31.             return false;
  32.         }
  33.         // item isn't in hash table
  34.         else {
  35.             // make capacity the lowest prime inclusive
  36.             if (prime(capacity) == false) {
  37.                 capacity = nextPrime(capacity);
  38.             }
  39.             // λ >= 0.5
  40.             if (size >= λThreshold * capacity) {
  41.                 capacity = nextPrime(capacity);
  42.                 return add(item);
  43.             }
  44.             // finds lowest prime that meets the criterion λ < 0.5
  45.             else {
  46.                 // condition for rehashing
  47.                 if (oldCapacity != capacity) {
  48.                     // set old to new capacity
  49.                     oldCapacity = capacity;
  50.                     // need to rehash the table
  51.                     LinkedList<String>[] oldStorage = storage;
  52.                     // set hashTable to a new String array with the new capacity
  53.                     storage = (LinkedList<String>[]) new LinkedList[capacity];
  54.                     // clear size
  55.                     size = 0;
  56.                     // loops through the old hash table
  57.                     for (int i = 0; i < oldStorage.length; i++) {
  58.                         // inserts the values from the old hash table into the
  59.                         // new one with new hash function
  60.                         if(oldStorage[i] != null) {
  61.                             // linked list at position i in the array isn't empty
  62.                             // loop through and add all elements in the linked list
  63.                             while (oldStorage[i].size() != 0) {
  64.                                 // inserts the first item in the linked list and
  65.                                 // removes it from the linked list
  66.                                 separateChainingAdd(oldStorage[i].poll());
  67.                             }
  68.                         }
  69.                     }
  70.                     separateChainingAdd(item);
  71.                     return true;
  72.                 } else {
  73.                     separateChainingAdd(item);
  74.                     return true;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.    
  80.     /**
  81.      * inserts item into hash table using separate chaining
  82.      *
  83.      * @param item
  84.      */
  85.     private void separateChainingAdd(String item) {
  86.         int hash = functor.hash(item);
  87.         if(storage[hash % capacity] == null) {
  88.             storage[hash % capacity] = new LinkedList<String>();
  89.             storage[hash % capacity].add(item);
  90.             size++;
  91.         }
  92.         // the linked list at position hash, doesn't contain the item
  93.         else if(!storage[hash % capacity].contains(item)) {
  94.             // add item to the linked list at hash
  95.             storage[hash % capacity].add(item);
  96.             size++;
  97.         }
  98.     }
  99.  
  100.     @Override
  101.     public boolean addAll(Collection<? extends String> items) {
  102.         boolean bool = false;
  103.         // adds all items in items
  104.         for (String item : items) {
  105.             // if new item is added, change bool to true
  106.             if (add(item)) {
  107.                 bool = true;
  108.             }
  109.         }
  110.         // return bool after everything is added
  111.         return bool;
  112.     }
  113.  
  114.     @SuppressWarnings("unchecked")
  115.     @Override
  116.     public void clear() {
  117.         capacity = 2;
  118.         storage = (LinkedList<String>[]) new LinkedList[capacity];
  119.         size = 0;
  120.     }
  121.  
  122.     @Override
  123.     public boolean contains(String item) {
  124.         int hash = functor.hash(item);
  125.         if(storage[hash % oldCapacity] == null) {
  126.             return false;
  127.         }
  128.         else {
  129.             return storage[hash % oldCapacity].contains(item);
  130.         }
  131.     }
  132.  
  133.     @Override
  134.     public boolean containsAll(Collection<? extends String> items) {
  135.         boolean bool = false;
  136.         // adds all items in items
  137.         for (String item : items) {
  138.             // if new item is added, change bool to true
  139.             if (contains(item)) {
  140.                 bool = true;
  141.             }
  142.         }
  143.         // return bool after everything is added
  144.         return bool;
  145.     }
  146.  
  147.     @Override
  148.     public boolean isEmpty() {
  149.         return (size() == 0);
  150.     }
  151.  
  152.     @Override
  153.     public int size() {
  154.         return size;
  155.     }
  156.  
  157.     /**
  158.      * method used to find the next prime number
  159.      *
  160.      * @param capacity
  161.      * @return next prime number
  162.      */
  163.     private static int nextPrime(int capacity) {
  164.         // starts with smallest integer larger than capacity till next prime
  165.         capacity++;
  166.         while (prime(capacity) == false) {
  167.             return nextPrime(capacity);
  168.         }
  169.         return capacity;
  170.     }
  171.  
  172.     /**
  173.      * checks to see if n is prime
  174.      *
  175.      * @param n
  176.      * @return boolean true if prime, false otherwise
  177.      */
  178.     private static boolean prime(int n) {
  179.         // i from 2 to floor function of sqrt(n)
  180.         for (int i = 2; i < Math.sqrt(n); i++) {
  181.             if (n % i == 0) {
  182.                 return false;
  183.             }
  184.         }
  185.         return true;
  186.     }
  187.    
  188.     public static void main(String[] args) {
  189.         BadHashFunction bhf = new BadHashFunction();
  190.         ChainingHashTable cht = new ChainingHashTable(5, bhf);
  191.         List<String> arrayList = new ArrayList<String>();
  192.         arrayList.add("one");
  193.         arrayList.add("two");
  194.         arrayList.add("six");
  195.         arrayList.add("three");
  196.        
  197.         Collection<String> c = arrayList;
  198.        
  199.         System.out.println(cht.addAll(c));
  200.         while(cht.storage[3].isEmpty() == false) {
  201.             System.out.println(cht.storage[3].poll());
  202.         }
  203.        
  204.     }
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement