Necessary Structs to implement a HashTable (that uses a Linked List to avoid collisions) in C?

Question

Hey guys I been reading about pointers, structs and data structures in C over the last couple of days. Now I am trying to implement a Hash Table in C by following along this tutorial: https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm

However tutorialspoint is assuming there will only be 1 hash table and it is making it global. Furthermore, tutorialspoint does not take into account collisions.

I want to make a struct to not limit myself to a single hash table and I plan to incorporate chaining (to deal with collisions) with a linked list. I have the following:

typedef struct node {
    int key;
    int data;
    struct node* next;
} node;

typedef struct linkedList{
    node* head;
    node* tail;
    size_t size;
} linkedList;

typedef struct hashTable{
    //perhaps an array of linked list? This member is what I need help with
    //And other potential members I am overlooking
    size_t size
} hashTable;

Some things that I need to explain:

1. The node struct serves as a pair of key/data and it has a pointer to the next pair that has the same hash code. All nodes with the same hash code will be in the same linked list.

2. The linkedList struct is represents a linked list that will eventually become a row in the hash table. All linked lists will be a row in the hash table.

3. The hashTable struct contains all the linkedLists.

How can I make an array of the linkedList struct in my hashTable struct? Is there other members I am overlooking in my 3 structs?

Any help is appreciated!

P.S. I plan to use the methods I wrote in my Linked List program. Here is a link to an early version of it: https://codereview.stackexchange.com/questions/176904/my-linked-list-implementation-in-c

Answer 1

You can use your node and list structures. The hash table would then just be a struct with an array of lists. The size of the hash table can be dynamic, but let's use a constant size:

enum {
    hashSize = 32
};

typedef struct hashTable {
    linkedList list[hashSize];
    size_t size;                     // How many elelents overall?
} hashTable;

You hash function must return an unsigned hash value smaller than hashSize.

But you don't really need the linked list structure. This structure caters for easy insertion at the front and at the end and it also keeps a count of its elements. The elements of the list are not ordered, so you can always insert at the front, and you don't really need the size, so you could define the linked lists just by pointers to their head, initally all NULL:

typedef struct hashTable {
    node *head[hashSize];
    size_t size;
} hashTable;

(But if you have the code for the linked list already, the array of linked lists may be the way to go.)

---

A note on the tutorialspoint code you linked: It does cater for collisions, but it uses another approach: There is just one slot for each hash code. If the slot for a hash code is already used, it uses the next free hash code.

That approach means that you cannot simply remove elements. Imagine you insert an item with the hash value 5, but that slot is already taken by another item with a different key, but the same hash code. Say 6 and 7 are also taken, so you insert the item into slot 8. If you search for that item, the search first looks at slot 5, but the item there doesn't match. The has code is increased and eventually, the item is found in slot 8. If we find an empty slot first, the search is called off without success. Removing the item in slot 5 makes the item in slot 8 inaccessible. Therefore, a dumme element must be put in that slot. Your linked list approach doesn not need such a dummy element.

(The tutorialspoint approach also means that if the hash table is full, you will search all elements, which isn't any better than searching an unsorted array. The linked list hash table will never be full, but when the number of items in the table is much greater than the hash table size, performance will degrade.)

Answer 2

typedef struct linkedList{
    node* head;
    node* tail;
    size_t size;
} linkedList;

I don't think you really need size_t size here. What comes to the actual hash table struct, you could do:

typedef struct has_map {
    linkedList** table; // stores the actual collision chains.
    size_t table_capacity; // the current capacity of table.
    size_t size; // number of mappings in this hash map.
} hash_map;

Also, I suggest you keep the length of table a power of two: 2, 4, 8, 16, ... That way you can change hash_code % hash_map->table_capacity with bit operation hash_code & (hash_map->table_capacity - 1).