Open Hashing in C

Question

#define maxCells 1000
#define maxCS 11
#define maxIT 19

typedef struct
{
char LN[16], FN[24], MI;
}nametype;

typedef struct studtype
{
unsigned long ID;
nametype name;
char course[8];
int yr;
}student;

typedef struct ctype
{
student stud;
int next;
}celltype;

typedef struct
{
int *Header;
int CourseCtr;  /*holds the # of elements for each course*/
}CSIT;

typedef CSIT Dictionary[2];
typedef int LIST;

typedef struct
{
celltype heap[maxCells];
int AvailPtr;   /*holds the index to the first available cell in the VH*/
}*VirtualHeap;

Problem Definition:

A list of BSCS and BSIT student records is stored in internal memory represented using cursor-based implementation. The list is to be converted into a dictionary, a set ADT. The dictionary is represented in memory using open-hashing (cursor-based). Each group in the header table is sorted in ascending order according to ID.

*Hash function exists and can be called in your function. The function will accept an element as its parameter and return the appropriate hash value for each element.

Write the code of the function CreateDic() – the function will convert the list of BSCS and BSIT student records into a dictionary, which will be returned to the calling function. Each student record is uniquely identified by the ID.

Questions

I have no idea what the problem is, nor understand any about open hashing. I'm new to this language. This not a homework nor an exercise. This is an exam we had last week and I never got the idea of the problem. Can anyone help me understand better about the problem. Whether there's a code or not. Help me on this one please.

Answer 1

I feel your pain. As others have said, what can be done here to patch your knowledge is limited. Here are a few points.

A set implemented with open hashing is an array of N list head pointers (your teacher called this array Header), each the start of a linked list.

To add a new element, create and fill in a new list cell, then compute an integer hash value H based on the cell's key. (In your problem, it will work fine to use the student ID itself for the hash key.) Insert the new cell into the linked list with head pointer at index (H mod N).

Now, your teacher has provided a framework where the "pointers" I've mentioned above are implemented as integer array indices. He or she sets up a big array of cells with a top pointer (integer index) that always shows how may cells have already been allocated.

This is a pretty unconventional framework. Not many production systems would do it this way. Same for the coding style and data structure choices, but let's continue.

We need to make assumptions to finish the problem: 1) the input lists are indices into the "virtual heap" and 2) we should destroy the input lists and re-use the nodes to insert in the hash set.

With all this in mind, we can write some code.

// Helper to create one CSIT hash set for the given list of students.
CSIT CreateCSITSet(size_t size, LIST lst, VirtualHeap *vh)
{
  CSIT csit;

  // Allocate the header array of integers and make them null.
  // safe_malloc is just malloc that exits properly if we're out of memory.
  csit.Header = safe_malloc(size * sizeof(int));

  // We're using -1 as a null index. 
  for (int i = 0; i < size; i++) csit.Header[i] = -1;

  // No students yet inserted.
  csit.CourseCtr = 0;

  // Traverse the input list and push onto the hash.
  int next = -1;
  for (int p = lst; p >= 0; p = next) {

    // Remember 'next' field because we'll change it below.
    next = vh.heap[p].next

    // Use the student ID to find the header index.
    int hix = vh.heap[p].stud.ID % size;

    // Push (and also unchain from the input list).
    vh.heap[p].next = csit.Header[hix];
    csit.Header[hix] = p;

    // Count the new entry.
    csit.CourseCtr++;
  }
  return csit;  // This returns the entire record: both fields.
}

// To create the dictionary, call our helper twice to fill in the hash sets.
Dictionary CreateDic(LIST bscs, LIST bsit, VirtualHeap *vh)
{
  Dictionary dict = safe_malloc(sizeof(Dictionary));
  dict[0] = CreateCSITSet(maxCS, bscs, vh);
  dict[1] = CreateCSITSet(maxIT, bsit, vh);
  return dict;
}

This is obviously untested and may contain small errors, but it ought to be close.

Note that I did not satisfy the requirement that the lists inside the hash set should be in sorted order. I'll leave you to work on that.

Answer 2

Probably this will give you a good start for a dictionary:

Quick Way to Implement Dictionary in C

If you are new to C you should probably learn more about linked lists before you go into open hashing. Entries of the hash table will contain a linked list each, or at least the head of it.