Author: Unknown
Subject: Chaining Question
Date: Saturday, 11 Apr 2020, 18:28:16

Our hash table is an array of "chains" (also arrays) which are to be dynamically allocated for each insert. Are we allowed to store the size of each chain in the first element of the chain (kind of like a head node containing information about the length of a list) to make dynamic allocation easier? i.e. when creating the table set each element of the table to an array of 1 triple, setting nSteps in that triple to be zero, and incrementing nSteps of the first triple every time an insert is made in that chain?

To make it more clear: say two strings hash to index i in the search table and are inserted there. Then index i of the search table would contain an array of THREE triples, the first of which contains the length of the chain in its nSteps field (so table[i][0]->nSteps = 2), and the two subsequent elements are the two inserted strings. Would that be okay? or is there an easier way to dynamically reallocate the chains.

Thanks!