+1 (315) 557-6473 

Program To Implement a Hash Table Using Java Programming Language Assignment Solutions.


Instructions

Objective
Write a java assignment program to implement a hash table.

Requirements and Specifications

Implement hash table in Java programming language
Implement hash table in Java programming language 1

Source Code

LAB 8

import java.util.HashSet;

import java.util.Random;

/**

 *

 * @author SivasamyA

 */

public class Lab8 {

    public static final int CAPACITY = 200131;

    /*

    Some primes of the form 4n+3:

    251

    2887

    10039

    25867

    50119

    100019

    200131

    ...

    999983

    1101319

    2000003

    ...

    9999991 <-- Good luck!

    39999983 <-- Good luck!!

    58115887 <-- Good luck!!!

    */

    public static final int HOW_MANY = (int)(.439 * CAPACITY);

    public static final int ONE_OUT_OF = 5;

    public static final int SEED = 271001;

    public static void main(String args[]) {

       MyHashTable ht1 = new MyHashTable(CAPACITY),

                            ht2 = new MyHashTable(CAPACITY);

       HashSet hs1 = new HashSet(CAPACITY),

                        hs2 = new HashSet(CAPACITY);

       Random rand = new Random(SEED);

       System.out.print("Inserting " + HOW_MANY + " numbers...");

       long start = System.currentTimeMillis();

       for (int i = 0; i < HOW_MANY; i++) {

          int rnum = rand.nextInt(Short.MAX_VALUE);

              ht1.add(rnum);

              hs1.add(rnum);

              ht2.add(rnum);

              hs2.add(rnum);

       }

       long end = System.currentTimeMillis();

       System.out.println("done, time=" + (end - start));

       System.out.print("Checking equivalence...");

       start = System.currentTimeMillis();

       boolean uniqueElementsEqual = MyHashTable.equalsUniqueElements(ht1, ht2);

       end = System.currentTimeMillis();

       boolean unqiqueElementsEqualCorrect = hs1.equals(hs2);

       System.out.println("done, equivalence=" + uniqueElementsEqual +

                          ", time=" + (end - start) + ", result=" +

                          ((unqiqueElementsEqualCorrect == uniqueElementsEqual) ? "correct" : "incorrect"));

       MyHashTable ht = ht1;

       HashSet hs = hs1;

       if (rand.nextInt(ONE_OUT_OF) == 0) {

           ht = ht2;

           hs = hs2;

       }

       System.out.print("Removing one random value...");

       start = System.currentTimeMillis();

       int removeMe = rand.nextInt(Short.MAX_VALUE);

       boolean removed = ht.remove(removeMe);

       while (removed == false) {

           removeMe = rand.nextInt(Short.MAX_VALUE);

           removed = ht.remove(removeMe);

       }

       hs.remove(removeMe);

       end = System.currentTimeMillis();

       System.out.println("done, removed=" + removeMe + ", time=" +

                          (end - start));

       System.out.print("Removing all occurrences of " + removeMe + "...");

       int removeCount = 1;

       while (ht.locate(removeMe) != null) {

           ht.remove(removeMe);

           removeCount++;

       }

       System.out.println("done, remove count=" + removeCount);

       System.out.print("Checking equivalence again...");

       start = System.currentTimeMillis();

       uniqueElementsEqual = MyHashTable.equalsUniqueElements(ht1, ht2);

       end = System.currentTimeMillis();

       unqiqueElementsEqualCorrect = hs1.equals(hs2);

       System.out.println("done, equivalence=" + uniqueElementsEqual +

                          ", time=" + (end - start) + ", result=" +

                          ((unqiqueElementsEqualCorrect == uniqueElementsEqual) ? "correct" : "incorrect"));

    }

}

MY HASH TABLE

import java.util.Iterator;

import java.util.NoSuchElementException;

/*

Give a comment block, if modifed.

*/

public class MyHashTable {

    // Give a comment block, if modified.

    private class MyHashTableItem {

        public boolean isValid = true;

        public E data;

        // Give a comment block, if modified.

        public MyHashTableItem(E inData) { data = inData; }

    }

    // Give a comment block, if modified.

    private int hash(T key) {

        return key.hashCode() % table.length;

    }

    private MyHashTableItem[] table; // Required

    private int num; // Required

    // Give a comment block, if modified.

    public MyHashTable(int inCapacity) {

        if (inCapacity < 0)

            throw new IllegalArgumentException();

        table = new MyHashTableItem[inCapacity];

    }

    // Give a comment block, if modified.

    public int size() { return num; }

    // Give a comment block, if modified.

    /**

     Improvement:

     A bucket which has been removed can also be used, so if bucket is invalid, add inObj there

     @param inObj object to be added to table

     @return true if inObj is added else false

     */

    public boolean add(T inObj) {

        int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;

        while (bucketsProbed < tableSize) {

            if (table[bucket] == null || !table[bucket].isValid) {

                table[bucket] = new MyHashTableItem(inObj);

                num++;

                return true;

            }

            bucket++;

            if (bucket == tableSize)

                bucket = 0;

            bucketsProbed++;

        }

        return false;

    }

    // Give a comment block, if modified.

    public boolean remove(T inObj) {

        int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;

        while (table[bucket] != null && bucketsProbed < tableSize) {

            if (table[bucket].isValid && table[bucket].data.equals(inObj)) {

                table[bucket].isValid = false;

                num--;

                return true;

            }

            bucket++;

            if (bucket == tableSize)

                bucket = 0;

            bucketsProbed++;

        }

        return false;

    }

    // Give a comment block, if modified.

    public T locate(T inObj) {

        int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;

        while (table[bucket] != null && bucketsProbed < tableSize) {

            if (table[bucket].isValid && table[bucket].data.equals(inObj))

                return table[bucket].data;

            bucket++;

            if (bucket == tableSize)

                bucket = 0;

            bucketsProbed++;

        }

        return null;

    }

    // Give a comment block, if modified.

    private class MyHashTableIterator implements Iterator {

        private int next = 0, tableSize;

        private MyHashTable myHt;

        // Give a comment block, if modified.

        public MyHashTableIterator(MyHashTable inHt) {

            myHt = inHt;

            tableSize = inHt.table.length;

            while (next < tableSize &&

               (myHt.table[next] == null ||

                myHt.table[next].isValid == false))

                next++;

        }

        // Give a comment block, if modified.

        public T next() {

            try {

                T retObj = myHt.table[next++].data;

                while (next < tableSize &&

                       (myHt.table[next] == null ||

                        myHt.table[next].isValid == false))

                    next++;

                return retObj;

            } catch (ArrayIndexOutOfBoundsException ex) {

                throw new NoSuchElementException();

            }

        }

        // Do not modify.

        public void remove() {

        /* No implementation */

            throw new UnsupportedOperationException();

        }

        // Give a comment block, if modified.

        public boolean hasNext() {

            return next < tableSize &&

                   myHt.table[next] != null &&

                   myHt.table[next].isValid != false;

        }

    }

    // Give a comment block, if modified.

    public Iterator iterator() {

        return new MyHashTableIterator<>(this);

    }

    // Give a comment block, if modified.

    public String toString() {

        String hashTableStr = "MyHashTable[size=" + num + ", ";

        Iterator itr = iterator();

        while (itr.hasNext()) {

            T obj = itr.next();

            hashTableStr += obj;

            if (itr.hasNext())

                hashTableStr += ", ";

        }

        hashTableStr += "]";

        return hashTableStr;

    }

    /**

     Iterate through inHt1

     Improvement: Use locate method instead of iterating through inHT2

     if unable to locate the element then return false else return true

     O(n) = n

     @param inHt1 HashMap to compare

     @param inHt2 HashMap to compare

     @param class of elements in HashMaps

     @return true if elements in inHt1 are same asinHt2 else false

     */

    public static boolean equalsUniqueElements(MyHashTable inHt1,

                                                   MyHashTable inHt2) {

        Iterator itr1 = inHt1.iterator();

        while (itr1.hasNext()) {

            T obj1 = itr1.next();

            if (inHt2.locate(obj1) == null)

                return false;

        }

        return true;

    }

}