Search code examples
c++hashtable

Am I Setting up this Hash Table Correctly?

I am in a data structures class and we are given a project regarding hash tables. An excerpt of the instructions I've been given are:

The hash table is an array of pointers to struct hash_table_entry all initialized to Nil.

So this is what I have written (again, an excerpt of the overall program):

hash_table_entry *hash_table = new hash_table_entry[hash_table_size];
for (int i=0;i<hash_table_size;i++)
{
    hash_table[i] = new hash_table_entry;
}

hash_table_entry is:

struct hash_table_entry{
char event_id; // Event id -- key used to hash on
int year; // Year of storm event
int event_index; // For the given year, the index into array of storm events };

So the questions I have are:

  1. hash_table is an array of type hash_table_entry pointer, correct?
  2. When the for loop runs through the array and creates a new hash_table_entry struct, are the default struct variables automatically set to "Nil"?

Thank you in advance for any insight!

Solution

  • hash_table is an array of type hash_table_entry pointer, correct?

    No, hash_table is a pointer to hash_table_entry, which after the given initialization with new hash_table_entry[hash_table_size]; will point to (the first element of) an array of hash_table_entry (not array to pointer to hash_table_entry).

    When the for loop runs through the array and creates a new hash_table_entry struct, are the default struct variables automatically set to "Nil"?

    As noted in the comments, the assignment

    hash_table[i] = new hash_table_entry;

    doesn't compile, because of a type mismatch. hash_table[i] has type hash_table_entry, while new hash_table_entry has type hash_table_entry*.

    But that aside, for the question of initialization: new hash_table_entry and new hash_table_entry[hash_table_size] (both creating objects or arrays of objects of type hash_table_entry) create objects. Because there is no initializer given in these expressions, the objects are default-constructed. Because hash_table_entry does not have any user-declared/defined constructors, this means that the implicitly defined default constructor will be used. This constructor does perform default-constuction of all members of hash_table_entry, which (because they are non-class types) means that nothing is done with them and therefore the members' values will remain indeterminate after the initialization.

    Whether this is what the assignment means with Nil is doubtful. Nil is not something that exists in C++ and so I assume that NULL or nullptr is meant and that you are supposed to allocate an array of pointers instead of objects and initialize them with null pointers.

    An array of pointers to hash_table_entry is allocated with new hash_table_entry*[hash_table_size] which results in a hash_table_entry**, not hash_table_entry*. If you add {} as in:

    new hash_table_entry*[hash_table_size]{}

    or more explicitly

    new hash_table_entry*[hash_table_size]{nullptr}

    it will also initialize all of the pointers to null pointers for you, no loop needed.