Why do I need double pointers for an array of objects? HashMap Example in C++

Question

I am practicing some C++ and I was confused about why I need double pointers for an array of objects(such as a node struct). Here is a simple code snippet to explain my situation:

struct HashNode{

    HashNode* next;
    int data;
    int key;
    int hashCode;

    HashNode::HashNode(
        HashNode* next, 
        const int& data, 
        const int& key, 
        const int& hashCode
        ) : next(next), data(data), key(key), hashCode(hashCode)
        {}

};

class HashMap{
    public:
        HashMap();
        HashMap(int tableSize);
        ~HashMap();

    private:
        //Here is the double pointer
        HashNode** table;
};

HashMap::HashMap(){
    //Here is the array initialization 
    table = new HashNode*[100];
}

I have removed the code that is unnecessary for the question.

If I remove the double pointer as such:

HashNode* table;

and

table = new HashNode[100];

I get the following error.

hashmap.cpp: In method `HashMap::HashMap()':
hashmap.cpp:87: no matching function for call to `HashNode::HashNode ()'
hashmap.cpp:61: candidates are: HashNode::HashNode(const HashNode &)
hashmap.cpp:58:                 HashNode::HashNode(HashNode *, const int &, cons
t int &, const int &)

which shows me that the HashNode tries to run a constructor.

If I change only the initialization of the array as table = new HashNode*[100]; while keeping HashNode* table; then I get the following error.

hashmap.cpp: In method `HashMap::HashMap()':
hashmap.cpp:87: assignment to `HashNode *' from `HashNode **'

My assumption is that when I make an array of objects, I need the lifetime of the objects to be for the duration of the program as well. This requires me to use pointers for the objects as well as the array. Therefore, I need to have double pointers for the array since it points to pointers and I need pointers for the objects.

However, I am still unsure and I cannot really find any good explanations online. Could someone please explain this situation?

Answer 1

This implementation uses separate chaining with linked lists for managing hash collisions. Therefore, table is an array of pointers to HashNode, meaning that it needs two asterisks:

• One asterisk comes from the type of array element, which is HashNode*
• The other asterisk comes from making an array of HashNode*

That is also why you have an asterisk in the new expression:

table = new HashNode*[100];
//                  ^