Question

Your task is to go through and implement the methods getBucketIndex, add, get, and remove. Follow the comments inside respective methods.

import java.util.ArrayList;
import java.util.Scanner;

public class HashtableChaining<K, V> {

   // Hashtable bucket
   private ArrayList<HashNode<K, V>> bucket;
   // Current capacity of the array list
   private int numBuckets;
   // current size of the array list
   private int size;
  
   public HashtableChaining(int buckets){
       bucket = new ArrayList<>();
       numBuckets = buckets;
       size = 0;
      
       // create empty chains
       for(int i = 0; i < numBuckets; i++){
           bucket.add(null);
       }
   }
  
   public int size(){
       return size;
   }
  
   public boolean isEmpty(){
       return size() == 0;
   }
  
   private int getBucketIndex(K key){
       // Implement Multiplicative hash
       // Assume INITIAL_VALUE = 7 HASH_MULTIPLIER = 3
   }
  
   //Adds a key value pair to hash
   public void add(K key, V value){
       // Find head of chain for given key
       // Check if key is already present
       // Insert key in chain
      
       // If load factor goes beyond threshold (0.75), then double the hash size
       // and rehash the existing items
       // print "Doubling the size, load factor > 0.75" when you double the hash size.
          
   }  
  
   // Returns value for a key
   public V get(K key){
       // Find head of chain for given key
       // Search key in chain
       // If key not found return null
      
       return null;
   }
  
   // Removes key from the hashtable
   public V remove(K key){
       // Apply hash function to find index for a given key
       // get head of the chain
       // Search for key in its chain
       // If key is found
       // Reduce size
       // Remove key and return      
       // Else keep moving in the chain
       //If key was not there return null

       return null;
      
   }
  

  

   public static void main(String[] args) {
       Scanner input = new Scanner(System.in);
       System.out.println("Enter the initial capacity:");
       int size = input.nextInt();
       HashtableChaining<String, Integer> hashtable = new HashtableChaining<>(size);

       System.out.println("Adding items to hashtable:");
      
       hashtable.add("FALL2017", 3);
       hashtable.add("SPRING2018", 3);
       hashtable.add("SUMMER2018", 1);
       hashtable.add("FALL2018", 4);
       hashtable.add("SPRING2019", 2);
       hashtable.add("SPRING2019", 3);

       System.out.printf("Size of the hashtable is %d%n", hashtable.size());
       System.out.println("Removing key SUMMER2018");
       System.out.printf("The value is %d%n", hashtable.remove("SUMMER2018"));
       System.out.printf("Now the size of the hashtable is %d%n",
               hashtable.size());
       System.out.println("Looking up key SUMMER2018");
       System.out.printf("The value is %s%n",
               hashtable.get("SUMMER2018"));
       System.out.printf("Is the hashtable empty? :%s%n",
               hashtable.isEmpty()? "True" : "False");

       input.close();
   }

}

Answer 1

import java.util.ArrayList;
import java.util.Scanner;

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 HashNode(K key, V value, HashNode<K, V> next) {
                this.key = key;
                this.value = value;
                this.next = next;
        }
}

public class HashtableChaining<K, V> {

        // Hashtable bucket
        private ArrayList<HashNode<K, V>> bucket;
        // Current capacity of the array list
        private int numBuckets;
        // current size of the array list
        private int size;

        public HashtableChaining(int buckets) {
                bucket = new ArrayList<>();
                numBuckets = buckets;
                size = 0;

                // create empty chains
                for (int i = 0; i < numBuckets; i++) {
                        bucket.add(null);
                }
        }

        public int size() {
                return size;
        }

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

        private int getBucketIndex(K key) {
                // Implement Multiplicative hash
                // Assume INITIAL_VALUE = 7 HASH_MULTIPLIER = 3
                return Math.abs(key.hashCode()) % numBuckets;
        }

        // Adds a key value pair to hash
        public void add(K key, V value) {
                // Find head of chain for given key
                // Check if key is already present
                // Insert key in chain
                
                // If load factor goes beyond threshold (0.75), then double the hash size
                // and rehash the existing items
                // print "Doubling the size, load factor > 0.75" when you double the hash size.
                
                if(size > 0.75 * numBuckets) {
                        ArrayList<HashNode<K, V>> oldbucket = bucket;
                        
                        bucket = new ArrayList<HashNode<K, V>>();
                        numBuckets = oldbucket.size() * 2;
                        size = 0;

                        // create empty chains
                        for (int i = 0; i < numBuckets; i++) {
                                bucket.add(null);
                        }
                        
                        for(HashNode<K, V> start : oldbucket) {
                                while(start != null) {
                                        add(start.key, start.value);
                                        start = start.next;
                                }
                        }
                }
                
                // add new node.
                if(get(key) != null) {
                        remove(key);
                }
                int index = getBucketIndex(key);
                bucket.set(index, new HashNode<>(key, value, bucket.get(index)));
                size++;
        }

        // Returns value for a key
        public V get(K key) {
                // Find head of chain for given key
                // Search key in chain
                // If key not found return null
                int index = getBucketIndex(key);
                HashNode<K, V> start = bucket.get(index);
                while(start != null) {
                        if(start.key.equals(key)) {
                                return start.value;
                        }
                        start = start.next;
                }

                return null;
        }

        // Removes key from the hashtable
        public V remove(K key) {
                // Apply hash function to find index for a given key
                // get head of the chain
                // Search for key in its chain
                // If key is found
                // Reduce size
                // Remove key and return
                // Else keep moving in the chain
                // If key was not there return null

                int index = getBucketIndex(key);
                HashNode<K, V> start = bucket.get(index);
                if(start != null) {
                        if(start.key.equals(key)) {
                                bucket.set(index, start.next);
                                size--;
                                return start.value;
                        } else {
                                HashNode<K, V> prev = start;
                                start = start.next;
                                
                                while(start != null && !start.key.equals(key)) {
                                        prev = start;
                                        start = start.next;
                                }
                                
                                if(start != null) {
                                        prev.next = start.next;
                                        size--;
                                        return start.value;
                                }
                        }
                }
                
                return null;
        }

        public static void main(String[] args) {
                Scanner input = new Scanner(System.in);
                System.out.println("Enter the initial capacity:");
                int size = input.nextInt();
                HashtableChaining<String, Integer> hashtable = new HashtableChaining<>(size);

                System.out.println("Adding items to hashtable:");

                hashtable.add("FALL2017", 3);
                hashtable.add("SPRING2018", 3);
                hashtable.add("SUMMER2018", 1);
                hashtable.add("FALL2018", 4);
                hashtable.add("SPRING2019", 2);
                hashtable.add("SPRING2019", 3);

                System.out.printf("Size of the hashtable is %d%n", hashtable.size());
                System.out.println("Removing key SUMMER2018");
                System.out.printf("The value is %d%n", hashtable.remove("SUMMER2018"));
                System.out.printf("Now the size of the hashtable is %d%n", hashtable.size());
                System.out.println("Looking up key SUMMER2018");
                System.out.printf("The value is %s%n", hashtable.get("SUMMER2018"));
                System.out.printf("Is the hashtable empty? :%s%n", hashtable.isEmpty() ? "True" : "False");

                input.close();
        }

}

please upvote.