Quelqu'un a écrit un dictionnaire (hashmap) en ANSI C?

Question

Je me demandais juste si quelqu'un pouvait me donner quelques conseils (sans jeu de mots) comment faire cela?

Je veux mettre de côté 4 Go de ram afin de mapper des nombres à la mémoire qui me sauve en parcourant une liste liée vérifiant s'ils sont là. Donc, au lieu d'avoir (1,2,3,4,8,34,543,2343) et traversant 8 éléments pour vérifier que '2343' est dans la liste, je veux être en mesure de rechercher la clé 2343 ' en O (1) fois?

Merci à l'avance

Answer 1

Je vous conseille l'intégration Lua dans votre projet. Facile à intégrer et entièrement ANSI C avec une structure de données collectées très flexible (une table Lua/aka hashmap). Vous pouvez toujours enlever les bits dont vous n'avez pas besoin, mais même si vous n'avez pas Lua est minuscule.

Lua a une pile API basée sur ce qui est pas trop difficile à suivre:

lua_State *L = luaL_newstate(); // make a new lua state 
    lua_newtable(L); // pushes a new table to the top of the stack (position 1) 

    // storing values 
    lua_pushinteger(2343); // key: 2343 
    lua_pushboolean(1); // value: true 
    lua_settable(L, 1); // pop key/value, store in table at position 1 

    // retrieving values 
    lua_pushinteger(2343); // key we're looking for 
    lua_gettable(L, 1); // get from table at top of stack - 2; pops key 
    if (lua_toboolean(L, -1)) // is it a true value? 
    { 
    // executes; we know 2343 is true as we pushed it just above 
    } 
    lua_pop(L, 1); // pop it off the stack; only our table remains 

Et vous pouvez itérer sur les valeurs aussi bien, peut-être faire disparaître la nécessité de votre liste chaînée (mais l'ordre de l'itération est non-déterminée). Manuel complet here.

Answer 2

Si les nombres sont 32 bits, vous n'avez même pas besoin de hachage, utilisez simplement un tableau.

Answer 3

Si vous avez seulement besoin de vérifier si le numéro existe dans la liste, vous pouvez essayer de créer un bitmap.

Si les nombres vont être dispersés sur une large plage comme 100 000 valeurs dans la gamme 0-4billion, alors une Hashtable serait plus rapide. Pour une implémentation C d'une table hachage take a look at GLib's Hashtable. Un bitmap peut contenir les nombres 0-4 294 967 295 en utilisant seulement 512 Mo de RAM.

#include <stdlib.h> 
#include <stdint.h> 
#include <stdbool.h> 
#include <assert.h> 

#define BITMAP_TEST 1 

#define BITMAP_32_WORD 1 

typedef struct Bitmap Bitmap; 
#if BITMAP_32_WORD 
#define BITWORD_BITS_SHIFT 5 
typedef uint32_t Bitword; 
#else 
#define BITWORD_BITS_SHIFT 6 
typedef uint64_t Bitword; 
#endif 
#define BITWORD_BITS (sizeof(Bitword) * 8) 
#define BITWORD_BITS_MASK (BITWORD_BITS - 1) 
#define BITWORD_MULT(bit) ((bit + (BITWORD_BITS_MASK)) & ~(BITWORD_BITS_MASK)) 
#define BITWORD_TEST(bword, bit) ((bword >> bit) & 1) 

#define BITMAP_WORD_COUNT(bit) (BITWORD_MULT(bit) >> BITWORD_BITS_SHIFT) 


struct Bitmap { 
    size_t length; 
    Bitword *bitmap; 
}; 

extern Bitmap *bitmap_new(size_t len) { 
    Bitmap *bitmap = malloc(sizeof(Bitmap)); 
    bitmap->length = len; 
    bitmap->bitmap = calloc(BITMAP_WORD_COUNT(len),sizeof(Bitword)); 
    return bitmap; 
} 

extern void bitmap_free(Bitmap *bitmap) { 
    free(bitmap->bitmap); 
    free(bitmap); 
} 

extern void bitmap_set(Bitmap *bitmap, size_t bit) { 
    assert(bit < bitmap->length); 
    bitmap->bitmap[(bit >> BITWORD_BITS_SHIFT)] |= ((Bitword)1 << (bit & BITWORD_BITS_MASK)); 
} 

extern void bitmap_unset(Bitmap *bitmap, size_t bit) { 
    assert(bit < bitmap->length); 
    bitmap->bitmap[(bit >> BITWORD_BITS_SHIFT)] &= ~((Bitword)1 << (bit & BITWORD_BITS_MASK)); 
} 

extern bool bitmap_test(Bitmap *bitmap, size_t bit) { 
    assert(bit < bitmap->length); 
    Bitword bword = bitmap->bitmap[(bit >> BITWORD_BITS_SHIFT)]; 
    return BITWORD_TEST(bword, (bit & BITWORD_BITS_MASK)); 
} 

#ifdef BITMAP_TEST 
#include <stdio.h> 

#define MAX_VALUE (2343 + 1) 
static const uint32_t test_values[] = { 1,2,3,4,8,34,543,2343 }; 
#define test_values_len (sizeof(test_values)/sizeof(uint32_t)) 

static void set_values(Bitmap *bitmap, const uint32_t *values, int len) { 
    int i; 
    for(i=0; i < len; i++) { 
     bitmap_set(bitmap, values[i]); 
    } 
} 

static void unset_values(Bitmap *bitmap, const uint32_t *values, int len) { 
    int i; 
    for(i=0; i < len; i++) { 
     bitmap_unset(bitmap, values[i]); 
    } 
} 

static void check_values(Bitmap *bitmap, const uint32_t *values, int len, bool is_set) { 
    int i; 
    for(i=0; i < len; i++) { 
     assert(bitmap_test(bitmap, values[i]) == is_set); 
    } 
} 

int main(int argc, char *argv[]) { 
    Bitmap *bitmap = bitmap_new(MAX_VALUE); 

    set_values(bitmap, test_values, test_values_len); 

    check_values(bitmap, test_values, test_values_len, true); 

    unset_values(bitmap, test_values, test_values_len); 

    check_values(bitmap, test_values, test_values_len, false); 

    bitmap_free(bitmap); 
    return 0; 
} 

#endif 

Answer 4

Une hashtable est en réalité seulement O (1) lorsqu'il n'y a pas de clés qui ont le même hachage.

Pour une version courte facile d'une table de hachage dans le regard C ici: http://pokristensson.com/strmap.html