Bài 25.328 phút đọc
Chaining
Sau bài này bạn sẽ làm được
- Cài bảng băm chaining đủ bốn thao tác
- Quản lý sở hữu chuỗi khóa bằng cấp phát và giải phóng rõ ràng
- Dùng lại mẹo con trỏ tới con trỏ khi xóa
- Hủy bảng băm không rò rỉ
Chaining là cách cài bảng băm dễ nhất: mỗi ô là đầu một danh sách liên kết, và va chạm thì thêm vào danh sách đó. Cái khó duy nhất không phải thuật toán mà là quản lý sở hữu chuỗi khóa.
#Cấu trúc
hashmap.h
#ifndef HASHMAP_H
#define HASHMAP_H
#include <stddef.h>
typedef struct Entry {
char *key; /* SỞ HỮU: bảng cấp phát và giải phóng */
int value;
struct Entry *next;
} Entry;
/* Bất biến:
1. buckets khác NULL và có đúng n_buckets phần tử
2. size == tổng số Entry trong mọi danh sách
3. Mọi Entry trong buckets[i] đều có hash(key) % n_buckets == i
4. Không có hai Entry nào cùng key */
typedef struct {
Entry **buckets;
size_t n_buckets;
size_t size;
} HashMap;
HashMap *hm_tao(size_t n_buckets);
void hm_huy(HashMap *m);
int hm_put(HashMap *m, const char *key, int value);
int hm_get(const HashMap *m, const char *key, int *ra);
int hm_remove(HashMap *m, const char *key);
size_t hm_so_phan_tu(const HashMap *m);
void hm_duyet(const HashMap *m,
void (*ham)(const char *, int, void *), void *ctx);
#endifhashmap.c
#include <stdlib.h>
#include <string.h>
#include "hashmap.h"
static unsigned long bam(const char *s)
{
unsigned long h = 5381;
for (; *s != '\0'; ++s)
h = h * 33 + (unsigned char)*s;
return h;
}
HashMap *hm_tao(size_t n_buckets)
{
if (n_buckets == 0) return NULL;
HashMap *m = malloc(sizeof *m);
if (m == NULL) return NULL;
m->buckets = calloc(n_buckets, sizeof *m->buckets); /* mọi ô là NULL */
if (m->buckets == NULL) { free(m); return NULL; }
m->n_buckets = n_buckets;
m->size = 0;
return m;
}
size_t hm_so_phan_tu(const HashMap *m) { return m ? m->size : 0; }#put: thêm hoặc cập nhật
hashmap.c (tiếp)
/* Đặt key thành value. Nếu key đã có thì cập nhật giá trị.
Trả về 0 nếu thêm mới
1 nếu cập nhật khóa đã có
-1 nếu hết bộ nhớ, bảng không đổi */
int hm_put(HashMap *m, const char *key, int value)
{
if (m == NULL || key == NULL) return -1;
size_t i = bam(key) % m->n_buckets;
/* Bước 1: tìm trong danh sách của ô đó */
for (Entry *e = m->buckets[i]; e != NULL; e = e->next)
if (strcmp(e->key, key) == 0) {
e->value = value;
return 1;
}
/* Bước 2: không có, tạo mục mới */
Entry *e = malloc(sizeof *e);
if (e == NULL) return -1;
size_t n = strlen(key) + 1;
e->key = malloc(n);
if (e->key == NULL) { free(e); return -1; } /* dọn phần đã cấp */
memcpy(e->key, key, n);
e->value = value;
/* Bước 3: thêm vào ĐẦU danh sách, O(1) */
e->next = m->buckets[i];
m->buckets[i] = e;
++m->size;
return 0;
}#get và remove
hashmap.c (tiếp)
/* Lấy giá trị của key. Trả về 0 nếu có, -1 nếu không. */
int hm_get(const HashMap *m, const char *key, int *ra)
{
if (m == NULL || key == NULL) return -1;
size_t i = bam(key) % m->n_buckets;
for (Entry *e = m->buckets[i]; e != NULL; e = e->next)
if (strcmp(e->key, key) == 0) {
if (ra != NULL) *ra = e->value;
return 0;
}
return -1;
}
/* Xóa key. Trả về 0 nếu xóa được, -1 nếu không có.
Dùng mẹo con trỏ tới con trỏ ở Bài 21.4. */
int hm_remove(HashMap *m, const char *key)
{
if (m == NULL || key == NULL) return -1;
size_t i = bam(key) % m->n_buckets;
Entry **pp = &m->buckets[i];
while (*pp != NULL) {
Entry *e = *pp;
if (strcmp(e->key, key) == 0) {
*pp = e->next; /* gỡ khỏi danh sách, không cần biết nút trước */
free(e->key);
free(e);
--m->size;
return 0;
}
pp = &e->next;
}
return -1;
}hashmap.c (tiếp)
void hm_huy(HashMap *m)
{
if (m == NULL) return;
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 free */
free(e->key);
free(e);
e = ke;
}
}
free(m->buckets);
free(m);
}#Ai sở hữu chuỗi khóa
Đây là quyết định thiết kế quan trọng nhất của cả bài, và nó ảnh hưởng tới toàn bộ giao diện.
| Cách | hm_put làm gì với key | Người gọi phải làm gì |
|---|---|---|
| Bảng sở hữu, tự chép | Cấp bộ nhớ mới và chép chuỗi vào | Không phải làm gì, key của họ vẫn thuộc về họ |
| Bảng sở hữu, nhận chuyển giao | Giữ nguyên con trỏ được truyền vào | Không được free key nữa, và không được dùng lại nó |
| Bảng không sở hữu | Chỉ lưu con trỏ | Phải giữ key sống lâu hơn bảng, và tự free |
#Duyệt toàn bộ bảng
hashmap.c (tiếp)
/* Gọi ham cho mọi cặp khóa giá trị. Thứ tự KHÔNG xác định.
ctx được truyền nguyên vẹn, đúng mẫu ở Bài 21.5. */
void hm_duyet(const HashMap *m,
void (*ham)(const char *key, int value, void *ctx),
void *ctx)
{
if (m == NULL || ham == NULL) return;
for (size_t i = 0; i < m->n_buckets; ++i)
for (Entry *e = m->buckets[i]; e != NULL; e = e->next)
ham(e->key, e->value, ctx);
}#Ứng dụng: đếm tần suất từ
dem-tu.c
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashmap.h"
typedef struct { char *key; int dem; } Muc;
typedef struct { Muc *d; size_t n, cap; } DanhSach;
static void gom(const char *key, int value, void *ctx)
{
DanhSach *ds = ctx;
if (ds->n == ds->cap) {
size_t moi = ds->cap ? ds->cap * 2 : 64;
Muc *t = realloc(ds->d, moi * sizeof *t);
if (t == NULL) return; /* bỏ qua, bản thật nên báo lỗi */
ds->d = t; ds->cap = moi;
}
ds->d[ds->n].key = (char *)key; /* chỉ mượn, bảng vẫn sở hữu */
ds->d[ds->n].dem = value;
++ds->n;
}
static int giam_dan(const void *a, const void *b)
{
const Muc *x = a, *y = b;
if (x->dem != y->dem) return y->dem - x->dem; /* đếm giảm dần */
return strcmp(x->key, y->key); /* rồi theo tên */
}
int main(int argc, char **argv)
{
if (argc < 2) { fprintf(stderr, "dung: %s tep\n", argv[0]); return 1; }
FILE *f = fopen(argv[1], "r");
if (f == NULL) { perror(argv[1]); return 1; }
HashMap *m = hm_tao(1024);
if (m == NULL) { fclose(f); return 1; }
char tu[128];
int k = 0, c;
while ((c = fgetc(f)) != EOF) {
if (isalpha((unsigned char)c)) {
if (k + 1 < (int)sizeof tu)
tu[k++] = (char)tolower((unsigned char)c);
} else if (k > 0) {
tu[k] = '\0';
int cu = 0;
hm_get(m, tu, &cu);
if (hm_put(m, tu, cu + 1) < 0) { hm_huy(m); fclose(f); return 1; }
k = 0;
}
}
if (k > 0) { /* từ cuối tệp, không có dấu ngắt */
tu[k] = '\0';
int cu = 0;
hm_get(m, tu, &cu);
hm_put(m, tu, cu + 1);
}
fclose(f);
printf("so tu khac nhau: %zu\n\n", hm_so_phan_tu(m));
DanhSach ds = { NULL, 0, 0 };
hm_duyet(m, gom, &ds);
qsort(ds.d, ds.n, sizeof *ds.d, giam_dan);
printf("top 10:\n");
for (size_t i = 0; i < ds.n && i < 10; ++i)
printf("%6d %s\n", ds.d[i].dem, ds.d[i].key);
free(ds.d);
hm_huy(m);
return 0;
}terminal
gcc -std=c17 -Wall -Wextra -g hashmap.c dem-tu.c -o dem-tu && ./dem-tu truyen-kieu.txt
so tu khac nhau: 3238 top 10: 1424 mot 1129 khong 987 co 841 nguoi 736 la 698 cho 612 nhu 579 ma 544 con 531 duong
# Valgrind chạy trên bản không bật sanitizer
valgrind --leak-check=full ./dem-tu truyen-kieu.txt
All heap blocks were freed -- no leaks are possible ERROR SUMMARY: 0 errors from 0 contexts
Tự làm thử
- Cài
HashMapđầy đủ với bốn thao tác, chạy dưới valgrind cho tới khi không còn rò rỉ. - Bỏ bước tìm trong
hm_put, rồiputcùng khóa hai lần và xemsizecùnghm_removehành xử thế nào. - Cài bản không sở hữu chuỗi khóa, rồi tái hiện lỗi ba khóa cùng trỏ vào một bộ đệm.
- Cài
hm_lay_hoac_taovà đo thời gian đếm từ so với cách gọihm_getrồihm_put. - Cài
hm_duyetrồi đổi số ô từ 8 thành 16 và xác nhận thứ tự duyệt thay đổi hoàn toàn.
Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.
Tóm tắt
- Chaining cho mỗi ô một danh sách liên kết, nên va chạm chỉ làm danh sách dài thêm chứ không phá cấu trúc.
- Hàm
putphải tìm trước để cập nhật khóa đã có, nếu không bảng sẽ chứa hai mục cùng khóa. - Mẹo
Entry **ppáp dụng hoàn hảo chohm_remove, vì bảng băm không có con trỏ đuôi phải giữ đồng bộ. - Bảng nên tự chép chuỗi khóa. Hai cách sở hữu kia đều bắt người gọi nhớ quy tắc, và quy tắc phải nhớ là quy tắc sẽ bị quên.
- Thứ tự duyệt hoàn toàn không xác định. Đừng bao giờ viết phép thử hay đầu ra phụ thuộc vào nó.