Strutture dati: Hash table

Le tavole di hash sfruttano la principale caratteristica degli array di elementi contigui: poter accedere ad un elemento in tempo costante $O(1)$ se si conosce l'indice dell'elemento, anche quando il numero di elementi è estremamente elevato. In questo caso, però, usando un semplice array il consumo di memoria potrebbe rivelarsi un problema. Le Hash table, invece, limitano il consumo di memoria e mantengono il tempo di 'accesso agli elementi quanto più possibile vicino a $O(1)$ usando una combinazione di array e liste concatenate (si faccia riferimento all'immagine sotto nel prosieguo della lettura).

Volendo si può allocare localmente o staticamente la hashtable e dinamicamente le liste concatenate.
Se gli elementi da inserire nelle liste concatenate non hanno valori numerici (insieme di elementi ${v1, v2, .., vn}$ nell'immagine sopra), bisogna creare una funzione (indicata dalla freccia nera) che trasformi gli stessi in valori numerici (insieme di elementi ${0, 1, 2, ..., n}$) da usare come input per la funzione hash, che ha il compito di portare questi valori all'interno dell'intervallo $[0, k)$, dove $k$ è il numero di elementi dell'hashtable, così da poterli usare come indici in quest'ultima.

In questa semplice implementazione (tutt'altro che ideale) si hanno elementi di tipo stringa (si veda [4] per la wordlist usata) che vengono trasformati in valori numerici considerando le stringhe come numeri in notazione posizionale. Ad esempio, se la stringa è "ciao" e la base è $2$, il suo valore numerico sarà $99*2^0+105*2^1+97*2^2+111*2^3 = 1585$, dove $99, 105, 97$ e $111$ sono i valori numerici dei caratteri 'c', 'i', 'a' e 'o'.
Per la funzione di hash, invece, si è optato per il metodo della moltiplicazione, che è di semplice implementazione. Per maggiori dettagli sul metodo della moltiplicazione e altre funzioni di hash si veda [1] o [2]. Per una semplice implementazione di liste concatenate si veda [3].
Si noti che la tabella di hash in questo esempio di codice ha spazio allocato dinamicamente ma sarebbe potuto essere allocato anche localmente sullo stack.

/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di 
utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme 
C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono 
una maggiore semplificazione.*/
 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
 
#pragma warning(disable : 4996)
 
struct link
{
 char val[20];
 struct link *prev;
 struct link *next;
};
 
link* list_search(link*, const char*);
void list_insert(link*&, link&);
void list_delete(link*&, link&);
void print_list(link*, int&);
 
unsigned int str2int_key(const char*);
unsigned int hash_funct(unsigned int);
void read_string(FILE*, char*);
 
int main(int argc, char *argv[], char *envp[])
{
 unsigned long *hashtable = (unsigned long*)calloc((pow(2, 9)), sizeof(unsigned long));
 link *links_alloc = (link*)calloc(1000, sizeof(link));
 
 size_t ind = 0;
 FILE *pFile = fopen("wordlist.txt", "r");
 if (pFile == nullptr)
 {
  fprintf(stderr, "%s\n", "Impossibile aprire il file!");
  return 1;
 }
 
 while (!feof(pFile))
 {
  read_string(pFile, links_alloc[ind].val);
  unsigned int int_str = str2int_key(links_alloc[ind].val);
  unsigned int index = hash_funct(int_str);
 
  if ((unsigned long*)hashtable[index] != nullptr)
   list_insert((link*&)hashtable[index], links_alloc[ind]);
  else
   hashtable[index] = (unsigned long)&links_alloc[ind];
 
  ind++;
 }
 fclose(pFile);
 
 unsigned int int_str = str2int_key("the");
 unsigned int index = hash_funct(int_str);
 
 int count = 0;
 
 if ((unsigned long*)hashtable[index] != nullptr)
 {
  link *f = list_search((link*)hashtable[index], "the");
  printf("%s\n", f->val);
  print_list((link*)hashtable[index], count);
  printf("Numero di elementi della lista: %d\n", count);
 }
 
 printf("\n");
 int i, j;
 count = 0;
 for (i = 0, j = 0; i < pow(2, 9); ++i)
 {
  if ((unsigned long*)hashtable[i] != nullptr)
  {
   ++j;
   printf("%d: ", i);
   print_list((link*)hashtable[i], count);
  }
 }
 printf("\n");
 printf("%d elementi dell'hashtable occupati su %d\n", j, (int)pow(2, 9));
 printf("Massimo numero di elementi in una lista: %d\n", count);
 
 free(links_alloc);
 free(hashtable);
 
 return 0;
}
 
void read_string(FILE* pfile, char *str)
{
 fgets(str, 20, pfile);
 
 int len = strlen(str);
 if (str[len - 1] == '\n')
  str[len - 1] = '\0';
}
 
unsigned int str2int_key(const char* str)
{
 unsigned int tmp = 0;
 char c;
 for (int i = 0; *str; str++, i++)
 {
  c = *str;
  tmp += (double)c * pow(2, i);
 }
 
 return tmp;
}
 
unsigned int hash_funct(unsigned int n)
{
 double A = (sqrt(5) - 1) / 2;
 unsigned long s = A * pow(2, 32);
 unsigned long r = n * s;
 r >>= 23;
 return r & 0x1FF;
}
 
link* list_search(link *first, const char* x)
{
 link *lp = first;
 while (lp != nullptr && strcmp(x, lp->val))
  lp = lp->next;
 
 return lp;
}
 
void list_insert(link *&first, link &l)
{
 l.next = first;
 
 if (first)
  first->prev = &l;
 
 l.prev = nullptr;
 first = &l;
}
 
void list_delete(link *&first, link &l)
{
 if (l.prev != nullptr)
  l.prev->next = l.next;
 else
  first = (l.next);
 
 if (l.next != nullptr)
  l.next->prev = l.prev;
}
 
void print_list(link *first, int &count)
{
 link *lp = first;
 int i;
 for (i = 1; lp->next != nullptr; ++i)
 {
  printf("%s, ", lp->val);
  lp = lp->next;
 }
 printf("%s", lp->val);
 printf("\n");
 if (count <= i)
  count = i;
}

Riferimenti
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Algoritmi in C - Sedgewick
[3] Strutture dati: Linked list
[4] https://gist.github.com/deekayen/4148741