Кто-нибудь написал словарь (hashmap) в ANSI C?

Question

Мне просто интересно, может ли кто-нибудь дать мне несколько советов (без каламбура), как это сделать?

Я хочу выделить 4 ГБ оперативной памяти, чтобы сопоставить числа с памятью, что спасает меня при обходе связанныхпроверка списка, если они там.

Таким образом, вместо того, чтобы иметь (1,2,3,4,8,34,543,2343) и обходить 8 элементов, чтобы убедиться, что «2343» находится в списке, я хочу иметь возможность искать ключ'2343' в O (1) раз?

Заранее спасибо

Answer 1

Если вам нужно только проверить, существует ли номер в списке, вы можете попытаться создать растровое изображение.

Если числа будут разбросаны по большому диапазону, например 100 000 значений в диапазоне 0-4 миллиардов, то Hashtable будет быстрее. Для реализации Hashtable на C взгляните на Hashtable GLib .

Растровое изображение может содержать числа 0-4,294,967,295, используя только 512 Мбайт оперативной памяти.

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

Если числа 32-битные, вам даже не нужно хэшировать, просто используйте массив.

Answer 3

Хеш-таблица на самом деле является только O (1), когда нет ключей с таким же хеш-значением.

Для простой короткой версии хеш-таблицы в C смотрите здесь: http://pokristensson.com/strmap.html

Answer 4

Я бы посоветовал встраивать Lua в ваш проект.Простое встраивание и полностью ANSI C с одной очень гибкой структурой данных для сбора мусора (таблица Lua / он же hashmap).Вы всегда можете удалить ненужные биты, но даже если вы этого не сделаете, 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

И вы также можете перебирать значения, возможно, избавляясь от необходимости вашего связанного списка (но порядок итерации не определен).Полное руководство здесь .