Va chạm

/* Chuồng bồ câu: n con chim, m chuồng, n > m
   thì có ít nhất một chuồng chứa từ hai con trở lên.

   Dạng mạnh: có ít nhất một chuồng chứa ít nhất trần(n/m) con.

   Với 10000 khóa và 4096 ô: trần(10000/4096) = 3.
   Vậy chắc chắn có ô chứa ít nhất 3 khóa, dù hàm băm hoàn hảo tới đâu. */

#include <stdio.h>

/* Xác suất KHÔNG có cặp nào trùng, với n khóa và m ô. */
static double p_khong_trung(long n, long m)
{
    double p = 1.0;

    for (long i = 0; i < n; ++i)
        p *= (double)(m - i) / (double)m;

    return p;
}

int main(void)
{
    printf("%8s %10s %14s\n", "so khoa", "so o", "P(co va cham)");

    struct { long n, m; } thu[] = {
        { 23,    365     },
        { 50,    365     },
        { 10,    1000    },
        { 100,   1000    },
        { 1000,  1000000 },
        { 77163, 1000000 },
    };

    for (size_t i = 0; i < sizeof thu / sizeof thu[0]; ++i)
        printf("%8ld %10ld %14.4f\n",
               thu[i].n, thu[i].m,
               1.0 - p_khong_trung(thu[i].n, thu[i].m));

    return 0;
}

#include <math.h>
#include <stdio.h>

int main(void)
{
    printf("%8s %8s %10s %12s %14s\n",
           "n khoa", "m o", "he so tai", "o trong (%)", "chuoi TB");

    struct { long n, m; } thu[] = {
        { 1000,   1024   },
        { 10000,  16384  },
        { 100000, 131072 },
        { 1000,   100    },
        { 1000,   10000  },
    };

    for (size_t i = 0; i < sizeof thu / sizeof thu[0]; ++i) {
        double n = (double)thu[i].n;
        double m = (double)thu[i].m;

        /* Số ô trống kỳ vọng: m * (1 - 1/m)^n, xấp xỉ m * e^(-n/m) */
        double trong  = m * pow(1.0 - 1.0 / m, n);
        double khac_0 = m - trong;

        printf("%8ld %8ld %10.2f %12.1f %14.2f\n",
               thu[i].n, thu[i].m, n / m, 100.0 * trong / m, n / khac_0);
    }

    return 0;
}

/* Mỗi ô là đầu một danh sách liên kết.
   Va chạm thì thêm vào danh sách đó.

   o 0 -> NULL
   o 1 -> "an" -> "ba" -> NULL
   o 2 -> NULL
   o 3 -> "cuc" -> NULL
   o 4 -> "do" -> "em" -> "ga" -> NULL                */

/* Ô bị chiếm thì dò sang ô kế tiếp theo một quy tắc.

   o 0: trong
   o 1: "an"        <- hash("an") = 1
   o 2: "ba"        <- hash("ba") = 1, bi chiem, do sang 2
   o 3: "cuc"
   o 4: trong                                        */