Question

Design a primary hash table data structure. a. Each hash table has an array of node pointers and can point a head of a linked list. Suppose the node class is given to you. The data type of each node is int. b. Override the default constructor with a constructor that has one default parameter called capacity. What happens to your default constructor? Create some instances of the sequence class using the new constructor in multiple ways. c. Design the insert function that accept a value and inserts the value in the index of value%(size of table). Try to be efficient. d. Design a search function that accepts a value and checks to see if it is inside the table, if it is there it return true. e. Design a remove function to remove a value from the table. f. Overload + and - operators for hash table such that you may insert or remove a new integer to the hash table using this operator. g. overload >> operator for hash table such that it accepts a hash table and it inserts the element from the input into the table. h. Explain why the value semantics of your hash table class is not safe to use? Make the value semantics safe to use. i. Explain what is the running time of each function.

Answer 1

public class HashEntry {

      private int key;

      private int value;

      HashEntry(int key, int value) {

            this.key = key;

            this.value = value;

      }     

      public int getKey() {

            return key;

      }

      public int getValue() {

            return value;

      }

}

public class HashMap {

      private final static int capacity = 128;

      HashEntry[] table;

      HashMap() {

            table = new HashEntry[capacity];

            for (int i = 0; i < capacity; i++)

                  table[i] = null;

      }

      public int get(int key) {

            int hash = (key % capacity);

            while (table[hash] != null && table[hash].getKey() != key)

                  hash = (hash + 1) % capacity;

            if (table[hash] == null)

                  return -1;

            else

                  return table[hash].getValue();

      }

      public void put(int key, int value) {

            int hash = (key % capacity);

            while (table[hash] != null && table[hash].getKey() != key)

                  hash = (hash + 1) % capacity;

            table[hash] = new HashEntry(key, value);

      }

}