How to insert values into linked list members on an hashtable

Question

I have a contact structure inserted into a linked list which is in an hashtable. I don't know if I defined all my structures correctly. I basically want to add a contact via input when given the command 'a' (command would be like this: a name mail phone). I sould not be able to add the contact if it already exists.

I've tried creating the necessary structure of an hashtable with linked lists, i just don't understand how to work with it. So this function would help me a lot with understanding this concept.

This is the structure i've tried

#define NOME_SIZE 1023
#define MAIL_SIZE 511
#define TELEFONE_SIZE 63
#define HASH_SIZE 1000

typedef struct contacts{
    char name[NOME_SIZE];
    char mail[MAIL_SIZE];
    char phone[TELEFONE_SIZE];
    struct contacts *next;
}HashList;


typedef struct hash_bucket{
    HashList *head, *tail; 
    int n_elements; 
}HashBucket;

HashBucket hashtable[HASH_SIZE];

I do not expect any output if i can successfuly add the contact. If it already exists it should return an error saying the contact already exists

The goal of a hash table is to have fast accesses from key(s), having a linked list even sorted for a key the goal will not be reach. Or `hash_bucket` represents the list of 'synonyms' ? in that case where is the hash table ? — bruno, May 13 '19 at 15:28
@bruno I think in this case, each hash table entry has its own linked list to resolve hash collisions. — Ian Abbott, May 13 '19 at 15:30
so you have somewhere a function computing the hash then you do `%HASH_SIZE`, in that case I recommend you to use a prime number for `HASH_SIZE`, that gives better result — bruno, May 13 '19 at 15:35
so just decide how and from what the hash is computed (name ?), then a way to iterate on a _HashList_, this is simple, what blocks you ? — bruno, May 13 '19 at 15:37
In `HashList`, you have `name`, `mail` and `phone` strings. I guess that `name` will be used as a key to look up the other information. In that case, you need to feed the `name` string to a hash function that produces a hash code value from 0 to `HASH_SIZE-1` and use the hash code to index into the hash table. Then you need to perform whatever list operation is required on the linked list - add/remove or search entries. — Ian Abbott, May 13 '19 at 15:39
Note you are **very** generous for the length of the fields, 1023 for a name, 511 for an email and 63 for a phone number, wow ^^ — bruno, May 13 '19 at 15:42
To hash a string you can look at https://stackoverflow.com/questions/7666509/hash-function-for-string and after just do a modulo with `HASH_SIZE` — bruno, May 13 '19 at 15:44
@bruno they were just random numbers to post the question lmao — Miguel Ribeiro, May 13 '19 at 15:45
I find `typedef struct contacts HashList` confusing. What do you intend? — Neil, May 13 '19 at 19:47

bruno · Accepted Answer · 2019-05-13T16:58:14.007

A proposal from your code and my remarks. I removed n_elements because for me it is useless. I let tail but not sure it is useful because your list only have a next with a previous. I let arrays for name, phone and mail but I think it is better to use char *

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOME_SIZE 1023
#define MAIL_SIZE 511
#define TELEFONE_SIZE 63
#define HASH_SIZE 1000

typedef struct contacts{
    char name[NOME_SIZE];
    char mail[MAIL_SIZE];
    char phone[TELEFONE_SIZE];
    struct contacts *next;
}HashList;


typedef struct hash_bucket{
    HashList *head, *tail; 
    /* int n_elements; * I removed that field, it is useless */
}HashBucket;

HashBucket hashtable[HASH_SIZE]; 

// from https://stackoverflow.com/a/7666577/2458991
size_t hash(char * str)
{
  size_t hash = 5381;
  unsigned char c;

  while ((c = (unsigned char) *str++) != 0)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

  return hash;
}

HashList * createElt(char * n, char * m, char * p)
{
  HashList * e = malloc(sizeof(HashList));

  strncpy(e->name, n, NOME_SIZE - 1);
  e->name[NOME_SIZE - 1] = 0;

  strncpy(e->mail, m, MAIL_SIZE - 1);
  e->name[MAIL_SIZE - 1] = 0;

  strncpy(e->phone, p, TELEFONE_SIZE - 1);
  e->name[TELEFONE_SIZE - 1] = 0;

  e->next = NULL;

  return e;
}

// add or replace an element, the key is the name
// return 0 if the entry is added, else a non null value if the entry is (probably) modified
int insertElt(char * n, char * m, char * p)
{
  // suppose list sort on the name
  HashBucket * hb = &hashtable[hash(n) % HASH_SIZE];
  HashList ** hl = &hb->head;

  for (;;) {
    if (*hl == NULL) {
      /* last (and may be first) element */
      *hl = createElt(n, m, p);
      hb->tail = *hl;
      return 0;
    }

    int cmp = strcmp((*hl)->name, n);

    if (cmp == 0) {
      /* replace */
      strncpy((*hl)->mail, m, MAIL_SIZE - 1);
      (*hl)->name[MAIL_SIZE - 1] = 0;

      strncpy((*hl)->phone, p, TELEFONE_SIZE - 1);
      (*hl)->name[TELEFONE_SIZE - 1] = 0;

      return 1;
    }

    if (cmp > 0) {
      /* insert before */
      HashList * e = createElt(n, m, p);

      e->next = *hl;
      *hl = e;

      return 0;
    }

    hl = &(*hl)->next;
  }
}

void pr()
{
  for (size_t i = 0; i != HASH_SIZE; ++i)
    for (HashList * hl = hashtable[i].head; hl != NULL; hl = hl->next)
      printf("%s %s %s\n", hl->name, hl->mail, hl->phone);
}

int main()
{
  printf("%d\n", insertElt("n1", "m1", "p1"));
  printf("%d\n", insertElt("n2", "m2", "p2"));
  pr();
  printf("%d\n", insertElt("n1", "mm1", "pp1"));
  pr();

  return 0;
}

Compilation and execution :

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall hm.c
pi@raspberrypi:/tmp $ ./a.out
0
0
n1 m1 p1
n2 m2 p2
1
n1 mm1 pp1
n2 m2 p2

I'm supposed to give the command 'a name mail phone' on the terminal. for exemple: 'a bruno bruno@gmail.com 987654322' So the function where i insert the variables should be void and i shoud use fgets() or scanf() depending on what's most helpful. The main function should only say something like this: 'int main(){ char command; lista = NULL; while(1){ command = getchar(); switch(command){ case'a': insertElt(); break; — Miguel Ribeiro, May 13 '19 at 16:57
@MiguelRibeiro frankly you can modify the code to do that no ? This is trivial — bruno, May 13 '19 at 16:59
it was super helpful! i was just explaining something i shoud have. thanks a lot — Miguel Ribeiro, May 13 '19 at 17:04

How to insert values into linked list members on an hashtable

1 Answers1