A little problem about hashmap

[JustDoIt0910]

Hello. I don't understand what's the function of field "used" in the struct sc_map_xxx.

struct sc_map_str {
    struct sc_map_item_str *mem;
    uint32_t cap;
    uint32_t size;
    uint32_t load_fac;
    uint32_t remap;
    _Bool used; // what is this used for?
    _Bool oom;
    _Bool found;
};

[tezc]

Hi @JustDoIt0910

Internally, map uses an array (struct sc_map_item_str *mem above). struct sc_map_item_xx is like:

struct sc_map_item_##name {
    K key; 
    V value;
    uint32_t hash;
}; 

This array contains some key value pairs, some of them are used some of them are not. If the key of an array item is zero (key == 0), it means that item/slot is empty. So, we can place the new item there.

What if user wants to store key=0, (say key = 0, value = 15). How are we going to distinguish between "empty indicator" key=0 and this valid item?

Hashmap does a trick, if user wants to put key=0, hashmap stores it as the first item: https://github.com/tezc/sc/blob/f0bb6d9813010d69d142aff123366e56348d289f/map/sc_map.c#L232

So, how do you know if that special slot is empty or not? Hashmap uses used boolean for that. If user puts key=0 to the map, it will be stored as the first item and used value will be true. So, when user calls get(key=0), we'll know if there is a real value in that special slot.

For pointer types (like str, void*), special key is NULL btw.

Let me know if this is clear. Cheers!

[JustDoIt0910]

Yes, it's clear. I understand, thank you very much!