Quel est le problème avec ma fonction de hachage?

Question

J'essaie de créer une table de hachage. Voici mon code:

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

#define N 19 
#define c1 3 
#define c2 5 
#define m 3000 
int efort; 
int h_table[N]; 

int h(int k, int i) 
{ 
    return (k + i*c1 + i*i*c2) % N; 
} 
void init() 
{ 
    for (int i = 0; i < N; i++) 
     h_table[i] = -1; 
} 
void insert(int k) 
{ 
    int position, i; 
    i = 0; 
    do 
    { 
     position = h(k, i); 
     printf("\n Position %d \n", position); 
     if (h_table[position] == -1) 
     {  
      h_table[position] = k; 
      printf("Inserted :elem %d at %d \n", h_table[position], position); 
      break; 
     } 
     else 
     { 
      i += 1; 
     } 
    } while (i != N); 
} 
void print(int n) 
{ 
    printf("\nTable content: \n"); 
    for (int i = 0; i < n; i++) 
    { 
     printf("%d ", h_table[i]); 
    } 

} 


void test() 
{ 
    int a[100]; 
    int b[100]; 
    init(); 
    memset(b, -1, 100); 
    srand(time(NULL)); 
    for (int i = 0; i < N; i++) 
    { 
     a[i] = rand() % (3000 + 1 - 2000) + 2000; 
    } 
    for (int i = 0; i < N ; i++) 
    { 
     insert(a[i]); 
    } 
    print(N); 
} 
int main() 
{ 
    test(); 
    return 0; 
} 

fonction Hash (« h ») et « insérer » la fonction sont pris de .Je ne sais pas « Introduction aux algorithmes » livre (Cormen) ce qui se passe avec la fonction h ou insérer la fonction. Parfois, il remplit complètement mon tableau, mais parfois non. Cela signifie que cela ne fonctionne pas bien. Qu'est-ce que je fais mal?

Answer 1

En bref, vous produisez des valeurs pour répéter position assez souvent pour empêcher h_table[] d'être peuplé après seulement N tentatives ...

Le générateur de nombres pseudo-aléatoires n'est pas garanti pour produire un ensemble de nombres uniques, Votre fonction h(...) ne garantit pas non plus la production d'un ensemble de valeurs de position mutuellement exclusives. Il est probable que vous générez la même position suffisamment de fois que vous n'avez plus de boucles avant que toutes les 19 positions aient été générées. La question combien de fois faut-il appeler h(...) en moyenne avant de pouvoir obtenir la valeur d'une position inutilisée? devrait être répondu. Cela peut vous aider à vous diriger vers le problème.

Comme une expérience, j'augmenté les indices looping N-100 en tout, mais la fonction h(...) (pour ne pas dépasser h_table[]). Et comme prévu les 5 premiers postes se sont immédiatement remplis. Le prochain rempli après 3 autres essais. Le prochain 10 essais plus tard, et ainsi de suite, jusqu'à la fin de 100 essais, il y avait encore des positions non écrites.
Lors de la prochaine exécution, toutes les positions de la table ont été remplies.

2 solutions possibles:
1) Modifier le hachage pour améliorer la probabilité de valeurs uniques.
2) Augmenter les itérations pour remplir h_table

Answer 2

Un good_hash_function() % N peut se répéter dans N re-hash. Un bon hachage ressemble presque aléatoire dans sa sortie même si elle est déterministe. Donc, dans N essais, il pourrait ne pas en boucle à travers tous les éléments du tableau. Après avoir échoué à trouver un élément de tableau libre après un certain nombre d'essais, disons N/3 essais, recommandez une approche différente. Recherchez simplement le prochain élément gratuit.