对比本书后面的内容来看，这章算比较轻松的，涉及到的函数也很少。
书里所谓的「原子」并没有「微小」、「原子操作」等意味，而是出于另一个目的 —— 作为字节序列的副本，这是典型的「替换思维」，用简单代替复杂。如同 MD5 能代表完整文件信息一样，原子能代表一串唯一的字节序列。
第三章 —— 原子
原子（atom）是一个指针，指向一个唯一的、不可变的序列，序列中包含零或多个字节（字节值）任意。大多数原子都指向 0 结尾字符串，但也可以是指向任一字节序列的指针。任一原子都只会出现一次，这也是它被称为原子的原因。如果两个原子指向相同的位置，那么两者是相同的。原子的一个优点是，只通过比较两个指针，即可比较两个字节序列是否相等。使用原子的另一个优点是节省空间，因为任一序列都只会出现一次。
由此可见这里指的原子本质是指针（实现细节），同时也代表所指向的字节序列。显然，书中的「原子」一词更多地表示「字节序列」（就像我们提到某人的名字时想说的是某个人，而不仅是几个汉字）。更具体的，原子是一个唯一的字节序列，这意味着不可能同时存在两个相同的原子，并且原子不修改，一旦创建便固定了。
这段话还揭示了原子的一般存在形式 —— 以 0 结尾的字符串（当然并不绝对，只是大多数情况），书中也采用了这种表示方式。值得注意的是，文中的「字符串」在于强调「以 0 结尾的字节序列」，并不是说原子只能是 ASCII 码表那可怜的 128 字符的组合，实际上原子中单个字节可以取 0 - 255 的任意值，所以才被称为「字节序列」而非「字符序列」。
从原子的两个优点（1、比较指针代替比较字节序列，2、节省空间）大概能猜到它的用途 —— 对大量字节序列频繁操作（比较）的情况。比如数据结构中的表和集合通常采用原子作为索引的「键」。
原子相关接口
Atom 接口很简单：
<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);
extern const char *Atom_int (long n);
#endif
其中 Atom_length 函数用于查询已存在的原子长度，而剩下的三个函数用于创建原子，Atom_new 的参数包括一个指向字节序列的指针，以及该序列中的字节数目。Atom_string 接收字符串用于创建原子，Atom_int 创建用字符串表示长整数 n 的原子。巧妇难为无米之炊，同理，创建原子必须先有一些「原料」，已知长度的字节序列、字符串或一个整数都可以作为「原料」。
在 C 语言里无法从指针形参中得到所指向内存的大小（即使是数组，传过来也会丢失大小信息），所以要么给出长度，要么使用结束标志（字符串），从这个角度不难理解 Atom_new 和 Atom_string 函数的设计。
实现
Atom 接口就像一个黑盒，你把创建原子所需的字节序列传进去，便会得到一个原子 —— const char * 类型的指针。那究竟盒子内部是如何运作的呢？把盒子打开看个究竟，或许这才是更有意思的事情。
创建原子操作
Atom_string和Atom_int可以在不了解原子表表示细节的情况下实现。例如，Atom_string只是调用了Atom_new：
<functions 25> ≡
const char *Atom_string(const char *str) {
assert(str);
return Atom_new(str, strlen(str));
}
Atom_int首先将其参数转换为一个字符串，然后调用Atom_new：
<functions 25> +≡
const char *Atom_int(long n) {
char str[43];
char *s = str + sizeof str;
unsigned long m;
if (n == LONG_MIN)
m = LONG_MAX + 1UL;
else if (n < 0)
m = -n;
else
m = n;
do
*--s = m%10 + '0';
while ((m /= 10) > 0);
if (n < 0)
*--s = '-';
return Atom_new(s, (str + sizeof str) - s);
}
Atom_int 中几乎所有代码都在完成「整数转字符串」这一操作，用对 10 取整和取余这种「骚操作」将一个数由低位到高位的一位一位取出，加上 0 字符转换后再从数组末尾往前写入。为了避免上一章所提到的「除法二义性」，首先把 long 转为 unsigned long 正数统一处理。特别的，对最小负数 LONG_MIN 进行额外检查（因为二进制补码表示的整数不对称）。
有意思的是，书中把数组长度 43 这个莫名奇妙的常量（像「变」出来的）称为「魔数（magic number）」，是一种很糟糕的代码风格。但这里作者认为这数只出现一次，如果再另起名字反而会「使代码更长且扰乱命名空间」，为此宁愿牺牲程序可读性（大神的想法就是霸气啊）。但书中对 43 是怎么来的也做出了解释 —— 「在任何机器上这都足以容纳任何整数的十进制表示」。
不难看出，Atom_new 才是创建原子的核心函数，而 Atom_string 和 Atom_int 通过调用 Atom_new 间接完成，不需要涉及内部数据结构「原子表」的操作。体现了函数的对代码的封装和复用。这时我们更好奇 Atom_new 函数的实现，以及原子到底是如何通过「原子表」存储与管理的。
原子表
Atom 的实现需要维护原子表。
Atom_new、Atom_string和Atom_int搜索原子表并可能向其添加新元素，而Atom_length只是搜索原子表。
在原子表中已存在待添加原子时将不会重复添加，此时直接返回指向已存在原子的指针（原子的唯一性）。
Atom 接口通过原子表存储和管理原子，接口中的四个函数是基于原子表的增加和查找操作，因此原子表的表示是整章书的核心。那原子表到底是个什么玩意儿？其实就是一个哈希表，长这样：
对于原子表来说，选择哈希表作为数据结构是显然的。这里的哈希表是一个指针数组，每个指针指向一个链表，链表中的每个表项保存了一个原子：
<data 26> ≡
static struct atom {
struct atom *link;
int len;
char *str;
} *buckets[2048];
哈希表是一个数组，元素是一个指向原子结构体的指针（元素也称为「哈希桶」），同时数组的每一项也作为一个单链表的头结点，在发生冲突时把新数据往链表插入即可（拉链法）。单个原子由两部分组成，atom 结构体和紧接其后的字节序列（上图中灰色部分），atom 结构体示意图如下：
结构体中的 link 字段指向链表中下一个表项， len 字段保存了字节序列的长度，而 str 指向序列本身（即 str 的地址加一）。在内存布局中表现为字节序列挨着结构体存放，使得每个链表项的大小都刚好足够容纳其字节序列，巧妙利用指针在内存实现变长序列的存储。
Atom_new 函数
Atom_new对序列 str[0..len - 1]（或空序列，如果 len 为零）计算一个哈希码，将哈希码对哈希桶的数目取模得到一个索引值，并搜索该索引值对应的哈希桶（即链表）。如果函数发现 str[0..len - 1]已经在表中，就只返回对应的原子：
<functions 25> +≡
const char *Atom_new(const char *str, int len) {
unsigned long h;
int i;
struct atom *p;
assert(str);
assert(len >= 0);
<h ← hash str[0..len - 1] 29>
h %= NELEMS(buckets);
for (p = buckets[h]; p; p = p->link)
if (len == p -> len) {
for (i = 0; i < len && p->str[i] == str[i]; )
i++;
if (i == len)
return p->str;
}
<allocate a new entry 28>
return p->str;
}
<macros 28> ≡
#define NELEMS(x) ((sizeof (x))/(sizeof((x)[0])))
NELEMS 是求数组长度的宏，通过数组大小除以首元素大小实现。这套路在 C 程序中广泛使用。
在函数中先通过 <h ← hash str[0..len - 1] 29> 代码块计算传入字节序列 str[0..len - 1] 的哈希码得到数组下标，通过外层 for 循环遍历链表、内层循环逐字节比较查找原子是否已存在，找到则直接返回该原子。其中还使用了一个小技巧 —— 比较前忽略长度不等的原子。从这个程序中也可以体会到大师对 for 循环的巧妙运用（按 K&R 的观点 for 能完全取代 while）。
如果 str[0..len - 1] 不在表中，代码块 <allocate a new entry 28> 将会为序列新分配一块内存并将新的表项添加到 buckets[h] 的头部，从而将该序列添加到哈希表中（头插法）。
<allocate a new entry 28> ≡
p = ALLOC(sizeof (*p) + len + 1);
p->len = len;
p->str = (char *p)(p + 1)
if (len > 0)
memcpy(p->str, str, len);
p->str[len] = '\0'
p->link = buckets[h];
buckets[h] = p;
<includes 25> +≡
#include "mem.h"
ALLOC 是本书内存管理接口 mem.h 中定义的宏。
对代码的理解问题应该不大，熟悉的「分配空间、填充成员、插入链表」三步走。 p->str = (char *p)(p + 1) 语句通过指针偏移的方式对 p->str 赋值。对指针稍有了解的童鞋都知道，指针的「加一」并不是对其地址值加 1，而是加上指针目标类型所占空间字节数，如果是 int 指针就加 4，double 指针就加 8。同理这里实际上加了 atom 结构体类型的大小。但这里我们并不关心地址值加了多少，这条语句的唯一目的是让 p->str 指向紧挨着结构体后的那个字节，即字节序列的第一个字节（回顾原子的内存布局）。
最后需要解释如何计算字节序列 str[0..len - 1] 的哈希码，通过 <h ← hash str[0..len-1] 29> 代码块实现哈希函数，只有短短几行。
<h ← hash str[0..len-1] 29> ≡
for (h = 0, i = 0; i < len; i++)
{
h = (h<<1) + scatter[(unsigned char)str[i]]
}
无符号长整型变量 h 表示得到的哈希码，计算过程如下：以输入序列 str 的值为下标，通过「查表法」得到一个数，累加到前一次 h 值左移一位的结果上，遍历 str 上的所有字节，如此重复移位、累加，得到最终的 h。
由于 C 语言存在 char 类型符号二义性，把 ‘str[i]’ 强转为无符号避免其值大于 127 时下标出现负数。
dcatter 是一个 256 项的数组，它将字节值映射到随机数，这些随机数是通过调用标准库函数
rand生成的。经验表明，这种简单的方法有助于使哈希值分布更均匀。
<data 26> +≡
static unsigned long scatter[] = {
2078917053, 143302914, 1027100827, 1953210302, 755253631, 2002600785,
1405390230, 45248011, 1099951567, 433832350, 2018585307, 438263339,
813528929, 1703199216, 618906479, 573714703, 766270699, 275680090,
1510320440, 1583583926, 1723401032, 1965443329, 1098183682, 1636505764,
980071615, 1011597961, 643279273, 1315461275, 157584038, 1069844923,
471560540, 89017443, 1213147837, 1498661368, 2042227746, 1968401469,
1353778505, 1300134328, 2013649480, 306246424, 1733966678, 1884751139,
744509763, 400011959, 1440466707, 1363416242, 973726663, 59253759,
1639096332, 336563455, 1642837685, 1215013716, 154523136, 593537720,
704035832, 1134594751, 1605135681, 1347315106, 302572379, 1762719719,
269676381, 774132919, 1851737163, 1482824219, 125310639, 1746481261,
1303742040, 1479089144, 899131941, 1169907872, 1785335569, 485614972,
907175364, 382361684, 885626931, 200158423, 1745777927, 1859353594,
259412182, 1237390611, 48433401, 1902249868, 304920680, 202956538,
348303940, 1008956512, 1337551289, 1953439621, 208787970, 1640123668,
1568675693, 478464352, 266772940, 1272929208, 1961288571, 392083579,
871926821, 1117546963, 1871172724, 1771058762, 139971187, 1509024645,
109190086, 1047146551, 1891386329, 994817018, 1247304975, 1489680608,
706686964, 1506717157, 579587572, 755120366, 1261483377, 884508252,
958076904, 1609787317, 1893464764, 148144545, 1415743291, 2102252735,
1788268214, 836935336, 433233439, 2055041154, 2109864544, 247038362,
299641085, 834307717, 1364585325, 23330161, 457882831, 1504556512,
1532354806, 567072918, 404219416, 1276257488, 1561889936, 1651524391,
618454448, 121093252, 1010757900, 1198042020, 876213618, 124757630,
2082550272, 1834290522, 1734544947, 1828531389, 1982435068, 1002804590,
1783300476, 1623219634, 1839739926, 69050267, 1530777140, 1802120822,
316088629, 1830418225, 488944891, 1680673954, 1853748387, 946827723,
1037746818, 1238619545, 1513900641, 1441966234, 367393385, 928306929,
946006977, 985847834, 1049400181, 1956764878, 36406206, 1925613800,
2081522508, 2118956479, 1612420674, 1668583807, 1800004220, 1447372094,
523904750, 1435821048, 923108080, 216161028, 1504871315, 306401572,
2018281851, 1820959944, 2136819798, 359743094, 1354150250, 1843084537,
1306570817, 244413420, 934220434, 672987810, 1686379655, 1301613820,
1601294739, 484902984, 139978006, 503211273, 294184214, 176384212,
281341425, 228223074, 147857043, 1893762099, 1896806882, 1947861263,
1193650546, 273227984, 1236198663, 2116758626, 489389012, 593586330,
275676551, 360187215, 267062626, 265012701, 719930310, 1621212876,
2108097238, 2026501127, 1865626297, 894834024, 552005290, 1404522304,
48964196, 5816381, 1889425288, 188942202, 509027654, 36125855,
365326415, 790369079, 264348929, 513183458, 536647531, 13672163,
313561074, 1730298077, 286900147, 1549759737, 1699573055, 776289160,
2143346068, 1975249606, 1136476375, 262925046, 92778659, 1856406685,
1884137923, 53392249, 1735424165, 1602280572
};
Atom_length 函数
最后的 Atom_length 函数十分简单粗暴，通过两层 for 循环遍历指针数组和链表，找到原子后返回长度：
PS：对长度未知原子无法进行散列，只能遍历哈希表各 buckets。
<functions 25> +≡
int Atom_length(const char *str) {
struct atom *p;
int i;
assert(str);
for (i = 0; i < NELEMS(buckets); i++)
for (p = buckets[i]; p; p = p->link)
if (p->str == str)
return p->len;
assert(0);
return 0;
}
因为 Atom_length 函数返回已存在的原子长度，所以一定能找到该原子并返回长度（提前结束循环），否则代表参数有误，这时通过 assert(0) 实现了一个「已检查的运行时错误」。
assert(0) 页用于指明一些假定不会发生的情况，即所谓「不可能发生的情况」。
习题（完整代码见Github）
3.1 大多数教科书推荐将 buckets 的容量设置为素数。使用素数和良好的哈希函数，通常会使 buckets 中的链表长度具有更好的分布。Atom 使用了 2 的幂作为 buckets 的容量，这种做法有时被明确地作为「反面典型」引用。编写一个程序来生成或读入（假定）10000 个有代表性的字符串，并测量 Atom_new 的速度和哈希表各个链表长度的分布。接下来改变 buckets，使之包含 2039 项（小于 2048 的最大素数），重复上述测量。使用素数有改进吗？读者的结论在多大程度上取决于你用来测量的具体机器？
答：编写 main.c 程序，add_words_from_file 函数实现从 string.txt 文件中读取英语单词创建原子（由于常用单词重复多，读了 70000 个才达到题目的 10000 要求），同时通过 clock 库函数计算 Atom_new 的总运行时间。Atom_hash_analysis 函数统计哈希表中各长度链表数目（横向直方图显示）：
double run_time;
int main()
{
FILE *fp = NULL;
fp = fopen("../string.txt", "r");
if (fp == NULL)
{
printf("can't open file...\n");
return EXIT_FAILURE;
}
else
{
add_words_from_file(fp, 70000);
fclose(fp);
}
Atom_hash_analysis();
printf("Atom_new's total run time: %lf s\n", run_time);
return 0;
}
buckets 容量为 2048 时运行结果如下图：
从结果可以看出，一共创建 10057 个原子，Atom_new 总执行时间 1.7 s 左右（时间加倍后）。理想情况下哈希码应该均匀分布，每个链表应该有 4.91 个表项，即所有链表长度都在 4 和 5 这两行。但实际只有几百个。其余数目成递减趋势分布在更长的链表上，甚至还有 84 个链表是空的，最长的链表长度也到了 17。
修改 buckets 容量，将 atom.c 第 12 行的 buckets[2048] 改为 buckets[2039]，并对应修改 main.c 中的 BUCKETS_SIZE 宏，再次运行程序比较结果：
buckets 容量为 2039 时运行结果如下图：
将哈希表容量改为素数后，发现链表长度在平均长度上（4 和 5）的分布更为集中，而且空表只有 15 个，最长链表也不过 14。虽然速度比 2048 容量时稍慢了 0.2 s， 但换来了哈希表更均匀的分布，在 Linux 下运行结果相同，结果应该和机器关系不大。综上所述，使用素数是有改进的。
补充：作者 Github 代码与书本不一致的坑
由于我是在作者 Github 代码基础上编写程序，在这份代码中，书本对哈希码取余的语句被替换为按位与操作，利用的是 a % b == a & (b-1) 的原理，但前提是 b 是 2 的幂（Java 的 HashMap 就使用了这种方法）。所以如果把 buckets 容量改为 2039，链表分布和效率都十分「感人」，基本是堆到了一坨去了（一大半空表），时间都花在操作链表上去了，把代码改回书本的取模后结果和上面一致（奇怪的是，机工 04 版的代码也是按位与，但英文原版和人邮 11 版的都是取模）。
「一坨链表」壮观景象：
因此如果使用按位与运算来计算下标索引，哈希表长度老老实实用 2 的幂吧，不然位运算省出的这丁点儿时间都用来遍历链表了，得不偿失。
3.2 查阅文献寻找更好的哈希函数，可能的来源包括[Knuth, 1973b]一书、算法和数据结构方面类似的教科书及其引用的论文、以及编译器方面的教科书，如[Aho, Sethi and Ullman, 1986]一书。尝试这些函数并测量其改进情况。
答：从网上搜集资料得知，常见的字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash 等等，尝试使用 BKDHash、APHash 和 DJBHash 三种哈希函数并评估性能，测试结果如下：
函数调用需要额外开销，为了公平起见，把原来的「查表法」也封装为函数使用。
查表法
BKDHash 算法
APHash 算法
DJBHash 算法
| 算法 | Atom_new 执行时间 | 链表平均长度 | 链表最大长度 | 空表数 |
|---|---|---|---|---|
| 原书查表法 | 2.049 s | 5.12 | 17 | 84 |
| BKDHash 算法 | 2.085 s | 4.95 | 15 | 16 |
| APHash 算法 | 2.294 s | 4.94 | 21 | 14 |
| DJBHash 算法 | 1.909 s | 4.95 | 13 | 14 |
从对比数据中可以看出，数中的查表法并不是十分出色，在速度、链表分布都不占优势。而最给力的是 DJBHash 算法，其链表长度具有更好的分布（集中在平均长度处，空表和长链表少），因此提高了哈希表的操作效率。
在 Mark Allen Weiss 的《数据结构与算法分析 —— C 语言描述》一书中有简单介绍这种算法，并把它称为「一个好的散列函数」。我们来看一下代码：
// DJB Hash Function
unsigned int DJBHash(char *str, int len)
{
unsigned int hash = 5381;
int i;
for (i = 0; i < len; i++)
{
hash += (hash << 5) + (*str++);
}
return (hash & 0x7FFFFFFF);
}
hash += (hash << 5) + (*str++) 根据 Horner 法则计算一个（32的）多项式函数，使得哈希值冲突少且分布均匀。至于为什么是移 5 位，书中的解释为代替「乘上 27」（和 32 接近），而 27 是「26 个字母加一个空格」得来的。由于数据源是英语文章，这也许是 DJBHash 更适合的原因（所以散列函数要根据数据源类型选择咯）。
补充：进一步测试发现，对于「有意义的英文句子」数据源，选用 DJBHahs、SDBMHash 和 BKDRHash 算法更为适合。
3.3 解释 Atom_new 不使用标准 C 库函数 strcmp 比较字节序列的原因。
答：C 库函数 strcmp 只能实现字符串比较（带结束符），而传入 Atom_new 函数的字节序列不一定存在 ‘\0’，导致 strcmp 函数无法正常工作。
3.4 以下是另一种声明原子结构的方法：
struct atom {
struct atom *link;
int len;
char str[1];
};
分配一个包含长度为 len 的字符串 struct atom 实例时，需要用 ALLOC(sizeof(*p) + len)，这为 link 和 len 字段分配了空间，而且为 str 字段分配的空间足以容纳 len + 1 个字节。正文中将 str 声明为指针会引入一层额外的间接，这种方法避免了间接方式所带来的时间和空间开销。遗憾的是，这种「技巧」违反了 C 语言标准，因为客户程序需要访问超出 str[0] 的各字节，这种访问的效果是未定义的。实现这种方法，并测量间接方式所带来的时间和空间开销。为了节省，是否值得违反标准？
答：题目试图通过使用 str[1] 定义数组的方式，把地址与空间合二为一（数组名为其地址），这样可以节省一个指针的空间，而且免去了间接寻址的开销。修改程序中 atom 结构以及 atom_new 填充结构的代码，实现上述设想，并测量时间与空间开销：
<allocate a new entry 28> ≡
p = ALLOC(sizeof (*p) + len);
p->len = len;
// p->str = (char *)(p + 1); // 注释掉，str 不再用作指针
if (len > 0)
memcpy(p->str, str, len); // 直接从结构体 str 成员空间开始拷贝
p->str[len] = '\0';
p->link = buckets[h];
buckets[h] = p;
对运行时间测量，发现改进十分有限，再通过 Linux 下的 pmap -X pid 命令查看内存分布，可以看到堆（heap）内存分配由 284K 减少到 276 K：
因为每个表项节省了一个字节（由于存在内存对齐，结构体所占大小不变），10000 个原子节省了 10K 左右，基本能对上。虽然节省空间，而引入了未定义操作，程序存在安全隐患。除非是对效率和空间十分看重的场合（如嵌入式系统），否则不值得冒这个险。
3.5 Atom_new 会比较 struct atom 实例的 len 字段与输入字节序列的长度，以避免比较长度不同的序列。如果每个原子的哈希码（而不是 buckets 的索引）也存储在 struct atom 中，还可以比较哈希码。实现并测量这种「改进」。这种做法值得吗？
3.6 Atom_length 执行得比较慢。修改 Atom 的实现，使得 Atom_length 的运行时间与 Atom_new 大致相同。
3.7 Atom 接口之所以演变到现在这种形式，是因为其中的各个函数是客户程序最常用的。还可能使用其他的函数和设计，这里和后续的各习题将探讨这些可能性，请实现
extern void Atom_init(int hint);
其中 hint 是对客户程序预期创建的原子数目的估计。在可能调用 Atom_init 时，读者会添加何种已检查的运行时错误以约束其行为？
3.8 在对 Atom 接口扩展中，可能提供几种函数来释放原子。例如下述函数：
extern void Atom_free(const char *str);
extern void Atom_reset(void);
可以分别释放 str 指定的原子及所有原子。请实现这些函数。不要忘记指定并实现适当的已检查的运行时错误。
3.9 一些客户程序开始执行时，会将大量字符串设置为原子，供后续使用。请实现
extern void Atom_vload(const char *str, ...);
extern void Atom_aload(const char *strs[]);
Atom_vload 会将可变长参数列表中的字符串创建为原子，直至遇到 NULL 指针为止，而 Atom_aload 对一个指针数组做同样的操作（即各数组项为指向字符串的指针，遇到 NULL 指针表示数组结束）。
3.10 如果客户程序承诺不释放字符串，那么可以避免复制字符串，对于字符串常数来说这是一个简单的事实，请实现
extern const char *Atom_add(const char *str, int len);
其工作方式如同 Atom_new，但并不复制字节序列。如果读者提供 Atom_add 和 Atom_free（以及习题 3.8 中的 Atom_reset），必须指定并实现何种已检查的运行时错误？
参考文章
- 各种字符串Hash函数比较 - BYVoid Mark Allen Weiss -《数据结构与算法分析 —— C 语言描述》（5.2 散列函数）
