Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*tabelle hash a indirizzamento aperto
- l'ispezione di una tabella hash a indirizzamento aperto permette la ricerca all'interno della tabella della posizione a cui si vuole inserire l'elemento.
- SE E' VUOTA l'elemento si inserisce all'interno
- SE E' PIENA allora si alloca della nuova memoria in coda o lo si inserisce semplicemente in coda
- si ridefinizsce il tipo di TInfo in quanto c'è necessita della mappatura dei campi usati all'interno della hash table
- il campo è una voce INT used che associa 1 se il campo è stato gia usato, 0 invece se non e stato utilizzato, per monitorare l'impiego dei bucket
- nella implementazione del meccanismo di inserimento della hash table a indirizzamento aperto causa un aumento del numero delle collisioni, quindi per ovviare a cio si necessita
- di un uamento della taglia della memoria allocata. Per permettere l'inserimento di tutti gli elementi dobbiamo avere un coefficiente di carico strettamente inferiore
- a 1 in quanto:
- -se superiore non permette l'inclusione di tutti gli elementi in quanto non è presente memoria allocata
- -le prestazioni migliorano in quanto si avvicinano a una complessità costante
- Il coefficiente di carico OTTIMALE deve essere compreso tra 0.5 e 0.75
- L'USO di questa tabella viene preferito quando la singola informazione da memorizzare nella hash table è piccola
- */
- #include "HTheader_aperto.h"
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- THT HTCreate(int n){
- THT* ht=malloc(sizeof(THT));
- assert(ht!=NULL);
- ht->bucket=malloc(sizeof(TInfo)*n);
- ht->used=malloc(sizeof(int)*n);
- assert(ht->bucket!=NULL && ht->used!=NULL);
- ht->n_used=0;
- ht->n_bucket=n;
- for(int i=0;i<n;i++){
- ht->used[i]=0;
- }
- return ht;
- }
- void HTDestroy(THT*ht){
- free(ht->used);
- free(ht->bucket);
- free(ht);
- }
- TValue HTSearch(THT*ht,TKey key){
- unsigned h=keyHash(key)%ht->n_bucket;
- TInfo info ={key};
- while(ht->used[h] && !infoEqual(info, ht->n_bucket[h])){
- h=(h+1)%ht->n_bucket;
- }
- return(ht->used[h])? &ht->bucket[h].v: NULL;
- }
- void HTinsert(THT*ht, TKey key, TValue value){
- TValue *p=HTSearch(ht, key);
- if(p!=NULL){
- *p=value;
- return;
- }
- //devo procedere al ridimensionamento in mancanza di spazio??
- if(ht->n_used+1>= (ht->n_bucket*GROW_FACTOR)){
- HTresize(ht,GROW_FACTOR*ht->n_bucket+1);
- unsigned int h=keyHash(key)%ht->n_used;
- while(ht->used[h])
- h=(h+1)%ht->n_bucket;
- ht->bucket[h].v=value;
- ht->bucket[h].k=key;
- ht->used[h]=1;
- ht->n_used++;
- }
- }
- //complessita computazionale
- //T(n1)+T(n2)=T(n)
- void HTresize (THT *ht, int n){
- TInfo* bucket=ht->bucket;
- int* used=ht->used;
- int n_buckets=ht->n_bucket;
- ht->bucket=malloc(sizeof(TInfo)*n);
- ht->used=malloc(sizeof(int)*n);
- assert(ht->bucket!=NULL && ht->used!=NULL);
- ht->n_bucket=n;
- for(int i=0;i<n;i++){
- ht->used[i]=0;
- }
- ht->n_used=0;
- for(int i=0;i<n_buckets;i++){
- if(ht->used[i]==1)
- HTinsert(ht,bucket[i].k, bucket[i].v);
- }
- free(bucket);
- free(used);
- }
- //complessita computazionale lineare
- void HTdelete(THT*ht, TKey key){
- unsigned int h=keyHash(key)%ht->n_bucket;
- //scandisco la tabella finoa che non trovo l'elemento
- TInfo info={key};
- while(ht->used[h] &&!infoEqual(info,ht->bucket[h]))
- h=(h+1)%ht->n_bucket;
- if(!ht->used[h]) //se non lo trova non fa modifiche
- return;
- unsigned int hole=h; //libero l'elemento
- ht->used[h]=0;
- ht->n_used--;
- //scansiono la tabella
- h=(h+1)%ht->n_bucket; //mi posiziono alla pos. successiva
- while(ht->used[h]){
- //verifico se l'elemento trovato è spostabile o meno
- //ottengo la chiave dell'elemento e l'hashing della chiave
- unsigned int h1=keyHash(ht->bucket[h].k)%ht->n_bucket;
- //valutazione del possibile spostamento della chiave
- if(((h>hole) &&(h1<=hole || h1>h))||(h<hole && h1>h && h1<=hole))
- {
- //cambio l'elemento e i parametri ad esso associati
- ht->bucket[hole]=ht->bucket[h] ;
- ht->used[hole]=1;
- hole=h;
- ht->used[hole]=0;
- }
- //reitero il procedimento per poter modificare il buco successivo creato
- h=(h+1)%ht->n_bucket;
- }
- }
- //ricerca quadratica
- /*
- h(k), |h(k)+c1+c2|m,|h(k)+c1+c2+2c1+2c2|m,...
- * se ipotizzo c1=c2=1/2:
- * h(k), |h(k)+1|m,|h(k)+3|m,...
- *
- * ****problematica: possibile mancanza di confronto tra elementi che vengono saltati
- * ***vantaggio: facilita il caso in cui gli elementi hanno tutti valori di hashing molto simili
- *
- * DOPPIO HASHING
- * determino due funzioni di hashing in base alle quali definisco un valore per determinare
- * l'hashing dell'elemento (combinazione lineare delle due hashing)
- * h1(k),|h1(k)+h2(k)|m, |h1(k) +2h2(k)|m,...
- *
- *
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement