c - 开放寻址冲突解决

Question

我在用 C 编程语言实现开放寻址哈希表时遇到了困难:

#ifndef COMDS_OPENADDR_HASH_TABLE
#define COMDS_OPENADDR_HASH_TABLE

#define COMDS_KEY_EXIST 1
#define COMDS_REALLOC_FAIL  2

struct kv_pairs {
    void *key;
    void *value;
};

typedef struct openaddr_hash_table {
    size_t buckets;
    size_t used;
    size_t (*hash)(void *data);
    struct kv_pairs *table; 
    int (*key_equal)(void *fkey, void *skey);
    int (*value_equal)(void *fvalue, void *svalue);
}OpenAddrHashTable;
#endif

所以在这里我使用了一个 struct kv_pairs 数组来保存我的键和值，问题是我必须有 3 个特殊值:DELETED、USED、< strong>FREE 表示该位置已删除/已使用/免费，我不知道如何对这些值进行编码？

我尝试将struct kv_pairs设置为able，并设置FREE 0x0 DELETED 0x1和USED 0x2，并进行这样的比较

table[i] == FREE || table[i] == (struct kv*)DELETED

Answer 1

这个问题有点令人困惑，我假设您没有尝试访问已经释放的内存(您的问题让我认为您是这样)。向 struct kv_pair 添加枚举标记将是一个简单的解决方案

struct kv_pair {
    enum { KV_PAIR_FREE, KV_PAIR_DELETED, KV_PAIR_USED } tag;
    void *key;
    void *value;
};

或者您可以添加一个单独的标签数组(可能一起分配)到 struct openaddr_hash_table

enum tag { KV_PAIR_FREE, KV_PAIR_DELETED, KV_PAIR_USED};
struct openaddr_hash_table {
    size_t buckets;
    size_t used;
    size_t (*hash)(void *data);
    struct kv_pairs *table;
    enum tag *tags;
    int (*key_equal)(void *fkey, void *skey);
    int (*value_equal)(void *fvalue, void *svalue);
};

选择哪一种取决于常见的内存访问模式，但两者都会增加数据结构的内存使用量。第三种不增加内存的解决方案(这似乎是您想要的)可能如下:

#include <stdint.h>
#define FREE 0
#define DELETED 1

struct kv_pair {
    void *key;
    union {
        void *value;
        uintptr_t tag;
    } value;
};

只有当 key 为 NULL 时，您才会检查标签，如果不是，则它正在使用中。