Implementing Hash Table in C

Question

The code under discussion is to check whether or not two arrays are equal. There are several ways of solving this question, hashing being one of them. I've tried to implement the same. If the inputs are in the range of 1 to 9 then I get a correct output. But if the inputs are above 100 then there is a segmentation fault error. How do I solve this error?

Thanks in advance.

Here's the code for your reference:

#include<stdio.h>
int main()
{
  int a[5],b[5],i,f=0;
  int freq[5]={0};

  printf("Enter elements for first array\n");
  for(i=0;i<5;i++)
    scanf("%d",&a[i]);
  printf("\nEnter elements for second array\n");
  for(i=0;i<5;i++)
    scanf("%d",&b[i]);

  for(i=0;i<5;i++)
    freq[a[i]]++;

  for(i=0;i<5;i++)
    freq[b[i]]--;

  for(i=0;i<5;i++)
  {
    if(freq[i]!=0)
    {
      f=1;
      break;
    }
  }
  if(f==1)
    printf("Not same");
  else
    printf("Same");
  return 0;
}

Answer 1

The cause of the segfault. Here is the live demo that you can poke yourself.

Memory access error: reading from the outside of a memory space; abort execution.
  # Reading 4 bytes from 0xff8f2520 will read undefined values.
  #
  # The memory-space-to-be-read (start:0xff8f250c, size:20 bytes) is bound to 'freq' at
  #    file:/prog.c::5, 7
  #
  #  0xff8f250c               0xff8f251f
  #  +------------------------------+
  #  | the memory-space-to-be-read  |......
  #  +------------------------------+
  #                                  ^~~~~~~~~~
  #        the read starts at 0xff8f2520 that is right after the memory-space end.
  #
  # Stack trace (most recent call first) of the read.
  # [0]  file:/prog.c::15, 5
  # [1]  [libc-start-main]

Answer 2

You only set limit of array freq larger, base on limit of element each array. You cant set it a large number, like 1,000,000

Answer 3

hash function as follows...

struct set
{
  int key;
  int data;
};
struct set *array;
int capacity = 10;
int size = 0;

int hashFunction(int key)
{
  return (key % capacity);
}
int checkPrime(int n)
{
  int i;
  if (n == 1 || n == 0)
  {
    return 0;
  }
  for (i = 2; i < n / 2; i++)
  {
    if (n % i == 0)
    {
      return 0;
    }
  }
  return 1;
}
int getPrime(int n)
{
  if (n % 2 == 0)
  {
    n++;
  }
  while (!checkPrime(n))
  {
    n += 2;
  }
  return n;
}
void init_array()
{
  capacity = getPrime(capacity);
  array = (struct set *)malloc(capacity * sizeof(struct set));
  for (int i = 0; i < capacity; i++)
  {
    array[i].key = 0;
    array[i].data = 0;
  }
}

void insert(int key, int data)
{
  int index = hashFunction(key);
  if (array[index].data == 0)
  {
    array[index].key = key;
    array[index].data = data;
    size++;
    printf("\n Key (%d) has been inserted \n", key);
  }
  else if (array[index].key == key)
  {
    array[index].data = data;
  }
  else
  {
    printf("\n Collision occured  \n");
  }
}

void remove_element(int key)
{
  int index = hashFunction(key);
  if (array[index].data == 0)
  {
    printf("\n This key does not exist \n");
  }
  else
  {
    array[index].key = 0;
    array[index].data = 0;
    size--;
    printf("\n Key (%d) has been removed \n", key);
  }
}
void display()
{
  int i;
  for (i = 0; i < capacity; i++)
  {
    if (array[i].data == 0)
    {
      printf("\n array[%d]: / ", i);
    }
    else
    {
      printf("\n key: %d array[%d]: %d \t", array[i].key, i, array[i].data);
    }
  }
}

int size_of_hashtable()
{
  return size;
}

Answer 4

Your 'freq[a[i]]' and 'freq[b[i]]' is probably what is causing you the problem. Unless a[i] and b[i] are within the range of the indexes for freq, it is going to try to reference somewhere out side of the freq array.

I've never had to do this to compare arrays, since by definition, arrays are already in memory, but I have had to do this for files which it might be problematic to try to read all of it into memory at one time. I would calculate a checksum / hash of all the bytes in the files and then just compare the checksum / hash values. I tended to use this when determining merging the filesystems from multiple hard drives or directories to eliminate duplicates or to give me a list of files that I needed to manually look at. Usually a 32-bit value was enough for this since it would give a 1 in 4G chance of two files who generated the same checksum not being the same file. Combining that with ensuring the files were the same size reduced the possibility even more. The checksum that I would use was a bit shift of the cumulative checksum by 1 bit and then xor-ing the next byte into the checksum. I'm sure there are more extensive checksums out there, but this served my purpose for what I was trying to do.