In a comment, OP mentioned they learn better from an example. (This is not an answer per se, only an example. Please consider this an extended comment, rather than an answer.)
Let's look at a simple, real-world example, then; but something that cannot be just copy-pasted and presented as ones own work.
Let's assume we need a hash table of text or tokens, say
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct hashentry {
struct hashentry *next;
size_t hash;
unsigned char data[];
};
struct hashtable {
size_t size;
struct hashentry **slot;
};
where the table itself is an array of pointers, and hash collisions are solved via chaining. Note that instead of key-value pairs, I am essentially using keys only; this is to avoid having this example code copy-pasted and presented as someones own work. I wrote this to help new programmers understand, not for cheaters to submit as their homework. (I am not referring to OP, mind you. These questions are often found via a web search, and I write these answers for that overall group, not just the asker.)
Table initialization to a specific size:
static inline void hashtable_init(struct hashtable *const ht, const size_t size)
{
size_t i;
if (!ht) {
fprintf(stderr, "hashtable_init(): No hashtable specified (ht == NULL).\n");
exit(EXIT_FAILURE);
} else
if (size < 1) {
fprintf(stderr, "hashtable_init(): Invalid hashtable size (size == %zu).\n", size);
exit(EXIT_FAILURE);
}
/* Allocate an array of pointers. */
ht->slot = calloc(size, sizeof ht->slot[0]);
if (!ht->slot) {
fprintf(stderr, "hashtable_init(): Failed to allocate an array of %zu slots.\n", size);
exit(EXIT_FAILURE);
}
ht->size = size;
/* Mark each slot unused. (On all current architectures, this is unnecessary,
as calloc() does initialize the pointers to NULL, but let's do it anyway.) */
for (i = 0; i < size; i++)
ht->slot[i] = NULL;
}
For a hash function, I like DJB2 Xor variant for text strings. It is not particularly good (there will be collisions), but it is very simple and fast:
static inline size_t hash_data(const char *data, const size_t datalen)
{
const char *const ends = data + datalen;
size_t hash = 5381;
while (data < ends)
hash = (33 * hash) ^ (unsigned char)(*(data++));
return hash;
}
Note that I use size_t as the type for the hash. You could use any type you want, but on most architectures, it's the same size as a pointer, which is .
To add a data entry to the hash table:
static inline void hashtable_add(struct hashtable *ht, const char *data, const size_t datalen)
{
struct hashentry *entry;
size_t hash, slotnum;
if (!ht) {
fprintf(stderr, "hashtable_add(): No hashtable specified (ht == NULL).\n");
exit(EXIT_FAILURE);
} else
if (ht->size < 1) {
fprintf(stderr, "hashtable_add(): Hashtable has zero size.\n");
exit(EXIT_FAILURE);
} else
if (!data && datalen > 0) {
fprintf(stderr, "hashtable_add(): data is NULL, but datalen == %zu.\n", datalen);
exit(EXIT_FAILURE);
}
/* Allocate memory for the entry, including the data, and the string-terminating nul '\0'. */
entry = malloc(sizeof (struct hashentry) + datalen + 1);
if (!entry) {
fprintf(stderr, "hashtable_add(): Out of memory (datalen = %zu).\n", datalen);
exit(EXIT_FAILURE);
}
/* Copy the data, if any. */
if (datalen > 0)
memcpy(entry->data, data, datalen);
/* Ensure the data is terminated with a nul, '\0'. */
entry->data[datalen] = '\0';
/* Compute the hash. */
hash = hash_data(data, datalen);
entry->hash = hash;
/* The slot number is the hash modulo hash table size. */
slotnum = hash % ht->size;
/* Prepend entry to the corresponding slot chain. */
entry->next = ht->slot[slotnum];
ht->slot[slotnum] = entry;
}
When I initially write code like the above, I always write it as a test program, and test it. (This technically falls under the unit testing paradigm.)
In this case, we can simply take the number of slots as a command-line parameter, and read each line from standard input as data to be added to the hash table.
Because standard C does not implement getline(), we'd better use fgets() instead, with a fixed-size line buffer. If we declare
#ifndef MAX_LINE_LEN
#define MAX_LINE_LEN 16383
#endif
we have a preprocessor macro MAX_LINE_LEN that defaults to 16383, but can be overridden at compile time by using compiler options. (With GCC, Intel CC, and clang, you can use e.g. -DMAX_LINE_LEN=8191 to halve it.)
In main(), I like to print the usage if the parameter count is incorrect, or -h or --help is the first parameter:
int main(int argc, char *argv[])
{
char buffer[MAX_LINE_LEN + 1];
char *line;
size_t size, i;
struct hashtable table;
char dummy;
if (argc != 2 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
fprintf(stderr, " %s ENTRIES < DATA-FILE > DOT-FILE\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program reads lines from DATA-FILE, adding them to\n");
fprintf(stderr, "a hash table with ENTRIES slots and hash chaining.\n");
fprintf(stderr, "When all input lines have been read, the contents of the\n");
fprintf(stderr, "hash table slots will be output as a Graphviz DOT format graph.\n");
fprintf(stderr, "\n");
return EXIT_SUCCESS;
}
Next, we can try and parse the first command-line parameter to size_t size;. I like to use a "sentinel" character, to detect if the parameter has garbage after the value (other than whitespace):
if (sscanf(argv[1], "%zu %c", &size, &dummy) != 1 || size < 1) {
fprintf(stderr, "%s: Invalid number of hash table entries.\n", argv[1]);
return EXIT_FAILURE;
}
hashtable_init(&table, size);
The next part is to read each line from standard input, and add them to the hash table.
while (1) {
line = fgets(buffer, sizeof buffer, stdin);
if (!line)
break;
/* Skip leading ASCII whitespace. */
line += strspn(line, "\t\n\v\f\r ");
/* Find out the remaining length of the line. */
size = strlen(line);
/* Ignore trailing ASCII whitespace. */
while (size > 0 && (line[size-1] == '\t' || line[size-1] == '\n' ||
line[size-1] == '\v' || line[size-1] == '\f' ||
line[size-1] == '\r' || line[size-1] == ' '))
size--;
/* Ignore empty lines. */
if (size < 1)
continue;
/* Add line to the hash table. */
hashtable_add(&table, line, size);
}
/* Check if fgets() failed due to an error, and not EOF. */
if (ferror(stdin) || !feof(stdin)) {
fprintf(stderr, "Error reading from standard input.\n");
return EXIT_FAILURE;
}
At this point, we have table with size slots. I write my test programs to write either plain text output (if simple), or Graphviz DOT format output (if structured like graphs). In this case, the graph output format sounds better.
/* Print the hash table contents as a directed graph, with slots as boxes. */
printf("digraph {\n");
for (i = 0; i < table.size; i++) {
struct hashentry *next = table.slot[i];
/* The slot box. */
printf(" \"%zu\" [ shape=\"box\", label=\"%zu\" ];\n", i, i);
if (next) {
/* The edge from the slot box to the entry oval. */
printf(" \"%zu\" -> \"%p\";\n", i, (void *)next);
while (next) {
struct hashentry *curr = next;
/* Each entry oval; text shown is the value read from the file. */
printf(" \"%p\" [ shape=\"oval\", label=\"%s\" ];\n", (void *)curr, curr->data);
next = next->next;
/* The edge to the next oval, if any. */
if (next)
printf(" \"%p\" -> \"%p\";\n", (void *)curr, (void *)next);
}
}
}
printf("}\n");
return EXIT_SUCCESS;
}
That's it. If you compile and run the above program with 10 as the command-line argument, and feed
one
two
three
four
five
six
seven
eight
nine
ten
to its standard input, it will output
digraph {
"0" [ shape="box", label="0" ];
"1" [ shape="box", label="1" ];
"1" -> "0xb460c0";
"0xb460c0" [ shape="oval", label="three" ];
"0xb460c0" -> "0xb46080";
"0xb46080" [ shape="oval", label="one" ];
"2" [ shape="box", label="2" ];
"3" [ shape="box", label="3" ];
"3" -> "0xb46180";
"0xb46180" [ shape="oval", label="nine" ];
"0xb46180" -> "0xb460a0";
"0xb460a0" [ shape="oval", label="two" ];
"4" [ shape="box", label="4" ];
"4" -> "0xb46160";
"0xb46160" [ shape="oval", label="eight" ];
"0xb46160" -> "0xb46140";
"0xb46140" [ shape="oval", label="seven" ];
"5" [ shape="box", label="5" ];
"5" -> "0xb46100";
"0xb46100" [ shape="oval", label="five" ];
"6" [ shape="box", label="6" ];
"6" -> "0xb461a0";
"0xb461a0" [ shape="oval", label="ten" ];
"7" [ shape="box", label="7" ];
"7" -> "0xb46120";
"0xb46120" [ shape="oval", label="six" ];
"0xb46120" -> "0xb460e0";
"0xb460e0" [ shape="oval", label="four" ];
"8" [ shape="box", label="8" ];
"9" [ shape="box", label="9" ];
}
which fed to Graphviz dot will generate a nice graph:
If you want to see the actual hash values above the data strings, change to
/* Each entry oval; text shown is the value read from the file. */
printf(" \"%p\" [ shape=oval, label=\"%zu:\\n%s\" ];\n", (void *)curr, curr->hash, curr->data);
As I said, the DJB2 Xor hash is not particularly good, and for the above input, you need at least 43 hash table slots to avoid chaining.
