Cấu trúc dữ liệu trong C/C++

Bảng băm (hash table) trong C, C++

Trong bài học này, bạn sẽ đếm số lần xuất hiện của từng từ bằng bảng băm tự cài đặt trong C và std::unordered_map trong C++.

Giới thiệu

Bảng băm (hash table) dùng một hàm băm (hash function) để chuyển mỗi khóa thành chỉ số của một ô lưu trữ (bucket), nhờ đó việc tìm kiếm, thêm và xóa diễn ra rất nhanh. Khi hai khóa khác nhau rơi vào cùng một ô, gọi là đụng độ (collision), bảng băm cần một cách xử lý như nối chuỗi (chaining) hoặc địa chỉ mở (open addressing).

Những điểm quan trọng

Xác định những điều kiện luôn phải đúng (invariant) của cấu trúc dữ liệu trước khi viết các thao tác.
Xử lý đầy đủ các trường hợp rỗng, đầy và cấp phát bộ nhớ thất bại.
Đánh giá cả độ phức tạp lẫn cách quản lý vùng nhớ của từng thao tác.

Xem cách hoạt động

Nhập một khóa rồi lưu hoặc tra cứu. Khóa được băm thành số bucket, nên chương trình nhảy thẳng tới đúng bucket.

Code ví dụ bằng C và C++

Chạy code →

main.c

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

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

Kết quả khi chạy

c=2 cpp=1

C++

Chạy code →

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

Kết quả khi chạy

c=2 cpp=1

So sánh C và C++

Hàm hash trong C tính một giá trị từ các ký tự của chuỗi rồi lấy dư cho 5 để chọn một trong 5 bucket. Mỗi bucket là một danh sách liên kết, nên các từ bị đụng độ được nối tiếp nhau trong cùng bucket. Ví dụ C chỉ dùng vài từ cố định để tập trung vào cơ chế bucket. Trong C++, std::unordered_map tự quản lý các nút, tự mở rộng khi cần và nhận khóa là chuỗi bất kỳ.

Dữ liệu (struct) và các thao tác thường tách rời, bộ nhớ được cấp phát và giải phóng thủ công.

C++

Class và container có thể tự bảo vệ tính đúng đắn của dữ liệu và tự quản lý tài nguyên.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

Thêm kiểm thử cho trạng thái rỗng và khi đạt giới hạn dung lượng.
Viết phần giải phóng bộ nhớ và kiểm tra rò rỉ bộ nhớ.
So sánh độ phức tạp với container tương ứng của thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách