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

Hash Table

Hash function ánh xạ key tới bucket; collision cần chaining hoặc open addressing.

Hash Table là gì?

Hash function ánh xạ key tới bucket; collision cần chaining hoặc open addressing.

Đếm từ bằng separate chaining và unordered_map.

Điểm quan trọng

Xác định invariant trước khi cài đặt operation.
Xử lý trường hợp rỗng, đầy và cấp phát thất bại.
Đánh giá đồng thời complexity và ownership.

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);
}

Output dự kiến

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';
}

Output dự kiến

c=2 cpp=1

So sánh C và C++

Ví dụ C dùng key cố định để tập trung vào bucket; std::unordered_map sở hữu node, tự grow và nhận string key tùy ý.

Struct và operation thường tách rời, cấp phát được quản lý thủ công.

C++

Class và container có thể bảo vệ invariant và tự quản lý tài nguyên.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Thêm test cho trạng thái rỗng và capacity boundary.
Cài đặt cleanup rồi kiểm tra memory leak.
So sánh complexity với standard container.