2015:04:07:HashTables

Introduction

Today, we are going to see how to implement simple hashtables. You will resolve collisions with linked lists.

Subject maintainer

Feel free to contact me if you find an error or if something is unclear.

• veyry_p (Pierre-Alexandre VEYRY) veyry_p@epita.fr

Submission

You will submit a repository containing at least a AUTHORS file, a Makefile at the root of the directory, and your source code. The main function must be in a file called main.c separated from the rest so that we can replace it with our own main.

We remind you that to be valid, your AUTHORS must match this :

   sh$ cat -e AUTHORS
   * login_x$

Architecture :

• login_x-tp-hash
  • AUTHORS
  • Makefile
  • README (facultatif)
  • src
    • main.c
    • Your source code

Reminder

In a hashtable, you have pairs of key,value. To store them, you will apply a hash function on the key to determine the position in the vector. If two keys have the same position, this is a conflict. You will link them in a linked list if the keys are different. However, remind that a key must be unique in the entire hashtable.

Structure Definitions

You will use this hashtable.h :

#ifndef HASHTABLE_H
# define HASHTABLE_H
 
# include <stddef.h>
 
struct place
{
  char *key;
  char *val;
  struct place *next;
};
 
struct hashtable
{
  size_t size;
  struct place **table;
};
 
#endif /* !HASHTABLE_H */

In the following exercises, you will implement functions and add their prototypes inside the hashtable.h header file.

Init the hashtable

You will implement the following function. It creates a new empty hashtable.

struct hashtable *init_hashtable(size_t s);

Hash function

To implement a hashtable, you need to calculate the position of your element in the vector. To do so, we will use a very common and simple hash function. The position of the vector will be calculated using this formula :

   pos = (strlen(key) + sum(ascii_val(key[i]))) mod hashtable.size

The main advantage of hashtable is performance. So you will use only one loop to implement this function. We will check the optimisation. The usage of strlen from the standard library is forbidden.

You can also use another hash function if you want but everything must work. This one is efficient and simple.

Insertion

You will have to implement the following function to add a value inside your hashtable :

int insert_hash(struct hashtable *table, const char *key, char *value);

If everything works, you will return 1. If you have a position conflict, add the new value at the beginning of the list. If the key already exists, you will not insert the element and return 0. If any other problem occurs, you will return 0.

Removing an element

You will implement the following function :

int rm_hash(struct hashtable *table, const char *key);

You will return 1 if it succeeded and 0 if you didn't find the key or if anything went wrong.

Getting a value

You will implement the following function :

char *get_hash(struct hashtable *table, const char *key);

You will return NULL if you don't find the key. Otherwise, you will return the value.

Free

If you free your memory, then you've understand everything. You will implement this function that removes everything in the hashtable and frees everything. We will check with valgrind.

void free_hash(struct hashtable *table);

BONUS : Print the table

You will implement a function to print the table.

void print_table(struct hashtable* table);

It will print all the keys and values.

You will separate the keys from their values with a space, a colon, and a space : " : "

The different places (slots) will be separated with a newline : '\n'

Don't print anything for empty places.

And when there are several values on the same line, you will separate them with this : " -> "

Example :

   sh$ ./a.out
   KEY1 : value1
   KEY2 : value2 -> KEX3 : value3
   KEY4 : value4