Tra i metodi di ricerca più efficenti vi è senza ombra di dubbio la Ricerca Hash.
L’idea su cui si basa è quella che per trovare velocemente un elemento, basta sapere dove è stato messo. (Nei grandi Mainframe esistono delle vere e proprie tabelle hash, che rendono quasi immediata la ricerca), noi useremo semplicemente una funzione (che se pur non iniettiva) permette con un sistema di gestione delle collissioni, di trovare al primo colpo o al massimo al 2/3 confronto l’elemento che cerchiamo, mentre con massimo 5/6 confronti sappiamo se quell’elemento non è presente.

In un certo senso, questo metodo di ricerca ricalca un pò l’ordinamento per inserimento diretto, ad esempio il Permutation sort… Fondamentalmente se usasse una funzione per inserire i propri elementi, sarebbe proprio la funzione identità che ad un f(x) = x (ovvero ad x associa x stessa). (noi nella ricerca hash non useremo la funzione identità per inserire gli elementi, perchè per chiavi molto grandi avremo bisogno di un array altrettanto grande).

Nell’inserimento hash è consuetudine quindi, usare funzioni che non siano iniettive e che se pur associano y uguali ad x diverse ci consentono di non sprecare troppa memoria.. e con un sistema di gestione delle collisioni, vanno più che bene.

La complessità computazionale dell’algoritmo di ricerca hash è: Alpha = m/n detto anche Fattore di carico, (dipende quindi da questo fattore). Dove m è il numero di elementi presenti (nel nostro array in questo caso), ed n è la dimensione dell’array.

Passiamo all’implementazione in linguaggio C, definiamo prima la struttura, poi una funzione per inizializzare l’array di strutture, una funzione per l’inserimento di un elemento e infine una funzione per la ricerca di un elemento nell’array. In coda a tutto il main che richiama le varie funzioni per un breve esempio pratico:

/*
RICERCA HASH.
inizializzazione.
inserimento di un elemento.
ricerca di un elemento (secondo il campo chiave).
*/
 
typedef struct{
        long int chiave;
        int attributo;
        }t_elem_tavola;
 
void inizializza(t_elem_tavola a[], int n){
     int i;
 
     for (i = 0; i < n; i++)
       a[i].chiave = -1;
 
     }
 
int inserimento_hash(t_elem_tavola a[], int n, t_elem_tavola x){
    //useremo la funzione modulo, per trovare l'indice in cui inserire l'elemento
    int k, nk;
    k = x.chiave % n;
    if (a[k].chiave == -1) a[k] = x;
    else{ nk = k;
         do{
           nk = (nk + 1) % n;
           }while((nk!=k)&&(a[nk].chiave != -1));
 
         if (nk == k) return 1; //non c'è più spazio. Avrà fatto un giro completo dell'array senza trovare posto
         else
          a[nk] = x;
 
         }    
 
    return 0;
    }
 
int ricerca(t_elem_tavola a[], int n, long int x){ //ricerchiamo una chiave x, in un array a[]
    int k, nk;
    t_elem_tavola temp;
    k = x % n;
    if (a[k].chiave == x) return k;
    else{ //altrimenti non l'ha trovato in quel posto, scorriamo in avanti l'array.
         nk = k;
         temp = a[k];
         a[k].chiave = x; //ce la mettiamo noi, se la ritrova nello stesso punto allora l'elemento non c'è nel'array
         do{
          nk = (nk+1) % n;
           }while((a[nk].chiave != x)&&(a[nk].chiave != -1));
 
         a[k] = temp;
         if (a[nk].chiave != x) return -1; //ha fatto un giro completo senza trovarlo.
         else return nk;
          }    
 
    }

Programma di esempio:

int main(){
         t_elem_tavola a[] = {{3, 56}, {40, 13}, {1, 5}, {8, 9}, {12, 7}, {3, 22}, {4, 66}, {13, 44}, {0, 100}, {7, 10}};
         t_elem_tavola b[10];
 
         int i, x;
 
         //printf("\n\n%d - % d\n\n", a[0].chiave, a[0].attributo);
          printf("Chiave:Attributo dell'array iniziale a[]:\n");
          for(i = 0; i < 10; i++)
           printf("%d:%d - ", a[i].chiave,a[i].attributo);
 
         inizializza(b, 10); //inizializziamo ogni chiave di b a -1
         for (i = 0; i < 10; i++)
           inserimento_hash(b, 10, a[i]); //inseriremo in b[] i nostri elementi disposti in modo da ritrovarli subito con la ricerca hash.
 
         printf("\n\nChiave:Attributo dell'array b[] con elementi di a[] inseriti tramite funzione modulo:\n");
         for(i = 0; i < 10; i++) //stampiamo l'array con gli elementi disposti secondo la funzione modulo (inserimento).
           printf("%d:%d - ", b[i].chiave, b[i].attributo);
 
         printf("\n\nInserisci la chiave dell'elemento da cercare: ");
         scanf("%d", &x);
         i = ricerca(b, 10, x);
         if (i >= 0)
           printf("\n\nL'elemento con chiave %d si trova nella posizione %d ed il valore associato e': %d \n", x, i, b[i].attributo);
         else
           printf("\n\nL'elemento con chiave %d non e' presente!\n", x);
 
          system("PAUSE");
          return 0;
           }