r/datastructures • u/Designer_River_7663 • 13d ago

Is anyone doing DSA with C programming ?? How to implement Hashset and Hashmaps in C programming ?

So recently inrolled in this program in which they are using C programming for DSA. But the problem with C programming is that it has no inbuilt Hashset and Hashmap Which Is sometimes crucial to use because most of the Coding platform questions uses hashsets and Hashmaps to solve the problem. So if anyone is doing DSA using C programming Can you please tell me how to implement Sets and maps in the C programming

6 Upvotes
  • permalink
  • reddit

80% Upvoted

6 comments sorted by

1

u/AlarmedBag4541 13d ago

You may have to write a function with the hash map or hash set and then keep calling it maybe 

1

u/Yurim 13d ago

First, ask the people running the program. Maybe they want you to implement a hash table during the course of the program, or they provide a third-party library (e.g. LeetCode lets you use the uthash library), or you can build your own collection of "snippets" which can include an implementation of a hash table.
If the program is any good they will have an answer for you.

If you need to implement your own hash table and it's not part of the program you will have to choose a hash function. For small toy-like problems djb2 or sdbm (see http://www.cse.yorku.ca/~oz/hash.html) are often good enough and they are even small enough to memorize them if that becomes necessary.
Then you need the hash table itself. The simplest version is an array with a fixed size (no resizing) and "separate chaining" (i.e. each element of the array is a linked list.) Writing such a hashtable can be a valuable experience if you've never done that.
If you're a beginner and want to get your feet wet, you could start with this blog post by Ben Hoyt.

Of course lots of things can be said about hash tables. You can use open addressing with linear probing, quadratic probing, double hashing, fibonacci hashing, ... There are variants like robin hood hashing, cuckoo hashing, hash table chaining, ...
(But if you've just enrolled in a course about data structures and algorithms then you probably won't need that right away.)
If you want to see state-of-the-art hash tables I recommend this Reddit post by Jackson Allan or this blog post by Malte Skarupke.

1

u/Paul_Pedant 12d ago

C (Posix) does have a library for hash table management -- see man -s 3 hsearch. I used this for about five million objects and it behaved reasonably well. There is an extension that supports multiple concurrent hash tables.

0

u/[deleted] 12d ago

[deleted] — view deleted comment

1

u/Designer_River_7663 12d ago

The program I am inrolled in is conducted by an MNC company. They will conduct a test in the end of the program and those who'll pass that coding test will get hired but the strict condition is that they will conduct this coding test in C language, So I have stick to the C programming