0

I was given an assignment to create a hash table that contains 30 buckets (20 primary, and 10 overflow), with each bucket containing 3 slots (each slot containing 2 stings for key and data passed in), a counter integer and a pointer variable that points to the next overflow bucket. My last C++ class was over a year ago so I'm completely lost as to how I am supposed to create this table properly (with no help from my professor).

This is my class declaration below. It technically compiles, however it crashes immediately, and when it debugs, I get an "Access Violation Reading Location" error stating "this was nullptr" on my home computer (and it includes a specific memory location on the computer I used in class).

#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

// Define Global Variables
#define MAXBUCKETs 30
#define MAXSLOTs 3
typedef char STR10[10 + 1];
typedef char STR20[20 + 1];

// Define Class
class hash{

public:

    int primaryBuckets = 20;
    int overflowBuckets = 10;

    union bucket
    {
        int count;
        bucket* nextOverflow;

        struct slot {
            string keyValue;
            string dataValue;
        };

        slot* slots[2];

    } HashTable[30];

    hash();                                         // Initialize HashTable
    int HashFunction(STR10 key, int buckets);       // Hash key to index
    void InsertIntoHT(STR10 key, STR20 data);       // Add data to slot
    void PrintItemsInIndex();
    void InsertOverflow(STR10 key, STR20 data, int index);
    void InsertPrimary(STR10 key, STR20 data, int index);
};

My constructor, from what I understand, initialized the array in the right order

::hash::hash()
{


    for (int i = 0; i < MAXBUCKETs; i++)
    {
        HashTable[i].count = 0;
        for (int j = 0; j < MAXSLOTs; j++)
        {
            HashTable[i].slots[j]->keyValue = "no_data";
            HashTable[i].slots[j]->dataValue = "no_data";
        }
    }
}

I'm pretty desperate for help at this point. I'm almost certain it's a bad pointer, but I've never understood them well. All help will be greatly appreciated! (This is also my first post so hopefully I didn't do anything wrong)

Thomas Shaw
  • 1
  • 2
  • `slot* slots[2];` should be `slot* slots[MAXSLOTs];` You used a magic number of 2 then set `MAXSLOTs` to 3. You should avoid these magic numbers.. – drescherjm Feb 10 '18 at 17:52
  • Also `HashTable[30];` should be `HashTable[MAXBUCKETs]` – drescherjm Feb 10 '18 at 17:53
  • 1
    Sorry to say it, but the code's a mess. For a start, `union`s are weird things: they can only store one of the listed members at a time: you should use a `struct` instead. Then, `slots` are pointers - you can't dereference them to access `keyValue` and `dataValue` until you've pointed them at some properly allocated memory: use `new`. – Tony Delroy Feb 10 '18 at 17:54
  • There is no need to be sorry, it really is a mess. I toyed around with structs however I'm not sure how I can hold 3 slots within a struct. Is it possible to hold 3 slots, a pointer and an int in a struct? – Thomas Shaw Feb 10 '18 at 17:57
  • ***Is it possible to hold 3 slots, a pointer and an int in a struct*** Yes of course. – drescherjm Feb 10 '18 at 17:57
  • You can have any number of members in a struct, as long as memory permits. – Olaf Dietsche Feb 10 '18 at 17:57
  • Ok, thank you everybody for your answers, I'm grasping this a little more now. Tony, when you say use new, how would I go about that? Should I make HashTable[i] = new slot; ? – Thomas Shaw Feb 10 '18 at 18:05

1 Answers1

0

Maybe I misunderstand this, but the union looks suspicious

union bucket
{
    int count;
    bucket* nextOverflow;

    struct slot {
        string keyValue;
        string dataValue;
    };

    slot* slots[2];

} HashTable[30];

A union is supposed to hold only one of its members, in this case one of

  • count
  • nextOverflow
  • slots[2]

Maybe a struct bucket is more appropriate.

Specifically, 

HashTable[i].count = 0;

sets count member to zero, and at the same time overwrites memory of slots, which holds a pointer to a slot entry

HashTable[i].slots[j]->keyValue = "no_data";

Here you must either use plain slot objects, which I recommend, e.g.

slot slots[MAXSLOTs];

or first initialize with new

for (int i = 0; i < MAXSLOTs; ++i)
    slots[i] = new slot;
Olaf Dietsche
  • 72,253
  • 8
  • 102
  • 198
  • I landed on a union because I figured my original problem was stemming from trying to access my slot struct members from within an array struct pointers. I just changed it back to struct bucket, but I'm now getting an access violation at 0xCCCCCCCC – Thomas Shaw Feb 10 '18 at 18:02
  • Where do you get this access violation? Have you also changed `slots[2]` to `slots[MAXSLOTs]`, because 2 != MAXSLOTs? – Olaf Dietsche Feb 10 '18 at 18:04
  • Yes, I have changed slots[2] to MAXSLOTs, and HashTable[30] to HashTable[MAXBUCKETs]. Visual Studio is debugging it and it's not giving me a specific location. – Thomas Shaw Feb 10 '18 at 18:08
  • `0xCCCCCCCC` means uninitialized stack memory. https://stackoverflow.com/a/127404/487892 – drescherjm Feb 10 '18 at 18:10
  • Thank you for the help Olaf! I tried to change my "struct slot" to a slot object, but I can't find any resources regarding accessing slot objects. When I tried to create a new slot struct using this: HashTable[i].slots[j] = new slot; I get a "syntax error: identifier 'slot'" – Thomas Shaw Feb 11 '18 at 19:21
  • There's no need to allocate with `new slot`, when you use objects instead of pointers. Accessing is done with the dot operator `.` instead of `->`, e.g. `HashTable[i].slots[j].keyValue = "no_data";` – Olaf Dietsche Feb 11 '18 at 19:40
  • Olaf, you are incredible! Thank you so much for everything, that was exactly what I was doing wrong. I changed to a slot object and used the dot operator and the program runs as it should. I really appreciate your patience and help! – Thomas Shaw Feb 13 '18 at 02:00
  • Great, I'm glad it helped. – Olaf Dietsche Feb 13 '18 at 09:23