Hash Table or map implementation

Question

I'd like to get feedback on whether my hash table is correct or not. Also, any ideas on performance?

 template<class J,class K>
class List {
private:
 struct Node {
 J key;K data;
 Node * next;
 Node(J _key,K _data):key(_key),data(_data),next(nullptr) {}
 }*head;
public:
 List():head(nullptr){}
 ~List() {
 deleteNode();
 }
 void insert(J _key ,K _data) {
 Node * newNode = new Node(_key, _data);
 newNode->next = head;
 head = newNode;
 }
 void traverse() {
 for(Node * curr = head; curr != nullptr; curr = curr->next) {
 cout<< "( "<<curr->key << ", " << curr->data << " )" << " ";
 }
 }
 K search(J key) {
 if (!empty()){
 for(Node * curr = head;curr != nullptr;curr = curr->next) {
 if (curr->key == key) {
 return curr->data;
 }
 }
 }
 return K(-1);
 }
 bool empty() { return (head == nullptr); }
 void deleteNode() {
 Node * tmp = nullptr;
 for(Node * curr = head; curr != nullptr;){
 tmp = curr->next;
 delete curr;
 curr = tmp;
 }
 }
};
template<class KEY, class VALUE>
class myHash {
private:
 struct bucket {
 List<KEY,VALUE> list_at_bucket;
 }*Buckets;
 int tableSize;
public:
 myHash(int size) {
 tableSize = size;
 Buckets = new bucket[tableSize];
 }
 ~myHash() {
 for(int i = 0; i < tableSize; i++) {
 Buckets[i].list_at_bucket.deleteNode();
 }
 }
 void put(KEY k, VALUE value) {
 int getCode = hash(k);
 Buckets[getCode].list_at_bucket.insert(k,value);
 }
 VALUE getValue(KEY _key) {
 int getCode = hash(_key);
 return Buckets[getCode].list_at_bucket.search(_key);
 }
 bool contains(KEY _key) {
 int getCode = hash(_key);
 if (Buckets[getCode].list_at_bucket.search(_key) != -1) {
 return true;
 }
 return false;
 }
 // need a template hash function
 int hash(KEY key) const {
 int value = 0;
 for (char each: key) {
 value += each;
 }
 return value % tableSize;
 }
 void traverse() {
 for (int index = 0; index <tableSize; index++){
 cout<< "[" << index << " ]-> ";
 Buckets[index].list_at_bucket.traverse();
 }
 }
};

• mello: @jamal the code works
• Jamal: You're also asking some off-topic questions, particularly ones regarding adding new code.
• mello: are you talking about the comment in the code ?
• Jamal: Yes, and some below the code, such as making keys unique and implementing a generic hash function.
• mello: i removed all comments

Answer 1

Well, there's a lott to say:

1. K and V are the traditional template-arguments for keys and values in C++.
   Why do you use J and K respectively KEY and VALUE instead?

2. List::Node is only instantiated at one place, where all three members are set. Why then does it have a constructor at all, and one setting the last one to nullptr at that?

3. Default copy- and move- construction and assignment are completely unsuited to your List, as it owns its nodes. Leaving them leads to double-deletes and abandoned nodes. Look at the rule of three.

   Also worth a look are inclass-initializers (for head).

4. deleteNode looks more like reset, and should zero head or be inlined into the destructor. As-is, it leaves head dangling...

5. The same comments apply to copying / moving / assigning myHash as to List.

6. The myHash dtor leaks the array of buckets...

7. contains should return the condition directly, instead of putting it into an if-clause. if(somebool) return true; else return false; is a bit wordy.

8. Your traverse-functions would be more appropriately named dump or some such... Anyway, why don't you overload operator>>(std::ostream, yourtypehere) instead?

9. Your hash-function runs afool of the fact that only the type itself can know which parts are relevant and how to hash them. Take a look at the design of std::hash.

10. Next, I would suggest embracing auto, see Almost Always Auto.

• mello: can i add the changes onto the original question ? so you could tell me if i have done them right