Stocker des entiers dans des tables de hachage implémentées par c?

Question

Actuellement, j'ai une implémentation de table de hachage en C qui utilise des chaînes comme clés et valeurs. Si je voulais stocker des entiers au lieu de chaînes comme valeurs, quelle serait la meilleure façon de le faire? Je pense à stocker l'entier dans une chaîne et à le convertir en entier quand j'en ai besoin, mais cela semble inefficace pour l'arithmétique. Quelque chose comme

insert("money", "13"); 
int i = atoi(get("key1")); 
int sum = i + 10; 
insert("money", itoa(sum)); 

Y at-il une meilleure façon de le faire?

EDIT: table de hachage mise en œuvre

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

typedef struct tableentry /* hashtab entry */ 
{ 
    struct tableentry *next; 
    char *key; 
    char *val; 
} tableentry_t; 

typedef struct hashtable 
{ 
    size_t size; 
    struct tableentry **tab; 
} hashtable_t; 

/* creates hashtable */ 
/* NOTE: dynamically allocated, remember to ht_free() */ 
hashtable_t *ht_create(size_t size) 
{ 
    hashtable_t *ht = NULL; 
    if ((ht = malloc(sizeof(hashtable_t))) == NULL) 
     return NULL; 
    /* allocate ht's table */ 
    if ((ht->tab = malloc(sizeof(tableentry_t) * size)) == NULL) 
     return NULL; 
    /* null-initialize table */ 
    int i; 
    for (i = 0; i < size; i++) 
     ht->tab[i] = NULL; 
    ht->size = size; 
    return ht; 
} 

/* creates hash for a hashtab */ 
static unsigned hash(hashtable_t *ht, char *s) 
{ 
    unsigned hashval; 
    for (hashval = 0; *s != '\0'; s++) 
     hashval = *s + 31 * hashval; 
    return hashval; 
} 

/* loops through linked list freeing */ 
static void te_free(tableentry_t *te) 
{ 
    tableentry_t *next; 
    while (te != NULL) 
    { 
     next = te->next; 
     free(te->key); 
     free(te->val); 
     free(te); 
     te = next; 
    } 
} 

/* creates a key-val pair */ 
static tableentry_t *new(char *k, char *v) 
{ 
    tableentry_t *te = NULL; 

    if ((te = calloc(1, sizeof(*te))) == NULL 
     || (te->key = strdup(k)) == NULL 
     || (te->val = strdup(v)) == NULL) 
    { 
     te_free(te); 
     return NULL; 
    } 
    te->next = NULL; 
    return te; 
} 

static tableentry_t *lookup(hashtable_t *ht, char *k) 
{ 
    tableentry_t *te; 
    /* step through linked list */ 
    for (te = ht->tab[hash(ht, k) % ht->size]; te != NULL; te = te->next) 
     if (strcmp(te->key, k) == 0) 
      return te; /* found */ 
    return NULL; /* not found */ 
} 

/* inserts the key-val pair */ 
hashtable_t *ht_insert(hashtable_t *ht, char *k, char *v) 
{ 
    tableentry_t *te; 
    /* unique entry */ 
    if ((te = lookup(ht, k)) == NULL) 
    { 
     te = new(k, v); 
     unsigned hashval = hash(ht, k) % ht->size; 
     /* insert at beginning of linked list */ 
     te->next = ht->tab[hashval]; 
     ht->tab[hashval] = te; 
    } 
    /* replace val of previous entry */ 
    else 
    { 
     free(te->val); 
     if ((te->val = strdup(v)) == NULL) 
      return NULL; 
    } 
    return ht; 
} 

/* retrieve value from key */ 
char *ht_get(hashtable_t *ht, char *k) 
{ 
    tableentry_t *te; 
    if ((te = lookup(ht, k)) == NULL) 
     return NULL; 
    return te->val; 
} 

/* frees hashtable created from ht_create() */ 
void ht_free(hashtable_t *ht) 
{ 
    int i; 
    for (i = 0; i < ht->size; i++) 
     if (ht->tab[i] != NULL) 
      te_free(ht->tab[i]); 
    free(ht); 
} 

/* resizes hashtable, returns new hashtable and frees old*/ 
hashtable_t *ht_resize(hashtable_t *oht, size_t size) 
{ 
    hashtable_t *nht; /* new hashtable */ 
    nht = ht_create(size); 
    /* rehash */ 
    int i; 
    tableentry_t *te; 
    /* loop through hashtable */ 
    for (i = 0; i < oht->size; i++) 
     /* loop through linked list */ 
     for (te = oht->tab[i]; te != NULL; te = te->next) 
      if (ht_insert(nht, te->key, te->val) == NULL) 
       return NULL; 
    ht_free(oht); 
    return nht; 
} 

Answer 1

Les fonctions d'accès et de manipulation associées à l'implémentation de la table de hachage suppose que les valeurs ont la forme de chaînes terminées par null, et que leur signification est réalisée entièrement par leur contenu (pas, par exemple, par les valeurs des pointeurs eux-mêmes). Entre autres choses, cela est évident du fait que les fonctions new() et ht_insert() font des copies des valeurs fournies via strdup(). Par conséquent, si vous avez l'intention d'utiliser ces fonctions (pas seulement les structures de données sous-jacentes), votre seule alternative pour stocker des entiers est de coder les entiers dans des chaînes d'une manière ou d'une autre et de stocker les chaînes. C'est ce que vous avez déjà trouvé. Notez, en passant, que cela pose un problème si vous voulez pouvoir stocker à la fois des chaînes et des entiers dans la même table de hachage. Les entrées de table ne fournissent aucun moyen d'enregistrer les métadonnées de type de données. Pour éviter les collisions entre les représentations de chaînes et de nombres, vous devez encoder les types de données dans les valeurs que vous stockez, non seulement pour les entiers mais aussi pour les chaînes. . Par exemple, vous pouvez encoder des valeurs dans des chaînes dont le premier caractère communique le type de données. Ainsi, peut-être "S12345" représente la chaîne"12345", tandis que "I12345" représente le entier12345. Mais vous n'avez pas besoin de telles astuces si vous supposez que toutes les valeurs sont de type uniforme, table par table.

Vous auriez plus d'options si vous étiez prêt à écrire au moins un ensemble partiel de fonctions de table de hachage alternatives pour stocker des entiers dans les structures de données existantes. Par exemple, vous pouvez utiliser le fait que les pointeurs et les entiers peuvent être convertis d'avant en arrière (avec des résultats définis par l'implémentation). Mais je vous interprète comme ayant rejeté de telles approches, car l'utilisation de fonctions alternatives est en fait la même chose que la modification de la mise en œuvre.