Hàm băm

/* Cộng mã của mọi ký tự. Ai cũng nghĩ ra cách này đầu tiên. */
unsigned long hash_tong(const char *s)
{
    unsigned long h = 0;

    for (; *s != '\0'; ++s)
        h += (unsigned char)*s;

    return h;
}

unsigned long hash_djb2(const char *s)
{
    unsigned long h = 5381;

    for (; *s != '\0'; ++s)
        h = h * 33 + (unsigned char)*s;      /* h = ((h << 5) + h) + c */

    return h;
}

/* Biến thể djb2a dùng phép hoặc loại trừ thay vì cộng.
   Trộn bit tốt hơn một chút với chuỗi ngắn. */
unsigned long hash_djb2a(const char *s)
{
    unsigned long h = 5381;

    for (; *s != '\0'; ++s)
        h = h * 33 ^ (unsigned char)*s;

    return h;
}

#include <stdint.h>

/* FNV-1a 32 bit. Do Fowler, Noll và Vo thiết kế.
   Đặc điểm: phép hoặc loại trừ TRƯỚC, phép nhân SAU. */
uint32_t hash_fnv1a(const char *s)
{
    uint32_t h = 2166136261u;            /* offset basis */

    for (; *s != '\0'; ++s) {
        h ^= (unsigned char)*s;
        h *= 16777619u;                  /* FNV prime = 2^24 + 2^8 + 0x93 */
    }

    return h;
}

/* Bản 64 bit, dùng khi cần miền giá trị rộng hơn. */
uint64_t hash_fnv1a_64(const void *du_lieu, size_t n)
{
    const unsigned char *p = du_lieu;
    uint64_t             h = 14695981039346656037u;

    for (size_t i = 0; i < n; ++i) {
        h ^= p[i];
        h *= 1099511628211u;
    }

    return h;
}

/* 33 mod 32 = 1

   Nên với mọi h:  (h * 33) mod 32 = (h * 1) mod 32 = h mod 32

   Suy ra:  h_moi mod 32 = (h_cu * 33 + c) mod 32 = (h_cu + c) mod 32

   Nghĩa là 5 bit THẤP của djb2 chính là 5 bit thấp của
   (5381 + tổng mã các ký tự), tức đúng bằng hàm băm ngây thơ! */

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

typedef unsigned long (*HamBam)(const char *);

typedef struct { const char *ten; HamBam f; } Muc;

static void do_mot_ham(const Muc *m, char **tu, size_t n_tu, size_t n_o)
{
    size_t *dem = calloc(n_o, sizeof *dem);

    if (dem == NULL) return;

    for (size_t i = 0; i < n_tu; ++i)
        ++dem[m->f(tu[i]) % n_o];

    size_t trong = 0, dong_nhat = 0;
    double tu_so = 0.0;

    for (size_t i = 0; i < n_o; ++i) {
        if (dem[i] == 0) ++trong;
        if (dem[i] > dong_nhat) dong_nhat = dem[i];

        tu_so += (double)dem[i] * ((double)dem[i] + 1.0) / 2.0;
    }

    /* Hệ số chất lượng của Bob Jenkins: bằng 1.0 khi phân bố giống hệt
       ngẫu nhiên đều, lớn hơn 1 khi bị gom cụm. */
    double n   = (double)n_tu;
    double m_o = (double)n_o;
    double mau = n / (2.0 * m_o) * (n + 2.0 * m_o - 1.0);
    double chat_luong = tu_so / mau;

    printf("%-10s: %5zu o trong (%4.1f%%), o dong nhat %3zu khoa, chat luong %.3f\n",
           m->ten, trong, 100.0 * trong / m_o, dong_nhat, chat_luong);
}

int main(int argc, char **argv)
{
    if (argc < 3) { fprintf(stderr, "dung: %s tep so_o\n", argv[0]); return 1; }

    size_t n_o = (size_t)strtoul(argv[2], NULL, 10);

    /* Đọc từ điển, mỗi dòng một từ. Bỏ qua phần đọc tệp cho gọn. */
    size_t n_tu;
    char **tu = doc_tu_dien(argv[1], &n_tu);

    if (tu == NULL) return 1;

    printf("%zu tu, %zu o\n\n", n_tu, n_o);

    Muc bang[] = {
        { "tong",   hash_tong  },
        { "djb2",   hash_djb2  },
        { "djb2a",  hash_djb2a },
        { "fnv1a",  hash_fnv1a_ul },
    };

    for (size_t i = 0; i < sizeof bang / sizeof bang[0]; ++i)
        do_mot_ham(&bang[i], tu, n_tu, n_o);

    giai_phong_tu_dien(tu, n_tu);

    return 0;
}