Benvenuti in questa sesta lezione della serie “Scuola Serale di Italian Geek“.
Queste brevi lezioni sono state progettate in modo tale da risultare volutamente sintetiche, dunque, per approfondimenti contattateci usando i commenti a fine articolo. Il codice presente nelle lezioni e’ funzionante ed e’ stato testato su compilatore gcc version 3.4.6 20060404 (Red Hat 3.4.6-9).
L’indice delle lezioni si trova qui.
Tabelle Hash
In informatica una hash table, o tabella hash è una struttura dati usata per mettere in corrispondenza una data chiave con un dato valore. Essa permette operazioni di ricerca e inserimento molto veloci: in pratica si ha un costo computazionale costante O(1).
La realizzazione di una tabella hash è basata sull’uso di array e dunque uno svantaggio intrinseco nella sua rappresentazione è il costo da pagare per ridimensionare la tabella.
Tuttavia l’efficienza delle Tabelle Hash e` tale che gli algoritmi di Hashing sono largamente usati in un vasto insieme di applicazioni. Ad esempio nei compilatori dei linguaggi di programmazione si usano Hash che hanno come chiavi le stringhe che corrispondono agli identificatori del linguaggio.
Dunque mentre con il metodo di indirizzamento diretto un elemento con chiave x viene memorizzato nella tabella in posizione x, con il metodo hash un elemento con chiave x viene memorizzato nella tabella in posizione f(x). La funzione f(x) è detta funzione hash.
Lo scopo della funzione hash è di definire una corrispondenza tra l’universo U delle chiavi e le posizioni di una tabella hash T[0..m-1] con f : U → {0,1,…,m-1}.
Necessariamente la funzione hash non può essere iniettiva, ovvero due chiavi distinte possono produrre lo stesso valore hash.
Quando questo accade si dice che si ha una collisione.
Come realizzare una funzione hash?
Metodo della divisione
Metodo della moltiplicazione
Metodo della funzione hash universale (non lo vedremo)
Nel metodo della divisione la funzione hash è del tipo:
f(x)=x mod m
Cioè il valore hash è il resto della divisione di x per m
Caratteristiche: il metodo è veloce ma si deve fare attenzione ai valori di m. Ma m deve essere diverso da 2p per un qualche p. Altrimenti fare il modulo in base m corrisponderebbe a considerare solo i p bit meno significativi della chiave. In questo caso dovremmo garantire che la distribuzione dei p bit meno significativi sia uniforme. Analoghe considerazioni per m pari a potenze del 10. Buoni valori sono numeri primi non troppo vicini a potenze del due.
Nel metodo della moltiplicazione la funzione hash opera in due passi:
- si moltiplica la chiave per una costante A in [0,1]
- si estrae la parte frazionaria del risultato si moltiplica questo valore per m e si prende la parte intera.
Analiticamente si ha: f(x)= floor(m(x * A mod 1))
Come esempio mostriamo come derivare x a partire da una chiave di tipo Stringa. Supponiamo per semplicità che il valore x restituito sia un intero. Sommiamo i codici ASCII dei vari caratteri componenti la stringa e applichiamo la funzione modulo per evitare di avere valori superiori a 4.294.967.295.
#include
#include
int stringaHash( char * s )
{
long int nMax = numeric_limits::max(); //4294967295
int C = 0;
for ( int i = 1; i C = (C + s[i]) % nMax;
return C;
}
Assumendo che la lunghezza della stringa sia una costante, la complessità della funzione è anch’essa costante.
Una volta ottenuto il valore x, utilizziamo il metodo del modulo per calcolare l’indirizzo nella tabella con p entrate con la formula:
(k % p) + 1;
Segue un esempio di programma in linguaggio C per la manipolazione di insiemi tramite tabelle Hash.
#include<stdio.h>
#define MAXTABLE 701
typedef struct plist *plist;
typedef struct plist
{
int info;
plist prec;
plist next;
}slist;
plist table[MAXTABLE];
int key,totimeh,timeh,number;
void cls()
{
int i;
for(i=0;i<30;i++) printf("\n");
}
plist alloc(key) /*procedura per allocamento in memoria di un tipo plist*/
int key;
{
plist new;
new=(plist)malloc(sizeof(slist));/*crea un nuovo nodo di tipo plist */
new->info=key; /*e di ampiezza slist */
new->next=NULL; /*inizializzo i campi del nuovo nodo*/
new->prec=NULL;
return(new);
}
int fmod(x,y)
int x,y;
{
int comodo;
comodo=x/y;
return (x-(comodo*y));
}
int hash(valore) /*posizione di valore nella tabella hash*/
int valore;
{
return fmod(valore,MAXTABLE);
}
void carhash(nkey)
int nkey;
{
int slot;
plist node;
extern plist table[]; /*tabella*/
extern int timeh; /*contatore operazioni*/
slot=hash(nkey); /*ricava la posizione in table grazie alla funzione hash*/
timeh++;
node=alloc(nkey);
node->next=table[slot];/*inserisce in testa alla lista table[slot]*/
timeh+=3;
if(table[slot] != NULL)
{
table[slot]->prec=node;
timeh++;
}
table[slot]=node;
}
plist searchtab(key)
int key;
{
extern plist table[];
extern timeh;
plist node;
int slot;
slot=hash(key);timeh+=3;
node=table[slot];
while((node != NULL) & (node->info != key))
{
timeh+=2;
node=node->next;
}
return (node);
}
void deltab(key)
int key;
{
extern plist table[];
extern int timeh;
plist node;
node=searchtab(key);
timeh++;
if(node != NULL)
{
timeh+=4;
if(node->prec != NULL) node->prec->next=node->next;
else
{
table[hash(key)]=node->next;
timeh++;
}
if(node->next != NULL)
{
node->next->prec=node->prec;
timeh++;
}
free(node);
}
else printf("ELEMENTO NON PRESENTE NELLA TABELLA\n\n");
}
void printable()
{
int i=0;
plist node;
extern plist table[];
for(i=0;i<MAXTABLE;i++)
{
if(table[i] != NULL)
{
printf("\n Posizione --> %4d * ",i);
for(node=table[i];node != NULL;node=node->next)
printf(" %4d",node->info);
printf("\n");
}
}
}
void tempo()
{
extern int timeh;
printf("\nTempo di esecuzione con HASH TABLE --> %4d\n",timeh);
timeh=0;
}
void mainins()
{
int nkey;
char ris;
printf(" **********INSERIMENTO**********\n");
do
{
printf("\nNumero: ");scanf("%d",&nkey);
carhash(nkey);
number++;
totimeh+=timeh;
printf("\nVuoi inserire un altro numero ? (s/n)-");
rewind(stdin);
ris=getchar();
}
while(ris != 'n');
rewind(stdin);
printf("\n------------------------>>>INSERIMENTO ULTIMATO \n\n\n\n\n\n");
}
main()
{
char scelta;
plist node;
cls();
do
{
printf("\n\n\n");
printf("*** MANIPOLAZIONE DI INSIEMI TRAMITE TABELLE HASH ***\n\n");
printf(" MENU' \n");
printf("\t\t 1) Insert\n");
printf("\t\t 2) Search\n");
printf("\t\t 3) Delete\n");
printf("\t\t 4) Print \n");
printf("\t\t 0) Exit \n");
printf("Scelta: ");scanf("%d",&scelta);printf("\n");
switch(scelta)
{
case 1:{
cls();
mainins();
break;
}
case 2:{
cls();
printf("\nQuale elemento vuoi cercare ? :");
rewind(stdin);
scanf("%d",&key);
node=searchtab(key);
if(node != NULL)
printf("\nElemento: %d presente nella tabella hash !\n",key);
else
printf("\nElemento: %d non presente nella tabella hash !\n",key);
break;
}
case 3:{
cls();
printf("\nQuale elemento vuoi eliminare ? ->");
rewind(stdin);
scanf("%d",&key);
deltab(key);
printf("\nElemento ->%d eliminato.\n",key);
break;
}
case 4:{
cls();
printable();
break;
}
default:break;
}
}
while(scelta);
tempo();
}
Di seguito i link per scaricare il pdf della lezione ed il codice sorgente di esempio.
Download
- Lezione 6: Tabelle Hash
- hash.c
Il prossimo appuntamento e’ per Venerdi’ 2 Dicembre 2011, la lezione avra’ per argomento gli Algoritmi Greedy.
Alla prossima!
Puoi seguire Massimo Orazio Spata, l’autore di questo post, su Twitter.
Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo:[email protected]
Articoli Simili:
- Impara a Programmare, Lezione 4: Alberi rosso-neri
- Impara a Programmare, Lezione 1: Le Liste in C
- Impara a Programmare, Lezione 5: Heap
Pacman
Nostradamus
Magical Cat Adventure
Snake