Hệ số tải và rehash

/* Chaining */
he_so_tai = size / n_buckets

/* Open addressing */
he_so_tai = (size + so_bia_mo) / n_o

/* Đổi số ô thành n_moi và tính lại vị trí cho mọi mục.
   Trả về 0 nếu ổn, -1 nếu hết bộ nhớ và bảng KHÔNG đổi. */
static int hm_rehash(HashMap *m, size_t n_moi)
{
    if (n_moi == 0) return -1;

    Entry **b_moi = calloc(n_moi, sizeof *b_moi);

    if (b_moi == NULL) return -1;      /* thất bại, bảng cũ còn nguyên */

    /* Chuyển từng mục sang mảng mới. KHÔNG cấp phát lại mục nào,
       chỉ nối lại con trỏ, nên hàm này không thể thất bại giữa chừng. */
    for (size_t i = 0; i < m->n_buckets; ++i) {
        Entry *e = m->buckets[i];

        while (e != NULL) {
            Entry *ke = e->next;                 /* lưu TRƯỚC khi đổi next */
            size_t j  = bam(e->key) % n_moi;     /* TÍNH LẠI vị trí */

            e->next   = b_moi[j];                /* thêm vào đầu ô mới */
            b_moi[j]  = e;
            e         = ke;
        }
    }

    free(m->buckets);
    m->buckets   = b_moi;
    m->n_buckets = n_moi;

    return 0;
}

/* Gọi ở đầu hm_put, trước khi thêm phần tử mới. */
int hm_put(HashMap *m, const char *key, int value)
{
    if (m == NULL || key == NULL) return -1;

    if ((m->size + 1) * 4 > m->n_buckets * 3)      /* tải sẽ vượt 0,75 */
        if (hm_rehash(m, m->n_buckets * 2) != 0)
            return -1;

    /* phần còn lại như Bài 25.3 */
    ...
}

/* Với open addressing thì rehash phải CHÈN LẠI từng khóa,
   vì vị trí phụ thuộc cả vào những khóa khác đã có trong mảng mới. */
static int oa_rehash(OAMap *m, size_t n_moi)
{
    if (n_moi < 8 || (n_moi & (n_moi - 1)) != 0) return -1;

    O *o_moi = calloc(n_moi, sizeof *o_moi);

    if (o_moi == NULL) return -1;

    /* Chèn lại vào mảng mới. Không cấp phát chuỗi nào, chỉ chuyển con trỏ. */
    for (size_t i = 0; i < m->n_o; ++i) {
        if (m->o[i].trang_thai != O_DANG_DUNG) continue;      /* bỏ bia mộ */

        size_t h = (size_t)bam(m->o[i].key) & (n_moi - 1);

        for (size_t k = 0; k < n_moi; ++k) {
            size_t j = (h + k) & (n_moi - 1);

            if (o_moi[j].trang_thai == O_TRONG) {
                o_moi[j] = m->o[i];      /* chuyển cả struct, kể cả con trỏ key */

                break;
            }
        }
    }

    free(m->o);
    m->o         = o_moi;
    m->n_o       = n_moi;
    m->so_bia_mo = 0;      /* rehash quét sạch mọi bia mộ */

    return 0;
}

/* Bắt đầu với 8 ô, nhân đôi mỗi lần vượt ngưỡng.
   Rehash xảy ra ở các mốc kích thước 8, 16, 32, ..., n.

   Tổng chi phí của mọi lần rehash khi chèn n phần tử:

     8 + 16 + 32 + ... + n  <  2n

   Chia đều cho n lần put: mỗi lần gánh dưới 2 thao tác phụ.
   Đó là hằng số, nên put có chi phí KHẤU HAO O(1).

   So sánh với cách tăng thêm một lượng cố định, ví dụ mỗi lần thêm 100 ô:

     100 + 200 + 300 + ... + n  =  n(n+100)/200  =  O(n binh phuong)

   Chia cho n lần put: mỗi lần gánh O(n). Chèn n phần tử thành O(n binh phuong). */

/* Mỗi số xấp xỉ gấp đôi số trước, và đều là số nguyên tố. */
static const size_t NGUYEN_TO[] = {
    17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949,
    21911, 43853, 87719, 175447, 350899, 701819, 1403641,
    2807303, 5614657, 11229331, 22458671, 44917381
};

static size_t nguyen_to_ke(size_t n)
{
    for (size_t i = 0; i < sizeof NGUYEN_TO / sizeof NGUYEN_TO[0]; ++i)
        if (NGUYEN_TO[i] > n) return NGUYEN_TO[i];

    return n * 2 + 1;      /* vượt bảng, chấp nhận không phải số nguyên tố */
}

/* Giữ HAI mảng cùng lúc trong lúc chuyển. */
typedef struct {
    Entry **cu;
    Entry **moi;
    size_t  n_cu, n_moi;
    size_t  vi_tri;        /* ô tiếp theo cần chuyển từ cu sang moi */
    size_t  size;
    int     dang_chuyen;   /* khác 0 khi đang trong quá trình rehash */
} HashMapDan;

/* Chuyển một số ô mỗi lần được gọi. Gọi từ put, get và remove. */
static void chuyen_mot_it(HashMapDan *m, size_t so_o)
{
    if (!m->dang_chuyen) return;

    for (size_t k = 0; k < so_o && m->vi_tri < m->n_cu; ++k, ++m->vi_tri) {
        Entry *e = m->cu[m->vi_tri];

        while (e != NULL) {
            Entry *ke = e->next;
            size_t j  = e->h % m->n_moi;

            e->next     = m->moi[j];
            m->moi[j]   = e;
            e           = ke;
        }

        m->cu[m->vi_tri] = NULL;
    }

    if (m->vi_tri >= m->n_cu) {      /* xong */
        free(m->cu);
        m->cu          = NULL;
        m->dang_chuyen = 0;
    }
}

/* Trong lúc chuyển, phép tìm phải nhìn CẢ HAI mảng. */
int hmd_get(HashMapDan *m, const char *key, int *ra)
{
    unsigned long h = bam(key);

    if (m->dang_chuyen) {
        size_t i = h % m->n_cu;

        if (i >= m->vi_tri)                    /* ô này chưa được chuyển */
            for (Entry *e = m->cu[i]; e; e = e->next)
                if (e->h == h && strcmp(e->key, key) == 0) {
                    if (ra) *ra = e->value;

                    return 0;
                }
    }

    size_t j = h % m->n_moi;

    for (Entry *e = m->moi[j]; e; e = e->next)
        if (e->h == h && strcmp(e->key, key) == 0) {
            if (ra) *ra = e->value;

            return 0;
        }

    return -1;
}