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-PREV INDEX NEXT