前言
在阅读《C Interfaces and Implementations》的第三章时，我了解了原子表这一概念，因此写一篇博客记录一下。
原子
要了解原子表，首先要明白原子是什么。这里的“原子”和“原子操作”中的原子没有关系。
原子是一个指针，它指向由零个或多个任意字节组成的唯一且不可改变的字节序列。在同一个原子表中，一个字节序列只对应一个原子。
原子有几个特征：
- 原子本身是一个指针。
- 原子指向的字节序列不可改变。
- 在同一个原子表中，一个字节序列只对应一个原子。
这使得原子具有几个特点：
- 重复获取同一个字节序列对应的原子，得到的是同一个指针。
- 比较两个原子是否相等，就能知道它们对应的字节序列是否相等。
- 相同且不可改变的字节序列只需要保存一份。
值得注意的是，原子指向的字节序列不能修改，这是原子接口作出的约定，并不是 C 语言能够从语法层面完全强制保证的。毕竟指针操作是万能的（笑），const 也只能限制用户通过当前指针修改，真要强制转换，它也无能为力啊。
因此，实际使用时，原子保存的大多是不需要修改的字符串。尤其是字符串字面量，它由编译器生成，程序不能安全地修改，用户一般也不会去修改它。
比如有一个根据字节序列创建并返回原子的函数 Atom_New：
extern const uint8_t *Atom_New(const uint8_t *buffer, int len);
const char *a = (char*)Atom_New((uint8_t*)"hello", strlen("hello"));
const char *b = (char*)Atom_New((uint8_t*)"hello", strlen("hello"));
对于同一个字节序列 "hello"，Atom_New 返回的原子 a 和 b 相同，也就是 a == b。它们都指向原子表保存的同一份 "hello" 字节序列。
为什么 Atom_New 能根据字节序列创建并返回原子？重复输入 "hello" 时，为什么返回的原子相同？这就用到了原子表。
原子表
在同一个原子表中，每个字节序列只保存一份。无论重复输入多少次，原子表都会返回指向这份字节序列的同一个指针，也就是同一个原子。
原子表本质上完成的是：
输入字节序列
↓
是否已经存在相同的字节序列？
├─ 是 → 返回已有原子
└─ 否 → 申请或预留空间，复制字节序列并返回新的原子
基于这个需求，原子表通常使用散列表实现。
如果使用线性表在 n 个原子中查找一个字节序列，平均时间复杂度是 O(n)。在哈希分布较好、散列表大小合适的情况下，平均查找时间复杂度可以达到 O(1)。
不过，计算哈希值时仍然需要遍历输入的字节序列。
通常的实现是先计算输入字节序列的哈希值，找到可能存放原子的位置，再比较字节序列是否相同。
如果已经存在相同的字节序列，就直接返回对应的原子；如果不存在，就申请或预留空间，复制输入的字节序列，再返回指向这份字节序列的指针，也就是新的原子。
结语
这个数据结构我之前了解得不多。我感觉它是一种节省内存的数据结构，不过它要求字节序列不可改变，我认为大部分程序都用不上。
参考资料
- 《C Interfaces and Implementations》第三章