In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #11 exercise sheet]

[AED067] Hash Tables with Separate Chaining

In this problem you should only submit a hashTableSC.h file with a self-containing definition of a class HashTableSC<KeyType>

Base Code

Use as a basis the skeleton code of HashTableSC<KeyType> (see code | download code) which provides the initial code for a basic implementation of an hash table using separate chaining for collision resolution.

The Problem

Implement the following 3 methods (which already exist on the given file, but still lack functional code):

• bool contains(const KeyType & k) should return true if the key k exists in the hash, and false otherwise.
• bool insert(const KeyType & k) should try to insert the key k in the hash table, returning true when successful (the key was inserted) and false otherwise (the key was not inserted because it already existed). The key should be inserted at the end of the list of the respective bucket.
• bool remove(const KeyType & k) should try to remove the key k in the hash table, returning true when successful (the key was removed) and false otherwise (the key was not removed because it did not exist). When removing a key, the rest of the list of the respective bucket should not change.

In all methods, to find the corresponding position (bucket) on the table, use modular hashing over the hash function of the class (that was initialized on the constructor), that is, for key k the position can be found calling hash(k) % size.

On methods insert and remove, don't forget to update the numberKeys variable to reflect the change on the number of inserted keys.

Submission

You should submit the file hashTableSC.h with the methods contains, insert and remove implemented as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, construct the hash table, read the operations and call your methods, printing its result.

#include <string>
#include "hashTableSC.h"

// Read hash table and then q operations
template <typename KeyType>
void read() {
  int n;
  std::cin >> n;
  std::hash<KeyType> h;
  HashTableSC<KeyType> hashTable(n, h);

  int q;
  std::cin >> q;
  for (int i=0; i<q; i++) {
    std::string op;
    KeyType k;
    std::cin >> op;
    if (op == "CONTAINS") {
      std::cin >> k;
      std::cout << "contains(" << k << "): " << hashTable.contains(k) << std::endl;
    } else if (op == "INSERT") {
      std::cin >> k;
      std::cout << "insert(" << k << "): " << hashTable.insert(k) << std::endl;
    } else if (op == "REMOVE") {
      std::cin >> k;
      std::cout << "remove(" << k << "): " << hashTable.remove(k) << std::endl;
    } else if (op == "SHOW") {
      std::cout << "showContents():" << std::endl;
      hashTable.showContents();
    }
  }
}

int main() {

  std::string type;
  std::cin >> type;
  if (type == "int") read<int>();
  else if (type == "string") read<std::string>();
  
  return 0;
}

int 5
17
INSERT 42
INSERT 17
INSERT 12
INSERT 31
INSERT 42
CONTAINS 17
CONTAINS 52
SHOW
INSERT 45
INSERT 52
INSERT 13
REMOVE 17
REMOVE 31
REMOVE 31
CONTAINS 17
CONTAINS 52
SHOW

insert(42): 1
insert(17): 1
insert(12): 1
insert(31): 1
insert(42): 0
contains(17): 1
contains(52): 0
showContents():
Size: 5 | Number of keys: 4 | Load Factor: 0.800
0: EMPTY
1: 31
2: 42 17 12
3: EMPTY
4: EMPTY
insert(45): 1
insert(52): 1
insert(13): 1
remove(17): 1
remove(31): 1
remove(31): 0
contains(17): 0
contains(52): 1
showContents():
Size: 5 | Number of keys: 5 | Load Factor: 1.000
0: 45
1: EMPTY
2: 42 12 52
3: 13
4: EMPTY

Explanation of the Example Input:

An empty hash table is initially created with 5 buckets. Afterwards:

• 42 is successfully inserted at bucket 2
• 17 is successfully inserted at bucket 2
• 12 is successfully inserted at bucket 2
• 31 is successfully inserted at bucket 1
• 42 is not inserted (it already existed)
• contains(17) is true because 17 is on table
• contains(52) is false because 52 is not on table
• The contents of the hash table are shown and correspond to the following 4 keys inserted:
  
• 45 is successfully inserted at bucket 0
• 52 is successfully inserted at bucket 2
• 13 is successfully inserted at bucket 3
• 17 is successfully removed from bucket 2
• 31 is successfully removed from bucket 1
• 31 is not removed (it was not on the table)
• contains(17) is false because 17 is not on table
• contains(52) is true because 52 is on table
• The contents of the hash table are shown and correspond to the following 5 keys inserted: