CODEWITHSUNDEEP
chashhashtablecollision-detection
KarimS
KarimS

Reputation: 3892

open addressing collision resolution

I faced a difficulty while implementing open addressing hash table in the c programming language:

#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

So here I use a array of struct kv_pairs, to hold my keys and value, the problem is that i must have 3 special values: DELETED, USED, FREE to indicate that the location is deleted/used/free, I don't know how to encode these value?

I tried to set struct kv_pairs able and set FREE 0x0 DELETED 0x1 and USED 0x2, and doing the comparison like that

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

Upvotes: 0

Views: 71

Answers (1)

sonologico
sonologico

Reputation: 764

The question is a bit confusing and I'm supposing that you're not trying to access already freed memory (which your question makes me think you are). Adding an enum tag to struct kv_pair would be an easy solution

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

Or you could add a separate array (possibly allocated together) of tags to 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);
};

The one to choose would depend on the common memory access pattern, but both would increase the memory usage of the data structure. A third solution with no memory increase (that seems to be what you want) could be the following:

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

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

You would check the tag only if key is NULL and if not, it's in use.

Upvotes: 1

Related Questions