Hello. I'm in a Data Structures class in a group of 3. My group members are rarely online to discuss anything, they just push and pull from git, so I can't really ask them for help right away.
We are assigned to fill in the TODO'S left by our professor for a hash table. I have to do the hash function and the count elements function. I believe I got the hash function down, but how do I go about counting elements
I watched some videos and tried to draw out pictures and in psuedo code
So I got first a for loop and loop through depending on the table's size
At that element in the table, if the size there is = 1, meaning one element, we add to a variable "count" once
If its greater then one, it means theres a collision so there's a linked list. So we would have to make a pointer I believe and check if its anull, and keep going through the list until its not NULL, counting each time, right?
IF its 0, we do nothing since it means its empty
Here's my code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
size_t hashTbl::countElements() const
{
/* TODO: write this */
size_t count = 0;
for(unsigned int i = 0; i < TLEN; i++) {
if(table[i].size() == 1) {
count++;
}
else if(table[i].size() > 1) {
//initialize a pointer?? Not sure
//Then I check if the first element is NULL
//While its not NULL, count++ and move to the next node
//End when we reach NULL
;
}
else; //If it equals 0, do nothing.
}
return count;
}
| |
Here's the public and private
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
public:
/* see the readme for these parameters. if the pointer
* params are null, then the constructor should randomly
* assign them. the hash function will have codomain
* 0,...,2^rangebits - 1 */
hash(unsigned rangebits = 64, const uint32_t* a = 0,
const uint64_t* alpha = 0, const uint64_t* beta = 0);
uint64_t operator()(const string& x) const;
static const size_t aLen = 32; /* we can only hash 128 byte strings */
unsigned rangebits;
uint32_t a[aLen]; /* vector for initial hash */
uint64_t alpha; /* for second hash */
uint64_t beta; /* for second hash */
};
private:
list<val_type>* table; /* array to hold the linked lists */
unsigned nBits; /* size of hash table == 2^nBits */
hash h; /* instance of hash function */
}
| |
Am I on the right track? Any help is appreciated, thanks.