Open addressing

/* Dò tuyến tính: thử ô i, rồi i+1, i+2, ... quay vòng */
size_t i = bam(key) % n;

while (o[i].trang_thai == DANG_DUNG && strcmp(o[i].key, key) != 0)
    i = (i + 1) % n;

/* Kết thúc vòng lặp thì hoặc o[i] trống, hoặc o[i].key bằng key. */

/* 1. Dò tuyến tính: i, i+1, i+2, i+3, ... */
size_t vi_tri(size_t h, size_t k, size_t n) { return (h + k) % n; }

/* 2. Dò bậc hai: i, i+1, i+4, i+9, i+16, ... */
size_t vi_tri(size_t h, size_t k, size_t n) { return (h + k * k) % n; }

/* 3. Băm kép: i, i+h2, i+2*h2, i+3*h2, ... với h2 là hàm băm thứ hai */
size_t vi_tri(size_t h, size_t k, size_t n, size_t h2)
{
    return (h + k * h2) % n;
}

/* h2 PHẢI nguyên tố cùng nhau với n, nếu không phép dò
   chỉ chạm được một phần các ô và có thể lặp vô hạn.
   Cách thường dùng khi n là lũy thừa của 2:  h2 = 2 * (h2_tho % (n/2)) + 1
   tức luôn là số lẻ, mà số lẻ thì nguyên tố cùng nhau với 2 mũ k. */

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

#define N 64

int main(void)
{
    int o[N] = { 0 };

    srand(42);

    for (int da_dien = 0; da_dien < 56; ++da_dien) {
        size_t i = (size_t)(rand() % N);

        while (o[i]) i = (i + 1) % N;      /* dò tuyến tính */

        o[i] = 1;

        if ((da_dien + 1) % 14 == 0) {
            printf("sau %2d khoa (tai %.2f): ", da_dien + 1,
                   (double)(da_dien + 1) / N);

            int cum_dai_nhat = 0, cum = 0;

            for (int k = 0; k < N; ++k) {
                putchar(o[k] ? '#' : '.');

                if (o[k]) { ++cum; if (cum > cum_dai_nhat) cum_dai_nhat = cum; }
                else      cum = 0;
            }

            printf("  cum dai nhat %d\n", cum_dai_nhat);
        }
    }

    return 0;
}

#ifndef OAHASH_H
#define OAHASH_H

#include <stddef.h>

typedef enum { O_TRONG = 0, O_DANG_DUNG, O_BIA_MO } TrangThaiO;

typedef struct {
    char       *key;          /* NULL khi trống hoặc bia mộ */
    int         value;
    TrangThaiO  trang_thai;
} O;

/* Bất biến:
     1. n_o là lũy thừa của 2, ít nhất bằng 8
     2. size + so_bia_mo <= n_o * 7 / 10
     3. Mọi khóa xuất hiện nhiều nhất một lần
     4. trang_thai == O_DANG_DUNG  khi và chỉ khi  key != NULL      */
typedef struct {
    O     *o;
    size_t n_o;
    size_t size;
    size_t so_bia_mo;
} OAMap;

OAMap *oa_tao(size_t n_o);
void   oa_huy(OAMap *m);
int    oa_put(OAMap *m, const char *key, int value);
int    oa_get(const OAMap *m, const char *key, int *ra);
int    oa_remove(OAMap *m, const char *key);

#endif

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

#include "oahash.h"

#define KHONG_CO ((size_t)-1)

static unsigned long bam(const char *s)
{
    unsigned long h = 2166136261u;      /* FNV-1a, tron bit tot hon djb2 */

    for (; *s != '\0'; ++s) {
        h ^= (unsigned char)*s;
        h *= 16777619u;
    }

    return h;
}

OAMap *oa_tao(size_t n_o)
{
    if (n_o < 8 || (n_o & (n_o - 1)) != 0) return NULL;   /* phải là lũy thừa của 2 */

    OAMap *m = malloc(sizeof *m);

    if (m == NULL) return NULL;

    m->o = calloc(n_o, sizeof *m->o);      /* O_TRONG là 0, key là NULL */

    if (m->o == NULL) { free(m); return NULL; }

    m->n_o       = n_o;
    m->size      = 0;
    m->so_bia_mo = 0;

    return m;
}

/* Tìm chỉ số ô chứa key, hoặc KHONG_CO. */
static size_t tim_o(const OAMap *m, const char *key)
{
    size_t h = (size_t)bam(key) & (m->n_o - 1);

    for (size_t k = 0; k < m->n_o; ++k) {
        size_t i = (h + k) & (m->n_o - 1);

        if (m->o[i].trang_thai == O_TRONG) return KHONG_CO;   /* hết chuỗi dò */

        if (m->o[i].trang_thai == O_DANG_DUNG &&
            strcmp(m->o[i].key, key) == 0)
            return i;

        /* O_BIA_MO thì đi tiếp */
    }

    return KHONG_CO;      /* đã quét hết bảng */
}

int oa_get(const OAMap *m, const char *key, int *ra)
{
    if (m == NULL || key == NULL) return -1;

    size_t i = tim_o(m, key);

    if (i == KHONG_CO) return -1;

    if (ra != NULL) *ra = m->o[i].value;

    return 0;
}

int oa_put(OAMap *m, const char *key, int value)
{
    if (m == NULL || key == NULL) return -1;

    if ((m->size + m->so_bia_mo + 1) * 10 > m->n_o * 7)
        if (oa_rehash(m, m->n_o * 2) != 0) return -1;

    size_t h        = (size_t)bam(key) & (m->n_o - 1);
    size_t ung_vien = KHONG_CO;

    for (size_t k = 0; k < m->n_o; ++k) {
        size_t i = (h + k) & (m->n_o - 1);

        if (m->o[i].trang_thai == O_TRONG) {
            size_t dich = (ung_vien != KHONG_CO) ? ung_vien : i;
            size_t n    = strlen(key) + 1;
            char  *ban  = malloc(n);

            if (ban == NULL) return -1;

            memcpy(ban, key, n);

            if (m->o[dich].trang_thai == O_BIA_MO) --m->so_bia_mo;

            m->o[dich].key        = ban;
            m->o[dich].value      = value;
            m->o[dich].trang_thai = O_DANG_DUNG;
            ++m->size;

            return 0;
        }

        if (m->o[i].trang_thai == O_BIA_MO) {
            if (ung_vien == KHONG_CO) ung_vien = i;

            continue;
        }

        if (strcmp(m->o[i].key, key) == 0) {
            m->o[i].value = value;

            return 1;
        }
    }

    return -1;      /* bảng đầy, không xảy ra nếu bất biến 2 được giữ */
}

int oa_remove(OAMap *m, const char *key)
{
    if (m == NULL || key == NULL) return -1;

    size_t i = tim_o(m, key);

    if (i == KHONG_CO) return -1;

    free(m->o[i].key);
    m->o[i].key        = NULL;
    m->o[i].trang_thai = O_BIA_MO;
    --m->size;
    ++m->so_bia_mo;

    return 0;
}

void oa_huy(OAMap *m)
{
    if (m == NULL) return;

    for (size_t i = 0; i < m->n_o; ++i)
        free(m->o[i].key);      /* free(NULL) an toàn, không cần kiểm */

    free(m->o);
    free(m);
}