Garbage values are being initialized as the values of my hash table even though I specifically code all indices to -1

Question

I don't know if I'm missing something very simple but I'm having trouble initializing all values of my empty hash table to -1. I have an another array with the ID numbers (that I will hash). I'm initializing all values to -1 because I can check later if the value of my hash array is -1 then I can insert without quadratically probing.

In my constructor, I initialize the table size. Then I create an array with that size. Then I point my private pointer to that array so I'll always have access to it. From there, I initialize my table... And I have a question about the for loop in my constructor:

Does it matter if i do arr[i] = -1 or table[i] = -1? Because table points to all of the indices right? and arr[] obviously can access it's own indices. So I don't see why either way it matters.

If somebody could enlighten me that would be great. Thanks.


HashTable::HashTable(int bsize)
{
    this->tableSize= bsize; 
    int arr[bsize]; //creating an array to hold hash values 
    table = arr; //table pointer points to our new array
    for(int i = 0; i < bsize; i++){ 
        table[i] = -1; 
    }
}

void  HashTable:: printTable(){
    for(int i = 0; i < tableSize; i++){
        cout << table[i] << endl;
    }
}

Here's my class

class HashTable
{
    int tableSize = 40009;  // No. of buckets
    
    // Pointer to an array containing buckets
    int *table;
    int numOfcolision =0;
public:
    HashTable(int bsize);  // Constructor

    // inserts a key into hash table
    bool insert(int key);

    // hash function to map values to key
    unsigned int hashFunction(int key);

    void printTable();
    int getNumOfCollision();

    int search(int key);
};

Your array is a VLA, which is illegal. Use a `vector` instead. — cigien, Nov 28 '20 at 18:37
`int arr[bsize]; //creating an array to hold hash values` -- Please `g++` engineers, in future versions of your compiler, I beg you to change your default settings to not accept this as valid. — PaulMcKenzie, Nov 28 '20 at 18:40
@cigien For the purpose of my assignment I cannot use vectors. — , Nov 28 '20 at 18:49
@Esau *For the purpose of my assignment I cannot use vectors* -- If your assignment is so restrictive, then using fake C++ as you are doing now would be even more forbidden. At least `std::vector` is actual C++. — PaulMcKenzie, Nov 28 '20 at 18:55
Yeah. Are you suggesting that I could make arr[] on the heap so I don't lose it when the constructor returns? If I catch your drift.. I'm also considering declaring arr[tablesize] as a private variable in my class too. — , Nov 28 '20 at 18:56
@PaulMcKenzie not sure if I understood your comment about g++ in my compiler. What exactly did you mean? Sorry if this is a dumb question I'm a relatively new to coding. — , Nov 28 '20 at 18:59
@PaulMcKenzie not 100% sure if we're NOT allowed to use vectors I just assumed we can't. I can check with my TAs. Don't blame them — , Nov 28 '20 at 19:00
*I'm also considering declaring arr[tablesize]*. There is no such thing as variable length arrays in C++. As to the comment about g++, that compiler has by default, the usage of VLA's in a C++ program turned *on*. I wished they would turn it off by default, as new programmers get fooled into thinking their C++ code is valid, when it isn't valid. You take that same program and attempt to compile it with Visual C++, it will get rejected, and rightly so. — PaulMcKenzie, Nov 28 '20 at 19:03
@PaulMcKenzie ah ok I understand your point now. So it's bad practice and technically illegal to do int size = 10 and then int arr[size]? I've done this in the past in VS code and it compiles fine but I didn't know that it's bad practice — , Nov 28 '20 at 19:10
@PaulMcKenzie *I'm also considering declaring arr[tablesize].* This didn't up working for the reason you said. What did work is this : const static int tableSize = 40009; int arr[tableSize]; — , Nov 28 '20 at 19:16
Probably you did `const int size = 10;` -- That will always work, since `size` is `const`. Just stating `int size = 10;` has never worked for Visual C++, and will only work if or when the C++ standard committee approves of runtime values being used for array sizes. — PaulMcKenzie, Nov 28 '20 at 19:16
@PaulMcKenzie no I just tested it. I did this: `int size = 10; int array[size]; for(int w = 0; w < 10; w++){ cout << array[w] << " "; } cout << endl;` and it gave my garbage values of course but it worked. Sorry about the formatting in the comment. — , Nov 28 '20 at 19:18
You didn't use Visual C++. [See this](https://godbolt.org/z/h13Enb) and [this](https://godbolt.org/z/n11jhb) — PaulMcKenzie, Nov 28 '20 at 19:26

score 3 · Accepted Answer · answered Nov 28 '20 at 18:40

In your constructor:

int arr[bsize]; //creating an array to hold hash values

This is non-standard C++. Variable-length arrays are not standard C++. In standard C++ all array sizes are constant which are determined at compile time and not runtime. But, more importantly, is that this is a local variable in the constructor.

table = arr; //table pointer points to our new array

table is, presumably, a pointer class member. This initializes the class member to point to a local array in the constructor.

But as soon as the constructor returns, the array is destroyed, like all other variables that are local to function where they get declared. Using the pointer in the class member becomes undefined behavior, which manifests, for you, as random garbage.

Arrays don't work like this, in C++. You will need to replace the pointer/array hybrid in your class with a std::vector. You will find more information on how to use std::vector, and many examples of using them, in your C++ textbook.

In this case I will initialize arr[] as a private variable. I can't use vectors for this assignment. Thanks for the help this really clears up my problem! — , Nov 28 '20 at 18:54

Garbage values are being initialized as the values of my hash table even though I specifically code all indices to -1

1 Answers1