有人用 ANSI C 写过字典（哈希图）吗？

Question

我只是想知道是否有人可以给我一些指示（没有双关语）如何做到这一点？

我想留出 4GB 内存，以便将数字映射到内存，这样我就不用遍历链表来检查它们是否存在。

因此，我希望能够在 O( 中查找键“2343”，而不是使用 (1,2,3,4,8,34,543,2343) 并遍历 8 个元素来验证“2343”是否在列表中1）时间？

提前致谢

Answer 1

我建议在您的项目中嵌入 Lua 。易于嵌入且完全符合 ANSI C，具有一种非常灵活的垃圾收集数据结构（Lua 表/又名哈希图）。你总是可以去掉不需要的部分，但即使你不这样做，Lua 也是很小的。

Lua 有一个基于堆栈的 API，这并不难理解：

  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

您也可以迭代这些值，可能不需要链表（但迭代的顺序是不确定的）。完整手册此处。

Answer 2

如果您只需要检查列表中是否存在该数字，则可以尝试制作位图。

如果数字稀疏地分布在一个大范围内，例如 0-40 亿范围内的 100,000 个值，那么哈希表会更快。对于 Hashtable 的 C 实现看看 GLib 的 Hashtable。

位图仅使用 512 MB 的 RAM 即可保存数字 0-4,294,967,295。

#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 3

如果数字是 32 位，则甚至不需要散列，只需使用数组即可。

Answer 4

当没有具有相同哈希值的键时，哈希表实际上只有 O(1)。

有关 C 中哈希表的简单简短版本，请参见此处：
http://pokristensson.com/strmap.html