chashmaphashtablehashsetunsigned

runtime error because of " unsigned int "


trying to solve 217. Contains Duplicate in C with HashSet.

after i tried to make the calculated index to be always (+) i get an error.


#define BUCKET_SIZE 1000

typedef struct ListNodes {
  int val;
  struct ListNodes* next;
} ListNode;

typedef struct {
  ListNode* buckets[BUCKET_SIZE];
} MyHashSet;

// create hash table
MyHashSet* myHashSetCreate() {
    MyHashSet* obj = (MyHashSet*) malloc(sizeof(MyHashSet));
    for(int i = 0 ; i < BUCKET_SIZE ; i++ ) {
        obj -> buckets[i] = NULL;
    }
    return obj;
}

bool myHashSet(MyHashSet* obj, int key) {
    unsigned int index =  key % BUCKET_SIZE; // problem here
    ListNode* current = obj->buckets[index];
    while(current != NULL) {
        if(current -> val == key) return true;
        current = current -> next;
    } 
    
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = key;
    newNode->next = obj->buckets[index];
    obj->buckets[index] = newNode;
    return false;
}

// task function

bool containsDuplicate(int* nums, int numsSize) {
     MyHashSet* obj = myHashSetCreate();
     for(int i = 0 ; i < numsSize ; i++) {
        if(myHashSet(obj, nums[i])) {
            return true;
        }
     }
    return false;
}


unsigned int index = key % BUCKET_SIZE;

result :

Line 23: Char 15: runtime error: load of address 0x6258000078f0 with insufficient space for an object of type 'struct ListNode *' [solution.c] 0x6258000078f0: note: pointer points here

ListNode* current = obj->buckets[index];

i fixed the bug by :

int index = key % BUCKET_SIZE;

or

int index =  key % BUCKET_SIZE;
    if( index < 0) {
        index *= -1;
    }

any idea why the code behave weirdly ?


Solution

  • Avoid signed math:

    bool myHashSet(MyHashSet* obj, int key) {
        unsigned int index =  key % BUCKET_SIZE;
    

    change to

    bool myHashSet(MyHashSet* obj, unsigned key) {
        unsigned int index =  key % BUCKET_SIZE;
    // or 
    bool myHashSet(MyHashSet* obj, int key) {
        unsigned int index =  (unsigned) key % BUCKET_SIZE;
    // or 
    // #define BUCKET_SIZE 1000
    #define BUCKET_SIZE 1000u
    // or ...
    

    With original unsigned int index = key % BUCKET_SIZE;, key % BUCKET_SIZE computes the remainder which is in the -999 to 999 range. Converting a negative number to unsigned makes for large unsigned vales.