C hashmap (broken: too many collissions)

broken_hashmap.c

// https://stackoverflow.com/a/838413

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#define CAP 10000
#define Dict(keyT, valueT) struct { \
        int set[CAP]; \
        keyT keys[CAP]; \
        valueT values[CAP]; \
    }

#define Dict_set(dict, key, value) \
    _Dict_set(&(__typeof((key))){(key)}, &(__typeof((value))){(value)}, &dict.keys, &dict.values, dict.set, sizeof (dict.keys[0]), sizeof (dict.values[0]))

#define Dict_get(dict, key, dst) \
    _Dict_get(&(__typeof((key))){(key)}, &dict.keys, &dict.values, dict.set, &(dst), sizeof (dst), sizeof (dict.keys[0]), sizeof (dict.values[0]))

#define Dict_init(dict) \
    _Dict_init(&dict.keys, &dict.values, dict.set, sizeof (dict.keys[0]), sizeof (dict.values[0]))

int64_t hash(void *data, size_t size) {
    int64_t res = 1;
    for (size_t i = 0; i < size; ++i) {
        uint64_t h = ((uint8_t*)data)[i];
        h |= h == 0;
        res *= h;
        res += (97 * h) << 1;
    }
    return res;
}

void _Dict_set(void *key, void *value, void *keys, void *values, int set[CAP], size_t key_sz, size_t value_sz) {
    int64_t k_hash_idx = hash(key, key_sz) % CAP;
    memcpy(keys + (k_hash_idx * key_sz), key, key_sz);
    memcpy(values + (k_hash_idx * value_sz), value, value_sz);
    set[k_hash_idx] = 1;
}

int _Dict_get(void *key, void *keys, void *values, const int set[CAP], void *dst, size_t dst_sz, size_t key_sz, size_t value_sz) {
    if (dst_sz != value_sz) goto error;
    int64_t k_hash_idx = hash(key, key_sz) % CAP;
    if (!set[k_hash_idx]) goto error;

    void *_temp_key = malloc(key_sz);
    if (_temp_key == NULL) goto error;

    memcpy(_temp_key, keys + (k_hash_idx * key_sz), key_sz);
    int64_t _check_collision = hash(_temp_key, key_sz) % CAP;
    free(_temp_key);

    if (_check_collision != k_hash_idx) {
        for (size_t i = 0; i < CAP; ++i) {
            if (memcmp(key, keys + (i * key_sz), key_sz) == 0) {
                memcpy(dst, values + (k_hash_idx * value_sz), value_sz);
                return 0;
            }
        }
        return -1;
    }

    memcpy(dst, values + (k_hash_idx * value_sz), value_sz);
    return 0;

error:
    return -1;
}

void _Dict_init(void *keys, void *values, int set[CAP], size_t key_sz, size_t value_sz) {
    memset(keys, 0, key_sz);
    memset(values, 0, value_sz);
    memset(set, 0, sizeof (set[0]));
}

int main(void) {
    Dict(int, int) d;
    Dict_init(d);

    for (int i = 1; i < CAP; ++i) {
        Dict_set(d, i, i);
    }

    for (int key = 1; key < CAP; ++key) {
        int got = -1;
        if (Dict_get(d, key, got) != 0) {
            printf("Failure in Dict_get\n");
            return (EXIT_FAILURE);
        };
        printf("Key: %d, val: %d\n", key, got);
    }

    return (EXIT_SUCCESS);
}