Implement hash-table in C++

Question

The following is the implementation of hashtable using C++. Can you please help me to understand what HashEntry **table is? Why it is declared as a double pointer? Is it a array and each value of the array is HashEntry?

  class HashEntry {
    private:
          int key;
          int value;
    public:
          HashEntry(int key, int value) {
                this->key = key;
                this->value = value;
          }

          int getKey() {
                return key;
          }

          int getValue() {
                return value;
          }
    };

    const int TABLE_SIZE = 128;






    class HashMap {
    private:
          HashEntry **table;
    public:
          HashMap() {
                table = new HashEntry*[TABLE_SIZE];
                for (int i = 0; i < TABLE_SIZE; i++)
                      table[i] = NULL;
          }

          int get(int key) {
                int hash = (key % TABLE_SIZE);
                while (table[hash] != NULL && table[hash]->getKey() != key)
                      hash = (hash + 1) % TABLE_SIZE;
                if (table[hash] == NULL)
                      return -1;
                else
                      return table[hash]->getValue();
          }

          void put(int key, int value) {
                int hash = (key % TABLE_SIZE);
                while (table[hash] != NULL && table[hash]->getKey() != key)
                      hash = (hash + 1) % TABLE_SIZE;
                if (table[hash] != NULL)
                      delete table[hash];
                table[hash] = new HashEntry(key, value);
          }     

          ~HashMap() {
                for (int i = 0; i < TABLE_SIZE; i++)
                      if (table[i] != NULL)
                            delete table[i];
                delete[] table;
          }
    };

Answer 1

In this code, table is a pointer to a pointer to HashEntry

HashEntry **table;

The general rule is to start with the variable name and the basic type, go right as much as possible then go left, see this excellent description

http://unixwiz.net/techtips/reading-cdecl.html

So you start with the variable, table, and the basic type, HashEntry which is furthest to the left. Note that the article describes the rules for 'C' where a basic type can be a struct, think of your C++ class HashEntry as a 'C' struct.

table is ... HashEntry

There is nothing else to the right of table in the declaration, so go left, and you have "*" which stands for pointer to:

table is pointer to ... HashEntry

Again you must go left in the declaration and consume the next "*", you now have

table is pointer to pointer to HashEntry

... and you are done.

It is perhaps unfortunate that table was declared that way, because table implies array, and it is not declared as an array. It turns out that in C++, as in C, an array "decays" into a pointer when it is passed to a function. Here "decays" means you have lost information, namely the size of the array.

An equivalent declaration, which I think would give the reader more insight would be:

HashEntry * table[];

Using the rules about how to interpret variable declarations, this should be read as

table is undimensioned array of pointer to HashEntry

This is equivalent from the compiler's point of view to the previous declaration, because an undimensioned array is passed as a pointer to the type of the elements of the array (the value being the address of the first element, at offset 0). A "dimensioned array" also decays to a pointer, with the loss of the dimension information. See this SO answer for more information on decaying of arrays to pointers.

What is array decaying?