当前位置：文江博客话题详情

C99 中的 HashTable 和类似 Vector 的数据结构

发布于 2024-12-12 11:49:13 字数 179 浏览 0 评论 0原文

我想在C99中创建一个依赖于独立向量数据结构的哈希表。我可以在 OO 的帮助下在 C++ 中做到这一点，但我不确定如何使用结构和联合来实现这一点。

我希望任何链接的示例都不包含具有高度复杂的哈希函数的哈希表实现。我并不特别关心碰撞或存储效率。我只想要有关如何进行的建议，或者一个简单的示例来举例说明各个数据结构的形式而不是功能。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

魂ガ小子 2024-12-19 11:49:13

如果我正确地推断您希望以完全通用的方式实现不断增长的哈希表，那么您将需要大量 void 指针。向量并不太难，只是需要大量输入：

typedef struct {
    size_t capacity, nelems;
    void **contents;
} Vector;

enum { INITIAL_CAPACITY = 256 };

Vector *make_vector()
{
    Vector *v = malloc(sizeof(Vector));
    if (v == NULL)
        return NULL;
    v->capacity = INITIAL_CAPACITY;
    v->contents = malloc(sizeof(void *) * v->capacity);
    if (v->contents == NULL) {
        free(v);
        return NULL;
    }
    v->nelems = 0;
    return v;
}

// exercise for the reader
int vector_append(Vector *, void *);
void *vector_at(Vector const *);

请记住，通用哈希函数将具有原型 size_t hash(void const *, size_t)，即您需要传入尺寸。

（旁注：您会错过的不是 C++ 的 OOP 功能；而是模板、他们购买的类型安全性以及运算符重载等语法糖。看看 OpenBSD 的 ohash 库了解更多示例。）

If I infer correctly that you want to implement growing hash tables in a fully generic way, then you'll need a lot of void pointers. A vector isn't too hard, it just takes a lot of typing:

typedef struct {
    size_t capacity, nelems;
    void **contents;
} Vector;

enum { INITIAL_CAPACITY = 256 };

Vector *make_vector()
{
    Vector *v = malloc(sizeof(Vector));
    if (v == NULL)
        return NULL;
    v->capacity = INITIAL_CAPACITY;
    v->contents = malloc(sizeof(void *) * v->capacity);
    if (v->contents == NULL) {
        free(v);
        return NULL;
    }
    v->nelems = 0;
    return v;
}

// exercise for the reader
int vector_append(Vector *, void *);
void *vector_at(Vector const *);

Keep in mind that a generic hash function would have prototype size_t hash(void const *, size_t), i.e. you need to pass in the size.

(Side note: it's not C++'s OOP features that you're going to miss; it's templates, the type safety that they buy, and syntactic sugar such as operator overloading. Take a look at OpenBSD's ohash library for more examples.)

回复收藏 0 原文