Name your source code as .doc or docx (replace the text with With your last name

Question

Name your source code as .doc or docx (replace the text with With your last name and first name, in that order) and upload to blackboard. Use Open or Closed Hashing to store the following information in a hash table of your own size. The items are expected to consist of about 20 string values as the keys, with integers as the associated data. Implement a conversion into int from the key string value then store the value into the hash table (open or closed, your choice). Explain what you did and why you did it in an associated report. Attach your code to the report and submit as a word file Test your code with the following actions as inputs (program these in main) 1. create new hash table 2. input key, value {John, 1001} 3. input key value {Bob, 999} 4. input key value {Sue, 2012} 5. input key value {Mary, 101} 6. retrieve a inputs (one by one), outputting the key and value to standard output

Explanation / Answer

Here ,code uses open hashing to store and avoid collisons and reason to use it is open hashing defines each slot in the hash table to be the head of a linked list. All records that hash to a particular slot are placed on that slot's linked list. Open hashing is most appropriate when the hash table is kept in main memory, with the lists implemented by a standard in-memory linked list

package Chegg;

import java.util.ArrayList;
import java.util.Iterator;

// Class to represent entire hash table
public class HashTable<K, V> implements Iterable<HashTable.HashNode<K, V>> {
   // bucketArray is used to store array of chains
   private ArrayList<HashNode<K, V>> bucketArray;

   private int numBuckets;

   // Current size of array list
   private int size;

   static class HashNode<K, V> {
       K key;
       V value;

       HashNode<K, V> next;

       public HashNode(K key, V value) {
           this.key = key;
           this.value = value;
       }
   }

   public HashTable() {
       bucketArray = new ArrayList<>();
       numBuckets = 10;
       size = 0;

       for (int i = 0; i < numBuckets; i++)
           bucketArray.add(null);
   }

   public int size() {
       return size;
   }

   public boolean isEmpty() {
       return size() == 0;
   }

   // This implements hash function to find index
   // for a key
   private int getIndex(K key) {
       int hashCode = key.hashCode();
       int index = hashCode % numBuckets;
       return index;
   }

   // Returns value for a key
   public V get(K key) {
       // Find head of chain for given key
       int bucketIndex = getIndex(key);
       HashNode<K, V> head = bucketArray.get(bucketIndex);

       // Search key in chain
       while (head != null) {
           if (head.key.equals(key))
               return head.value;
           head = head.next;
       }

       // If key not found
       return null;
   }

   // Adds a key value pair to hash
   public void add(K key, V value) {

       int bucketIndex = getIndex(key);
       HashNode<K, V> head = bucketArray.get(bucketIndex);

       while (head != null) {
           if (head.key.equals(key)) {
               head.value = value;
               return;
           }
           head = head.next;
       }

       size++;
       head = bucketArray.get(bucketIndex);
       HashNode<K, V> newNode = new HashNode<K, V>(key, value);
       newNode.next = head;
       bucketArray.set(bucketIndex, newNode);

       // double the size if threshold value is reached
       if ((1.0 * size) / numBuckets >= 0.7) {
           ArrayList<HashNode<K, V>> temp = bucketArray;
           bucketArray = new ArrayList<>();
           numBuckets = 2 * numBuckets;
           size = 0;
           for (int i = 0; i < numBuckets; i++)
               bucketArray.add(null);

           for (HashNode<K, V> headNode : temp) {
               while (headNode != null) {
                   add(headNode.key, headNode.value);
                   headNode = headNode.next;
               }
           }
       }
   }

   @Override
   public Iterator<HashTable.HashNode<K, V>> iterator() {
       // TODO Auto-generated method stub
       Iterator<HashTable.HashNode<K, V>> it = new Iterator<HashTable.HashNode<K, V>>() {

           private int currentIndex = 0;

           @Override
           public boolean hasNext() {
               // TODO Auto-generated method stub
               return currentIndex < size && bucketArray.get(currentIndex) != null;
           }

           @Override
           public HashTable.HashNode<K, V> next() {
               // TODO Auto-generated method stub
               return bucketArray.get(currentIndex + 1);
           }

       };
       return it;
   }

   public static void main(String[] args) {
       HashTable<String, Integer> hashTable = new HashTable<>();
       hashTable.add("John", 1001);
       hashTable.add("Bob", 999);
       hashTable.add("Sue", 2012);
       hashTable.add("Mary", 101);

       for (Iterator<HashTable.HashNode<String, Integer>> iterator = hashTable.iterator(); iterator.hasNext();) {
           HashTable.HashNode<String, Integer> type = iterator.next();
           System.out.println(type.key + ":" + type.value);

       }

   }

}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.