原子(字节序列)、哈希表存储、散列函数

《C 语言接口与实现》读书笔记 —— 第三章

Posted by Shao Guoji on December 8, 2017

对比本书后面的内容来看,这章算比较轻松的,涉及到的函数也很少。

书里所谓的「原子」并没有「微小」、「原子操作」等意味,而是出于另一个目的 —— 作为字节序列的副本,这是典型的「替换思维」,用简单代替复杂。如同 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_newAtom_string 函数的设计。


实现

Atom 接口就像一个黑盒,你把创建原子所需的字节序列传进去,便会得到一个原子 —— const char * 类型的指针。那究竟盒子内部是如何运作的呢?把盒子打开看个究竟,或许这才是更有意思的事情。

创建原子操作

Atom_stringAtom_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_stringAtom_int 通过调用 Atom_new 间接完成,不需要涉及内部数据结构「原子表」的操作。体现了函数的对代码的封装和复用。这时我们更好奇 Atom_new 函数的实现,以及原子到底是如何通过「原子表」存储与管理的。

原子表

Atom 的实现需要维护原子表。Atom_newAtom_stringAtom_int 搜索原子表并可能向其添加新元素,而 Atom_length 只是搜索原子表。

在原子表中已存在待添加原子时将不会重复添加,此时直接返回指向已存在原子的指针(原子的唯一性)。

Atom 接口通过原子表存储和管理原子,接口中的四个函数是基于原子表的增加和查找操作,因此原子表的表示是整章书的核心。那原子表到底是个什么玩意儿?其实就是一个哈希表,长这样:

图1 哈希表

对于原子表来说,选择哈希表作为数据结构是显然的。这里的哈希表是一个指针数组,每个指针指向一个链表,链表中的每个表项保存了一个原子:

<data 26> 
  static struct atom {
      struct atom *link;
      int len;
      char *str;
  } *buckets[2048];

哈希表是一个数组,元素是一个指向原子结构体的指针(元素也称为「哈希桶」),同时数组的每一项也作为一个单链表的头结点,在发生冲突时把新数据往链表插入即可(拉链法)。单个原子由两部分组成,atom 结构体和紧接其后的字节序列(上图中灰色部分),atom 结构体示意图如下:

图2 单个原子结构

结构体中的 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 时运行结果如下图:

图3 数组长度 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 数组长度 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 版的都是取模)。

「一坨链表」壮观景象:

图5 一坨链表

因此如果使用按位与运算来计算下标索引,哈希表长度老老实实用 2 的幂吧,不然位运算省出的这丁点儿时间都用来遍历链表了,得不偿失。

3.2 查阅文献寻找更好的哈希函数,可能的来源包括[Knuth, 1973b]一书、算法和数据结构方面类似的教科书及其引用的论文、以及编译器方面的教科书,如[Aho, Sethi and Ullman, 1986]一书。尝试这些函数并测量其改进情况。

答:从网上搜集资料得知,常见的字符串哈希函数有 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash 等等,尝试使用 BKDHash、APHash 和 DJBHash 三种哈希函数并评估性能,测试结果如下:

函数调用需要额外开销,为了公平起见,把原来的「查表法」也封装为函数使用。

查表法

图6 查表法

BKDHash 算法

图7 BKDHash 算法

APHash 算法

图8 APHash 算法

DJBHash 算法

图9 APHash 算法

算法 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),这为 linklen 字段分配了空间,而且为 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:

图10 更改前

图11 更改后

因为每个表项节省了一个字节(由于存在内存对齐,结构体所占大小不变),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_addAtom_free(以及习题 3.8 中的 Atom_reset),必须指定并实现何种已检查的运行时错误?

参考文章