0
\$\begingroup\$

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();
        }
    }
};
\$\endgroup\$
  • \$\begingroup\$ @jamal the code works \$\endgroup\$ – mello Feb 3 '17 at 2:48
  • \$\begingroup\$ You're also asking some off-topic questions, particularly ones regarding adding new code. \$\endgroup\$ – Jamal Feb 3 '17 at 2:50
  • \$\begingroup\$ are you talking about the comment in the code ? \$\endgroup\$ – mello Feb 3 '17 at 2:51
  • \$\begingroup\$ Yes, and some below the code, such as making keys unique and implementing a generic hash function. \$\endgroup\$ – Jamal Feb 3 '17 at 2:53
  • \$\begingroup\$ i removed all comments \$\endgroup\$ – mello Feb 3 '17 at 2:56
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ can i add the changes onto the original question ? so you could tell me if i have done them right \$\endgroup\$ – mello Feb 6 '17 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.