Segmentation fault in hash table

Question

I don't understand why a segmentation fault is occurring in my program. Can someone explain the problem?

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
class HashTable {
private:
    int *A[1];
    int n;
    int bsize;
    vector<int> B;

public:
    HashTable(int size) {
        n = size;
        bsize = 0;
        *A = new int[n];
    }
    /*
    You should use another array B besides A. You do not initialize A, and thus the cells of A contain
    garbage initially. The array B is a std::vector which is initially empty. Use the same hash function
    h(x) = x. If A[x] contains i and B[i] contains x, it means that x exists in the hash table. If A[x]
    contains i but B[i] does not contain x or i is out of the range of B, it means that x does not exist in
    the hash table.
    */
    bool insert_hash(int x) {
        if (x >= n) {//sees if x is within the range of A
        } else {
            if (*A[x] > bsize){//sees if i is within the range of B
            } else {
                if (B[*A[x]] == x) {//sees if B[i] contains x

                    return false;
                }
            }

        }
        B.push_back(x);//adds key x to B
        bsize++;
        *A[x] = bsize;//store location at A
        return true;

    //The new key x should be pushed at the back of B and its location is stored at A[x]. This function
    //should return false if x already exists in the hash table, and returns true otherwise.
    }

    bool member_hash(int x) {
    //The function returns true if x exists in the hash table, and returns false otherwise.
        if (x <= n) {//sees if x is within the range of A
            if (*A[x] > bsize){//sees if i is within the range of B
                if (B[*A[x]] == x) {//sees if B[i] is x
                    return true;
                }
            }
        }
        return false;
    }

    bool delete_hash(int x) {
    //This function First checks whether x exists in the hash table: If no, then it returns false. Otherwise,
    //it stores -1 at the cell of B that contains x and then returns true.
        if (!member_hash(x)) {
            return false;
        } else {
            B[*A[x]] = -1;
            return true;
        }
    }
};

int main() {
    HashTable a(20);
    a.insert_hash(5);
    a.insert_hash(4);
    a.insert_hash(2);
    a.insert_hash(2);
    a.insert_hash(11);
    a.insert_hash(510);
    a.member_hash(11);
    a.delete_hash(11);
    a.member_hash(11);
    return 0;
}

I compiled the code just fine in DevC++ and also in Code::Blocks, but when I try to run this code, it ends up not responding, and when I run it on CodePad, I receive the message Segmentation Fault. Edit: To be more specific, it says "Segmentation fault (core dumped)" Edit 2: It seems that Segmentation fault begins at the first insert_hash in main, at the conditional statement (B[*A[x]] == x) Any ideas on how to solve this issue? Edit 3: B[*A[x]] == x, starting in member_hash, seems to cause it because B is empty. However, I am confused how the trash value in *A[x] gets to this condition, because I have other conditions (*A[x] < bsize) and (x < n) to guard against this. Solution?

Answer 1

int *A[1]; means you declare A as an array of one element of pointer to int.

Your array allocation compile but it's not good, your are allocating an array of int at an unknown address (as A[0] is undefined at this time)

If I correcly understand what you are trying to achieve, you want instead that A is an array of n elements of type int.

So I update your code accordingly :

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
class HashTable {
private:
    int *A;
    int n;
    int bsize;
    vector<int> B;

public:
    HashTable(int size) {
        n = size;
        bsize = 0;
        A = new int[n];
    }
    /*
    You should use another array B besides A. You do not initialize A, and thus the cells of A contain
    garbage initially. The array B is a std::vector which is initially empty. Use the same hash function
    h(x) = x. If A[x] contains i and B[i] contains x, it means that x exists in the hash table. If A[x]
    contains i but B[i] does not contain x or i is out of the range of B, it means that x does not exist in
    the hash table.
    */
    bool insert_hash(int x) {
        if (x >= n) {//sees if x is within the range of A
        } else {
            if (A[x] > bsize){//sees if i is within the range of B
            } else {
                if (B[A[x]] == x) {//sees if B[i] contains x

                    return false;
                }
            }

        }
        B.push_back(x);//adds key x to B
        bsize++;
        A[x] = bsize;//store location at A
        return true;

    //The new key x should be pushed at the back of B and its location is stored at A[x]. This function
    //should return false if x already exists in the hash table, and returns true otherwise.
    }

    bool member_hash(int x) {
    //The function returns true if x exists in the hash table, and returns false otherwise.
        if (x <= n) {//sees if x is within the range of A
            if (A[x] > bsize){//sees if i is within the range of B
                if (B[A[x]] == x) {//sees if B[i] is x
                    return true;
                }
            }
        }
        return false;
    }

    bool delete_hash(int x) {
    //This function First checks whether x exists in the hash table: If no, then it returns false. Otherwise,
    //it stores -1 at the cell of B that contains x and then returns true.
        if (!member_hash(x)) {
            return false;
        } else {
            B[A[x]] = -1;
            return true;
        }
    }
};

int main() {
    HashTable a(20);
    a.insert_hash(5);
    a.insert_hash(4);
    a.insert_hash(2);
    a.insert_hash(2);
    a.insert_hash(11);
    a.insert_hash(510);
    a.member_hash(11);
    a.delete_hash(11);
    a.member_hash(11);
    return 0;
}