layout: post

title: 第三章：名称与名称表

st_table

作为方法表和实例表，st_table在前面提到过。在本章中，让我们详细看一下st_table的机制。

概要

我之前提到过，st_table是一个hash表。什么是hash表呢？它是一种数据结构，记录一对一的关系，比如变量名与其值，函数名与其体，等等。

然而，除hash表外，当然还有其它的数据结构，可以记录一对一的关系。比如下面的list数据结构也能满足这个目的。

struct entry { ID key; VALUE val; struct entry next; / 指向下一项 */ };

然而，这种方法缓慢。如果list中包含上千项，在最差的情况下，必需穿越上千次的链。 换句话说，搜索时间随元素数量的比例而增长。这很糟糕。从远古时代开始， 就酝酿出许多不同的提速方法。hash表就是提速方法之一。换句话说，这里的要点不在于是否需要hash表，而是因为它可以更快一些。

那么接下来，我们来看看st_table。但首先说一下，这个库并非Matsumoto所创，而是： ▼ st.c credits

1 / This is a public domain general purpose hash table package written by Peter Moore @ UCB. /

(st.c)

如上所示。

顺便说一下，当我用Google搜索时，找到了另一个版本，它提到st_table是“STring TABLE”的缩写。 然而，我发现一个矛盾，它有“通用目的”和“字符串”两个方面。

hash表是什么？

可以这样理解hash表：让我们把它看作一个拥有n项的数组。比如，假设n=64（图1）。

数组 图1: 数组

然后，我们指定一个函数f，用一个键值产生一个0到n-1（0-63）的整数i。我们称这个f为hash函数。 对于给定的相同键值，f总会产生i。比如，如果我们做个假设，把键值限定为正整数，那么如果键值被64整除， 那么，余数总是在0到63之间。这个计算方法就可以作为函数f。

记录关系时，给定一个键值，函数f产生i，把它放到我们预备好的数组中索引为i的位置上。 换句话说，通过索引访问数组非常快。因此，基本的想法就是把键值变成整数。

数组赋值 图2: 数组赋值

然而，在现实世界中，问题没那么简单。这个想法有一个关键的问题。因为n只是64，如果要记录多于64个的关系， 肯定会有两个不同的键值有相同的索引。即便少于64，也可能会有相同的发生。以前面hash函数“key % 64”为例， 键值65和129的hash值都是1。这称为hash值冲突。有许多办法用来解决冲突。

比如，如果发生冲突，把它插入下一个元素的位置。这种方法叫做开放寻址。（图3）

开放寻址 图3: 开放寻址

除了像这样使用数组，还有其它的方式，比如使用指针，数组的每个元素都是一个指向各自链表的指针。 那么当发生冲突时，链表随之生长。这称为链接（chaining）。（图4）st_table使用的就是这种链接的方法。

链接 图4: 链接

然而，如果确定用到是哪些键值，那么可以想象有一个绝不会产生冲突的hash函数。这种函数称为“完美hash函数”。 实际上，确实有一些工具能够对一套给定的任意字符串创建了一个完美hash函数。GNU gpref就是其中之一。 ruby的解析器实现就使用了GNU gperf，但是……这还不到我们讨论它的时候。我们会在本书的第二部分讨论它。 数据结构

让我们从看源码起步。正如在引介的章节中所写，如果既有数据又有代码，最好先看数据。下面就是st_table的数据类型。 ▼ st_table

9 typedef struct st_table st_table;

16 struct st_table { 17 struct st_hash_type type; 18 int num_bins; / slot count / 19 int num_entries; / total number of entries / 20 struct st_table_entry **bins; / slot */ 21 };

(st.h)

▼ struct st_table_entry

16 struct st_table_entry { 17 unsigned int hash; 18 char key; 19 char record; 20 st_table_entry *next; 21 };

(st.c)

st_table主要是一个表的数据结构。st_table_entry持有存储的一个值。st_table_entry包含一个称为next的成员， 用于将st_table_entry放入一个链表。这是链接方法链的部分。这里用到了st_hash_type数据类型，稍后解释。 先让我解释其它部分，这样，你就能够对比和理解其角色了。

st_table数据结构 图5: st_table数据结构

那么让我们来看看st_hash_type。 ▼ struct st_hash_type

11 struct st_hash_type { 12 int (compare)(); / comparison function / 13 int (hash)(); / hash function / 14 };

(st.h)

这还是第三章，那么我们换种方式来看它。

int (*compare)()

这个部分表示compare成员的数据类型是一个函数指针，其返回值为int。hash也具有同样的类型。 这个变量可以用下面的方式替代：

int great_function(int n) { / ToDo: 做一些伟大的事情! / return n; }

{ int (*f)(); f = great_function;

这样调用：

  1. (*f)(7);

}

我们回到st_hash_type。hash和compare两个成员之中，hash就是前面提到的hash函数f。

另一方面，compare这个函数的作用是评估值是否相同。在链接方法中，相同hash值的点里可能插入了多个元素。 为了准确知道查找的是哪个元素，必需使用一个我们绝对信任的比较函数。compare就是那个函数。

这个st_hash_type是一项很好的泛化的技术。hash表本身并不确定存储键值的数据类型是什么。 比如，在ruby中，st_table的键值是ID或char*或VALUE，但是对每个（数据类型）都使用同样的hash是愚蠢的。 通常，随键值数据类型不同而改变的就是hasn函数之类的东西。对于内存管理和冲突检测之类的东西，通常大部分代码都一样。 只有实现需要随数据类型不同而改变的部分绑定到一个函数中，使用一个函数指针指向那个函数。 这样的话，组成hash表实现的主体代码就可以使用它了。

在面向对象的语言中，你可以把过程附着在一个对象上，传递它，因此，不需要这种机制。 也许说这种机制作为一种语言特征内建其中更合适。 st_hash_type的例子

使用一个类似于st_hash_type的数据结构是一种很好的抽象，但另一方面，理解它实际传递是何种代码可能就有些困难了。 如果不检查hash或compare用的是什么函数，我们便无法掌握事实。为了理解这点，可能要看一下st_init_numtable()才行， 在前面一章中，我们介绍过它。这个函数创建了一个表，其键值的数据类型为整数。 ▼ st_init_numtable()

182 st_table* 183 st_init_numtable() 184 { 185 return st_init_table(&type_numhash); 186 }

(st.c)

st_init_table()是这样一个函数，它完成表内存分配等工作。type_numhash是一个st_hash_type （它是一个名为st_table“类型”的成员）。看看这个type_numhash： ▼ type_numhash

37 static struct st_hash_type type_numhash = { 38 numcmp, 39 numhash, 40 };

552 static int 553 numcmp(x, y) 554 long x, y; 555 { 556 return x != y; 557 }

559 static int 560 numhash(n) 561 long n; 562 { 563 return n; 564 }

(st.c)

非常简单。ruby使用的这个表基本上就是这个type_numhash。 st_lookup()

接下来，我们看一下使用这个数据结构的函数。首先，从搜索的函数看起是个好主意。 下面就是搜索hash表的函数st_lookup()。

  1. ▼ st_lookup()
  3.  247  int
  4.  248  st_lookup(table, key, value)
  5.  249      st_table *table;
  6.  250      register char *key;
  7.  251      char **value;
  8.  252  {
  9.  253      unsigned int hash_val, bin_pos;
  10.  254      register st_table_entry *ptr;
  11.  255
  12.  256      hash_val = do_hash(key, table);
  13.  257      FIND_ENTRY(table, ptr, hash_val, bin_pos);
  14.  258
  15.  259      if (ptr == 0) {
  16.  260          return 0;
  17.  261      }
  18.  262      else {
  19.  263          if (value != 0)  *value = ptr->record;
  20.  264          return 1;
  21.  265      }
  22.  266  }
  24. (st.c)

重要的部分几乎都在do_hash()和FIND_ENTRY()中。让我们按顺序看一下。

  1. ▼ do_hash()
  3.   68  #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
  5. (st.c)

慎重起见，我们记下这个难于理解的宏的主体：

(table)->type->hash

是一个函数指针，key作为参数传递给它。这是调用函数的语法。*不是用在表上。换句话说，这个宏是一个hash值产生器， 每个数据类型都有事先预备好的hash函数type->hash，用它对键值产生一个hash值。

下面，继续来看FIND_ENTRY()。

  1. ▼ FIND_ENTRY()
  3.  235  #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
  4.  236      bin_pos = hash_val%(table)->num_bins;\
  5.  237      ptr = (table)->bins[bin_pos];\
  6.  238      if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
  7.  239          COLLISION;\
  8.  240          while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
  9.  241              ptr = ptr->next;\
  10.  242          }\
  11.  243          ptr = ptr->next;\
  12.  244      }\
  13.  245  } while (0)
  15.  227  #define PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && \
  16.           (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
  18.   66  #define EQUAL(table,x,y) \
  19.           ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
  21. (st.c)

COLLISION是一个调试宏，所以，我们（应该）忽略它。

FIND_ENTRY()的参数，从左开始是：

  • st_table
  • 这个参数指向的找到项
  • hash值
  • 临时变量

第二个参数会指向找到的st_table_entry*。

在最外层的，do .. while(0)用于对多表达式的宏进行安全封装。与其说是ruby， 不如说这是C语言预处理器的一种常用手法。在if(1)的情况下，可能需要附加else。 在while(1)的情况下，可能需要在最后添加一个break。

还有，while(0)后面没有分号。说到原因

FIND_ENTRY();

这样就不会让出现在通常表达式后的逗号成为徒劳。

st_add_direct()

继续，让我们来看看st_add_direct()，它向hash表中添加一个新的关系。 这个函数并不检查键值是否已经存在。它总会添加一个新的项。这就是函数名中direct的含义所在。

  1. ▼ st_add_direct()
  3.  308  void
  4.  309  st_add_direct(table, key, value)
  5.  310      st_table *table;
  6.  311      char *key;
  7.  312      char *value;
  8.  313  {
  9.  314      unsigned int hash_val, bin_pos;
  10.  315
  11.  316      hash_val = do_hash(key, table);
  12.  317      bin_pos = hash_val % table->num_bins;
  13.  318      ADD_DIRECT(table, key, value, hash_val, bin_pos);
  14.  319  }
  16. (st.c)

如同前面一样，这里调用do_hash()宏获取一个值。随后，下一个计算等同于FIND_ENTRY()开始的部分， 它以hash值得到真正的索引。

插入操作看上去是以ADD_DIRECT()实现的，既然名字全部大写，我们期待它是一个宏。

  1. ▼ ADD_DIRECT()
  3.  268  #define ADD_DIRECT(table, key, value, hash_val, bin_pos) \
  4.  269  do {                                                     \
  5.  270      st_table_entry *entry;                               \
  6.  271      if (table->num_entries / (table->num_bins)           \
  7.                               > ST_DEFAULT_MAX_DENSITY) {      \
  8.  272          rehash(table);                                   \
  9.  273          bin_pos = hash_val % table->num_bins;            \
  10.  274      }                                                    \
  11.  275                                                           \
  12.           /* (A) */                                            \
  13.  276      entry = alloc(st_table_entry);                       \
  14.  277                                                           \
  15.  278      entry->hash = hash_val;                              \
  16.  279      entry->key = key;                                    \
  17.  280      entry->record = value;                               \
  18.           /* (B) */                                            \
  19.  281      entry->next = table->bins[bin_pos];                  \
  20.  282      table->bins[bin_pos] = entry;                        \
  21.  283      table->num_entries++;                                \
  22.  284  } while (0)
  24. (st.c)

第一个if是一个异常情况，我稍后解释它。

（A） 分配以及初始化一个st_table_entry。

（B） 把entry插入到列表的起始位置。这是处理列表的常见手法。换句话说，

entry->next = list_beg; list_beg = entry;

将一个项插入到列表的前端。这类似于Lisp语言中的“cons-ing”。自己检查一下， 即便list_beg为空，这段代码也是正确的。

现在，让我来解释一下我留下的那段代码。

  1. ▼ ADD_DIRECT()-rehash
  3.  271      if (table->num_entries / (table->num_bins)           \
  4.                               > ST_DEFAULT_MAX_DENSITY) {      \
  5.  272          rehash(table);                                   \
  6.  273          bin_pos = hash_val % table->num_bins;            \
  7.  274      }                                                    \
  9. (st.c)

DENSITY is“浓度”。换句话说，这个条件检查hash表是否“拥挤”。在st_table中， 随着使用相同bin_pos的增长，链表会变得更长。换句话说，搜索会变慢。 如果bin中的元素过多，那么就应该增加bin的数量，降低拥挤程度。

当前ST_DEFAULT_MAX_DENSITY是

  1. ▼ ST_DEFAULT_MAX_DENSITY
  3.   23  #define ST_DEFAULT_MAX_DENSITY 5
  5. (st.c)

因为这个设置，如果在所有的bin_pos都有5个st_table_entries，那么大小就要增加。 st_insert()

st_insert()只是将st_add_direct()和st_lookup()组合了起来，因此， 如果你理解了那两个，这个就容易了。

  1. ▼ st_insert()
  3.  286  int
  4.  287  st_insert(table, key, value)
  5.  288      register st_table *table;
  6.  289      register char *key;
  7.  290      char *value;
  8.  291  {
  9.  292      unsigned int hash_val, bin_pos;
  10.  293      register st_table_entry *ptr;
  11.  294
  12.  295      hash_val = do_hash(key, table);
  13.  296      FIND_ENTRY(table, ptr, hash_val, bin_pos);
  14.  297
  15.  298      if (ptr == 0) {
  16.  299          ADD_DIRECT(table, key, value, hash_val, bin_pos);
  17.  300          return 0;
  18.  301      }
  19.  302      else {
  20.  303          ptr->record = value;
  21.  304          return 1;
  22.  305      }
  23.  306  }
  25. (st.c)

它会检查元素是否已经在表中存在。只有它不存在时，才会添加。如果插入，返回0，否则，返回1。 ID和符号

我已经讨论过什么是ID了。它将一个字符串对应为一个值，以它声明不同的名字。 实际的数据类型是unsigned int。 从char*到ID

字符串到ID的转换由rb_intern()完成。这个函数相当长，让我们省略掉中间的部分。

  1. ▼ rb_intern() (simplified)
  3. 5451  static st_table *sym_tbl;       /*  char* to ID   */
  4. 5452  static st_table *sym_rev_tbl;   /*  ID to char*   */
  6. 5469  ID
  7. 5470  rb_intern(name)
  8. 5471      const char *name;
  9. 5472  {
  10. 5473      const char *m = name;
  11. 5474      ID id;
  12. 5475      int last;
  13. 5476
  14.           /* If for a name, there is a corresponding ID that is already
  15.           registered, then return that ID */
  16. 5477      if (st_lookup(sym_tbl, name, &id))
  17. 5478          return id;
  19.           /* omitted ... create a new ID */
  21.           /* register the name and ID relation */
  22. 5538    id_regist:
  23. 5539      name = strdup(name);
  24. 5540      st_add_direct(sym_tbl, name, id);
  25. 5541      st_add_direct(sym_rev_tbl, id, name);
  26. 5542      return id;
  27. 5543  }
  29. (parse.y)

字符串和ID的对应关系由st_table完成。这里可能没有什么特别难的部分。

省略的部分做了些什么呢？它对全局变量名和实例变量名进行特殊处理，给它们设上了标记。 这是因为，在解析器中，根据ID了解变量的分类是必要的。然而，ID的基础部分与此无关， 因此，我就不在这里解释了。 从ID到char*

rb_intern()的反向操作是rb_id2name()，它用一个ID产生一个char*。你或许已经知道， id2name中2是“to”。“To”和“Two”同音，因此用“2”表示“to”。这种用法很常见。

这个函数也要设置ID分类标志，因此它也很长，让我们简化一下。

  1. ▼ rb_id2name() （简化版）
  3. char *
  4. rb_id2name(id)
  5.     ID id;
  6. {
  7.     char *name;
  9.     if (st_lookup(sym_rev_tbl, id, &name))
  10.         return name;
  11.     return 0;
  12. }

或许它看上去有些过于简化，但事实上，如果我们去掉了细节，它真的就是这么简单。

我想强调的是，找到name之后，并不进行复制。ruby API并不需要（甚至禁止）对返回值free()。 传递参数后，总是要复制来用。换句话说，创建和释放都是由一方完成，用户或是ruby。

因此，当创建和释放无法在一个值上完成（传递而不返回时），就要使用Ruby对象。我还没有讨论过它。 当Ruby对象不再使用，即便我们不关心它，它也可以自动释放。 VALUE和ID的转换

在Ruby的层次上，ID是一个Symbol类的实例。可以这样得到它：”string”.intern。 String#intern的实现是rb_str_intern()。

  1. ▼ rb_str_intern()
  3. 2996  static VALUE
  4. 2997  rb_str_intern(str)
  5. 2998      VALUE str;
  6. 2999  {
  7. 3000      ID id;
  8. 3001
  9. 3002      if (!RSTRING(str)->ptr || RSTRING(str)->len == 0) {
  10. 3003          rb_raise(rb_eArgError, "interning empty string");
  11. 3004      }
  12. 3005      if (strlen(RSTRING(str)->ptr) != RSTRING(str)->len)
  13. 3006          rb_raise(rb_eArgError, "string contains `\\0'");
  14. 3007      id = rb_intern(RSTRING(str)->ptr);
  15. 3008      return ID2SYM(id);
  16. 3009  }
  18. (string.c)

作为ruby类库代码的样例，这个函数相当合理。注意使用RSTRING()转型的地方，这里访问了数据结构的成员。

我们来读读代码。首先，rb_raise()只是一个错误处理，我们暂时忽略它。这里有我们之前看过的rb_intern()。 ID2SYM() 是一个宏，它将ID转换为Symbol。

反向操作由Symbol#to_s完成，实现在sym_to_s中。

  1. ▼ sym_to_s()
  3.  522  static VALUE
  4.  523  sym_to_s(sym)
  5.  524      VALUE sym;
  6.  525  {
  7.  526      return rb_str_new2(rb_id2name(SYM2ID(sym)));
  8.  527  }
  10. (object.c)

SYM2ID()是一个宏，它将Symbol（VALUE）转换为一个ID。

看上去，这个函数什么都没做。然而，可能需要注意一下内存处理的部分。rb_id2name()返回一个char*， 它不能用 free()释放。rb_str_new2()复制了参数的char*，使用的是它的拷贝。按照这种方式，如果采用一致的策略，就允许以链的方式编写函数。