Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package assignment10;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Collection;
- import java.util.LinkedList;
- import java.util.List;
- public class ChainingHashTable implements Set<String> {
- int capacity;
- int oldCapacity;
- HashFunctor functor;
- double λThreshold = 0.5;
- int size = 0;
- private LinkedList<String>[] storage;
- @SuppressWarnings("unchecked")
- public ChainingHashTable(int capacity, HashFunctor functor) {
- this.capacity = capacity;
- this.oldCapacity = capacity;
- this.functor = functor;
- storage = (LinkedList<String>[]) new LinkedList[capacity];
- }
- @SuppressWarnings("unchecked")
- @Override
- public boolean add(String item) {
- // return false if item is already in the hash table
- if (contains(item) == true) {
- return false;
- }
- // item isn't in hash table
- else {
- // make capacity the lowest prime inclusive
- if (prime(capacity) == false) {
- capacity = nextPrime(capacity);
- }
- // λ >= 0.5
- if (size >= λThreshold * capacity) {
- capacity = nextPrime(capacity);
- return add(item);
- }
- // finds lowest prime that meets the criterion λ < 0.5
- else {
- // condition for rehashing
- if (oldCapacity != capacity) {
- // set old to new capacity
- oldCapacity = capacity;
- // need to rehash the table
- LinkedList<String>[] oldStorage = storage;
- // set hashTable to a new String array with the new capacity
- storage = (LinkedList<String>[]) new LinkedList[capacity];
- // clear size
- size = 0;
- // loops through the old hash table
- for (int i = 0; i < oldStorage.length; i++) {
- // inserts the values from the old hash table into the
- // new one with new hash function
- if(oldStorage[i] != null) {
- // linked list at position i in the array isn't empty
- // loop through and add all elements in the linked list
- while (oldStorage[i].size() != 0) {
- // inserts the first item in the linked list and
- // removes it from the linked list
- separateChainingAdd(oldStorage[i].poll());
- }
- }
- }
- separateChainingAdd(item);
- return true;
- } else {
- separateChainingAdd(item);
- return true;
- }
- }
- }
- }
- /**
- * inserts item into hash table using separate chaining
- *
- * @param item
- */
- private void separateChainingAdd(String item) {
- int hash = functor.hash(item);
- if(storage[hash % capacity] == null) {
- storage[hash % capacity] = new LinkedList<String>();
- storage[hash % capacity].add(item);
- size++;
- }
- // the linked list at position hash, doesn't contain the item
- else if(!storage[hash % capacity].contains(item)) {
- // add item to the linked list at hash
- storage[hash % capacity].add(item);
- size++;
- }
- }
- @Override
- public boolean addAll(Collection<? extends String> items) {
- boolean bool = false;
- // adds all items in items
- for (String item : items) {
- // if new item is added, change bool to true
- if (add(item)) {
- bool = true;
- }
- }
- // return bool after everything is added
- return bool;
- }
- @SuppressWarnings("unchecked")
- @Override
- public void clear() {
- capacity = 2;
- storage = (LinkedList<String>[]) new LinkedList[capacity];
- size = 0;
- }
- @Override
- public boolean contains(String item) {
- int hash = functor.hash(item);
- if(storage[hash % oldCapacity] == null) {
- return false;
- }
- else {
- return storage[hash % oldCapacity].contains(item);
- }
- }
- @Override
- public boolean containsAll(Collection<? extends String> items) {
- boolean bool = false;
- // adds all items in items
- for (String item : items) {
- // if new item is added, change bool to true
- if (contains(item)) {
- bool = true;
- }
- }
- // return bool after everything is added
- return bool;
- }
- @Override
- public boolean isEmpty() {
- return (size() == 0);
- }
- @Override
- public int size() {
- return size;
- }
- /**
- * method used to find the next prime number
- *
- * @param capacity
- * @return next prime number
- */
- private static int nextPrime(int capacity) {
- // starts with smallest integer larger than capacity till next prime
- capacity++;
- while (prime(capacity) == false) {
- return nextPrime(capacity);
- }
- return capacity;
- }
- /**
- * checks to see if n is prime
- *
- * @param n
- * @return boolean true if prime, false otherwise
- */
- private static boolean prime(int n) {
- // i from 2 to floor function of sqrt(n)
- for (int i = 2; i < Math.sqrt(n); i++) {
- if (n % i == 0) {
- return false;
- }
- }
- return true;
- }
- public static void main(String[] args) {
- BadHashFunction bhf = new BadHashFunction();
- ChainingHashTable cht = new ChainingHashTable(5, bhf);
- List<String> arrayList = new ArrayList<String>();
- arrayList.add("one");
- arrayList.add("two");
- arrayList.add("six");
- arrayList.add("three");
- Collection<String> c = arrayList;
- System.out.println(cht.addAll(c));
- while(cht.storage[3].isEmpty() == false) {
- System.out.println(cht.storage[3].poll());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement