您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

C 語言實現 Atom 原子表：字串去重與高效比較的經典設計

編輯：C++ 入門

什麼是 Atom（原子）？

Atom 是指向唯一、不可變位元組序列的指標。核心特性：

唯一性：相同內容的序列在表中僅存一份
指標比較即相等判斷：atom1 == atom2 等價於內容相等，O(1)
節省空間：重複字串僅存一份
不可變：建立後不可修改

應用場景：編譯器符號表、解析器關鍵字、網路協議標籤、任何大量重複字串場景。

介面設計

// atom.h
#ifndef ATOM_INCLUDED
#define ATOM_INCLUDED

extern int Atom_length(const char *str);           // 取得原子長度
extern const char *Atom_new(const char *str, int len); // 由位元組序列建立/查找原子
extern const char *Atom_string(const char *str);   // 由 C 字串建立/查找原子
extern const char *Atom_int(long n);               // 整數轉原子

#endif

核心實現：雜湊表 + 分離鏈接

資料結構

// atom.c
#define NELEMS(x) (sizeof(x)/sizeof((x)[0]))

static struct atom {
    struct atom *link;   // 同雜湊桶下一個
    int len;             // 序列長度
    char *str;           // 指向柔性陣列成員
} *buckets[2048];        // 2048 桶，2 的冪次利於位元組取模

結構記憶體佈局：

struct atom { link | len | str[0]...str[len]\\0 }
// 分配時：ALLOC(sizeof(struct atom) + len + 1)
// str 指向結構體末尾的柔性陣列，單次分配提升快取局部性

雜湊函數

static unsigned long scatter[256] = { 
    2078917053, 143302914, ... // 256 隨機數，由 rand() 生成
};

unsigned long h = 0;
for (int i = 0; i < len; ++i)
    h = (h << 1) + scatter[(unsigned char)str[i]];
h &= NELEMS(buckets) - 1;  // 等價 h % 2048，但更快

使用查表法 + 位移混合，避免模除運算，分布均勻。

Atom_new 核心邏輯

const char *Atom_new(const char *str, int len) {
    assert(str && len >= 0);
    
    // 1. 計算雜湊值
    unsigned long h = 0;
    for (int i = 0; i < len; ++i)
        h = (h << 1) + scatter[(unsigned char)str[i]];
    h &= NELEMS(buckets) - 1;

    // 2. 搜尋桶內鏈表
    for (struct atom *p = buckets[h]; p; p = p->link) {
        if (len == p->len) {
            int i = 0;
            while (i < len && p->str[i] == str[i]) ++i;
            if (i == len) return p->str;  // 找到，直接返回
        }
    }

    // 3. 未找到，建立新原子
    struct atom *p = ALLOC(sizeof(*p) + len + 1);
    p->len = len;
    p->str = (char*)(p + 1);  // 指向柔性陣列起始
    if (len > 0) memcpy(p->str, str, len);
    p->str[len] = '\\0';
    p->link = buckets[h];
    buckets[h] = p;
    return p->str;
}

輔助函數

const char *Atom_string(const char *str) {
    assert(str);
    return Atom_new(str, strlen(str));
}

const char *Atom_int(long n) {
    char buf[43];  // 足夠存 64 位整數 + 符號
    char *s = buf + sizeof(buf);
    unsigned long m = (n == LONG_MIN) ? (unsigned long)LONG_MAX + 1 
                 : (n < 0) ? -n : n;
    do *--s = m % 10 + '0'; while ((m /= 10) > 0);
    if (n < 0) *--s = '-';
    return Atom_new(s, (buf + sizeof(buf)) - s);
}

int Atom_length(const char *str) {
    // 遍歷所有桶查找指標匹配
    for (int i = 0; i < NELEMS(buckets); ++i)
        for (struct atom *p = buckets[i]; p; p = p->link)
            if (p->str == str) return p->len;
    assert(0); return 0;  // 不應發生
}

設計亮點解析

柔性陣列成員：char *str 指向結構體後的記憶體，單次 ALLOC 完成結構+字串分配，減少碎片、提升快取命中
雜湊表大小為 2 的冪次：位元組 & (N-1) 替代昂貴模除
查表式雜湊：scatter[] 預計算 256 隨機數，避免運行時乘法
指標比較語意：呼叫端僅需 if (a == b) 判斷字串相等，極簡高效
整數轉字串無符號算術：規避 LONG_MIN 絕對值溢位與有號除法未定義行為

使用範例

#include "atom.h"
#include <stdio.h>

int main() {
    const char *a = Atom_string("hello");
    const char *b = Atom_string("hello");
    const char *c = Atom_string("world");
    
    printf("a == b: %d\\n", a == b);  // 1 (同一指標)
    printf("a == c: %d\\n", a == c);  // 0
    printf("len: %d\\n", Atom_length(a)); // 5
    
    const char *num = Atom_int(-12345);
    printf("int atom: %s\\n", num);
}