SHARE
TWEET

Untitled

a guest Dec 11th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*tabelle hash a indirizzamento aperto
  2. 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.
  3. SE E' VUOTA l'elemento si inserisce all'interno
  4. SE E' PIENA  allora si alloca della nuova memoria in coda o lo si inserisce semplicemente in coda
  5.  
  6. si ridefinizsce il tipo di TInfo  in quanto c'è necessita della mappatura dei campi usati all'interno della hash table
  7. 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
  8.  
  9.  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
  10. di un uamento della taglia della memoria allocata. Per permettere l'inserimento di tutti gli elementi dobbiamo avere un coefficiente di carico strettamente inferiore
  11. a 1 in quanto:
  12. -se superiore non permette l'inclusione di tutti gli elementi in quanto non è presente memoria allocata
  13. -le prestazioni migliorano in quanto si avvicinano a una complessità costante
  14. Il coefficiente di carico OTTIMALE deve essere compreso tra 0.5 e 0.75
  15.  
  16. L'USO di questa tabella viene preferito quando la singola informazione da memorizzare nella hash table è piccola
  17.  
  18. */
  19.  
  20. #include "HTheader_aperto.h"
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <assert.h>
  24.  
  25. THT HTCreate(int n){
  26.     THT* ht=malloc(sizeof(THT));
  27.     assert(ht!=NULL);
  28.     ht->bucket=malloc(sizeof(TInfo)*n);
  29.     ht->used=malloc(sizeof(int)*n);
  30.     assert(ht->bucket!=NULL && ht->used!=NULL);
  31.     ht->n_used=0;
  32.     ht->n_bucket=n;
  33.     for(int i=0;i<n;i++){
  34.         ht->used[i]=0;
  35.     }
  36.     return ht;
  37. }
  38.  
  39. void HTDestroy(THT*ht){
  40.     free(ht->used);
  41.     free(ht->bucket);
  42.     free(ht);
  43. }
  44.  
  45. TValue HTSearch(THT*ht,TKey key){
  46.     unsigned h=keyHash(key)%ht->n_bucket;
  47.     TInfo info ={key};
  48.     while(ht->used[h] && !infoEqual(info, ht->n_bucket[h])){
  49.         h=(h+1)%ht->n_bucket;
  50.     }
  51.     return(ht->used[h])? &ht->bucket[h].v: NULL;
  52. }
  53.  
  54. void HTinsert(THT*ht, TKey key, TValue value){
  55.     TValue *p=HTSearch(ht, key);
  56.     if(p!=NULL){
  57.         *p=value;
  58.         return;
  59.     }
  60.     //devo procedere al ridimensionamento in mancanza di spazio??
  61.     if(ht->n_used+1>= (ht->n_bucket*GROW_FACTOR)){
  62.         HTresize(ht,GROW_FACTOR*ht->n_bucket+1);
  63.         unsigned int h=keyHash(key)%ht->n_used;
  64.         while(ht->used[h])
  65.             h=(h+1)%ht->n_bucket;
  66.         ht->bucket[h].v=value;
  67.         ht->bucket[h].k=key;
  68.         ht->used[h]=1;
  69.         ht->n_used++;
  70.     }
  71.    
  72. }
  73. //complessita computazionale
  74. //T(n1)+T(n2)=T(n)
  75. void HTresize (THT *ht, int n){
  76.     TInfo* bucket=ht->bucket;
  77.     int* used=ht->used;
  78.     int n_buckets=ht->n_bucket;
  79.     ht->bucket=malloc(sizeof(TInfo)*n);
  80.     ht->used=malloc(sizeof(int)*n);
  81.     assert(ht->bucket!=NULL && ht->used!=NULL);
  82.     ht->n_bucket=n;
  83.     for(int i=0;i<n;i++){
  84.         ht->used[i]=0;
  85.     }
  86.     ht->n_used=0;
  87.    
  88.     for(int i=0;i<n_buckets;i++){
  89.         if(ht->used[i]==1)
  90.             HTinsert(ht,bucket[i].k, bucket[i].v);
  91.     }
  92.     free(bucket);
  93.     free(used);
  94. }
  95.  
  96.  
  97. //complessita computazionale lineare
  98. void HTdelete(THT*ht, TKey key){
  99.     unsigned int h=keyHash(key)%ht->n_bucket;
  100.     //scandisco la tabella finoa che non trovo l'elemento
  101.     TInfo info={key};
  102.     while(ht->used[h] &&!infoEqual(info,ht->bucket[h]))
  103.         h=(h+1)%ht->n_bucket;
  104.     if(!ht->used[h])            //se non lo trova non fa modifiche
  105.         return;
  106.     unsigned int hole=h;        //libero l'elemento
  107.     ht->used[h]=0;
  108.     ht->n_used--;
  109.                                 //scansiono la tabella
  110.     h=(h+1)%ht->n_bucket;       //mi posiziono alla pos. successiva
  111.     while(ht->used[h]){
  112.         //verifico se l'elemento trovato è spostabile o meno
  113.         //ottengo la chiave dell'elemento e l'hashing della chiave
  114.         unsigned int h1=keyHash(ht->bucket[h].k)%ht->n_bucket;
  115.         //valutazione del possibile spostamento della chiave
  116.         if(((h>hole) &&(h1<=hole || h1>h))||(h<hole && h1>h && h1<=hole))
  117.         {
  118.             //cambio l'elemento e i parametri ad esso associati
  119.            ht->bucket[hole]=ht->bucket[h] ;
  120.            ht->used[hole]=1;
  121.            hole=h;
  122.            ht->used[hole]=0;
  123.         }
  124.         //reitero il procedimento per poter modificare il buco successivo creato
  125.         h=(h+1)%ht->n_bucket;
  126.     }
  127.    
  128.    
  129. }
  130.  
  131. //ricerca quadratica
  132. /*
  133.  h(k), |h(k)+c1+c2|m,|h(k)+c1+c2+2c1+2c2|m,...
  134.  * se ipotizzo c1=c2=1/2:
  135.  * h(k), |h(k)+1|m,|h(k)+3|m,...
  136.  *
  137.  * ****problematica: possibile mancanza di confronto tra elementi che vengono saltati
  138.  * ***vantaggio: facilita il caso in cui gli elementi hanno tutti valori di hashing molto simili
  139.  *
  140.  * DOPPIO HASHING
  141.  * determino due funzioni di hashing in base alle quali definisco un valore per determinare
  142.  * l'hashing dell'elemento (combinazione lineare delle due hashing)
  143.  * h1(k),|h1(k)+h2(k)|m, |h1(k) +2h2(k)|m,...
  144.  *
  145.  *
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top