Author: Stan Eisenstat
Subject: Re: [Cs223] Chaining Question
Date: Sunday, 12 Apr 2020, 08:42:45

    > Message Posted By: Unknown
    >
    > 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.

Yes, but a simpler solution is to use an array of
structs for the hash table, with each struct containing
the number of triples stored in that chain and a pointer
to the block of storage containing the triples.

--Stan-