##第三章 名称和命名表 ####st_table 作为存储方法的表和实例变量的表，st_table已经出现过几次了。本章首先就st_table做详细的说明。 ###概要 我们已经说过st_table是哈希表。哈希表是保存一对一对应关系的数据结构。这种一对一关系可以是变量名和变量的值，也可以是函数名和函数的实体，等等。 当然除了哈希表也可以用其它的数据结构来表示一一对应关系。比如可以下面这种list的结构体。 ``` struct entry { ID key; VALUE val; struct entry *next; /* 指向下一个元素 */ }; ``` 但是这种方法很慢。如果存在1000个元素的话，最糟糕的情况下要遍历1000次这个链表。也就是探索的时间和元素的个数是成正比的。这样的话就会很糟糕。所以从很早就考虑了各种解决方法。哈希表就是这个解决方法的一种。也就是说哈希表并不是仅有的方法，但是能够带来高速化的处理。 接下来我们实际来看st_table。注意看，这个库并不是松本先生的原创。 ``` 1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */ (st.c) ``` ……恩至少注释是这么说的。 顺带一提，用谷歌检索到的其他版本的注释上说，st_table是string table的简称。但是我认为general purpose和string到底是有些矛盾的……。 ####所谓哈希表 哈希表的设想如下。首先有一个长度为n的数组。比如说n=64。 [](img/ch_name_array.jpg) [](img/ch_name_array.jpg) 然后准备一个能够将键映射到0到n-1(0~63)的整数i的函数f。这个f被叫做哈希函数。对于同一个键，f必须保证每次都返回相同的i。假设键的值是整数的话，这个整数被64整除的余数肯定是在0到63之间的。所以这个取余的计算可以成为f函数。 要找到对应关系的存储位置的时候，先对键调用哈希函数f，求得i的值，然后数组的第i个元素就好了。也就是说，因为访问数组的某个元素是十分快速的，所以只需要找到某种方法把键转换成整数就好了，这个就是hash的核心思想。 [](img/ch_name_aset.jpg) [](img/ch_name_aset.jpg) 可惜世界上是没有这么理想的情况的。这个方法有个致命的问题。n现在只有64个元素，所以当需要对应64个以上的元素键的话肯定会发生重复。就算键没超过64个，也有可能发生两个键对应相同的索引的情况。比如刚才用64取余的的方法，当键的值是65或者129的时候，对应的哈希值都是1。我们把这个叫做哈希冲突。解决冲突的方法主要有几种。 比如发生冲突的话可以按照下面的方法放入元素。这个方法叫做开放定址法。 [](img/ch_name_nexti.jpg) [](img/ch_name_nexti.jpg) 另外有一种方法，不是直接将元素存在数组中，而是在数组中存放一个个链表的指针。发生冲突的时候逐渐延长链表的长度。这个方法叫做连锁法。st_table采用的就是这个连锁法。 [](img/ch_name_chain.jpg) [](img/ch_name_chain.jpg) 说来如果能够实现知道键的集合的内容的话也许可以设计出一个绝对不会发生冲突的哈希函数。这个函数被叫做绝对哈希函数。然后还有针对任何的字符串的集合来生成哈希函数的工具，比如说GNU的gperf。ruby的语法解析器实际上也用到了这个工具……还不是说这个的时候。我们会在第二部分继续介绍。 ###数据结构 现在我们来看实际的代码。在序章中已经说过，如果同时存在数据类型和代码的话当然是先读数据类型。下面我们来看一下st_table实际使用的数据类型。 ``` 9 typedef struct st_table st_table; 16 struct st_table { 17 struct st_hash_type *type; 18 int num_bins; /* 槽的个数 */ 19 int num_entries; /* 总共存放的元素数*/ 20 struct st_table_entry **bins; /* 槽 */ 21 }; (st.h) ``` ``` 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_hash_type的类型，我们会稍后对此说明首先就别的地方对照下图进行逐一确认好了。 [](img/ch_name_sttable.jpg) [](img/ch_name_sttable.jpg) 接下来我们来看st_hash_type。 ``` 11 struct st_hash_type { 12 int (*compare)(); /* 比较函数 */ 13 int (*hash)(); /* 哈希函数 */ 14 }; (st.h) ``` 毕竟才第三章我们还是认真得看下去吧。 ``` int (*compare)() ``` 这个表示的是返回int的函数指针成员compare。hash也是同理。这种变量用下面的方法代入。 ``` int great_function(int n) { /* ToDo */ return n; } { int (*f)(); f = great_function; ``` 然后用下面的方法调用。 ``` (*f)(7); } ``` 现在回到st_hash_type的解说。hash compare这个两个成员中，hash就是之前说过的哈希函数。 compare则是用来判断键是否是同一个的函数。因为连锁法中相同的哈希值n的地方会存放多个要素。为了知道其中哪个元素才是我们真正需要的，这就需要有一个可以完全信任的比较函数。这个比较函数就是compare。 这个st_hash_type是一种很巧妙的通用化方法。哈希表是无法确定自己保存的键的类型的。比如ruby的st_table的键勊是ID，char*，VALUE。如果每种类型都要设计一种哈希的话实在是太蠢了。因为键的类型不同而导致改变的仅仅是哈希函数的部分而已，无论是分配内存还是检测冲突的大部分代码都是相同的。于是我们仅仅把不同的地方作为函数特化起来，用函数指针来制定其具体函数来使用。这样的话就可以使本来就占据着大部分代码的哈希表的实装更加灵活。 面向对象的语言本身就把对象和过程捆绑在一起所以这种构造是没有必要的。或者说这种构造作为语言的功能已经被嵌入进去了。 st_hash_type的例子 st_hash_type的结构体虽然是一种很成功的通用方法，但是也是的代码变得复杂难懂起来。不具体看一下hash和compare函数的话总是没有什么实感。于是现在就可以来看看上一章也出现的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。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() 接下来我们来看哈希结构体里面的函数，从开始可以先从探索函数入手。哈希表中的探索函数st_lookup()内容如下。 ``` 247 int 248 st_lookup(table, key, value) 249 st_table *table; 250 register char *key; 251 char **value; 252 { 253 unsigned int hash_val, bin_pos; 254 register st_table_entry *ptr; 255 256 hash_val = do_hash(key, table); 257 FIND_ENTRY(table, ptr, hash_val, bin_pos); 258 259 if (ptr == 0) { 260 return 0; 261 } 262 else { 263 if (value != 0) *value = ptr->record; 264 return 1; 265 } 266 } (st.c) ``` 重要的部分几乎都在do_hash()和FIND_ENTRY()里面，我们按着顺序来看。 do_hash() ``` 68 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) (st.c) ``` 保险起见我们还是把宏里面的复杂的部分单独抽取出来 ``` (table)->type->hash ``` 这个函数指针带上一个参数key之后就调用了相关的函数。*的内容不是table(而是表示这个带参数的函数指针)。也就是说，这个宏使用按照类型定义的不同的哈希函数type->hash，带上参数key来求哈希值。 接下去我们来看FIND_ENTRY()。 ``` 235 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 236 bin_pos = hash_val%(table)->num_bins;\ 237 ptr = (table)->bins[bin_pos];\ 238 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ 239 COLLISION;\ 240 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 241 ptr = ptr->next;\ 242 }\ 243 ptr = ptr->next;\ 244 }\ 245 } while (0) 227 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && \ (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 66 #define EQUAL(table,x,y) \ ((x)==(y) || (*table->type->compare)((x),(y)) == 0) (st.c) ``` COLLISION是用来debug的宏，直接无视好了。 FIND_ENTRY()的参数从前向后分别是 1.st_table 2.应该使用的临时变量 3.哈希值 4.检索的键 第二个参数用来保存查询到的st_table_entry*的值。 另外最外面一层为了保证由多个式子组成的宏安全执行，使用了do～while(0)。这个是ruby，严格来说是c语言的预处理的风格。使用if(1)的话会不小心带上else。而使用while(1)的话最后还需要break。 while(0)的后面不接分号也是有讲究的。如果你硬要问为什么，请看 ``` FIND_ENTRY(); ``` 一般都是这样写，所以最后的就不会多出来一个分号。 ####st_add_direct() 接下去我们来看在哈希表中添加新数据的函数st_add_direct()。这个函数不检查键是否已经登录，而是无条件得追加新的项目。这个就是direct的意思。 ``` 308 void 309 st_add_direct(table, key, value) 310 st_table *table; 311 char *key; 312 char *value; 313 { 314 unsigned int hash_val, bin_pos; 315 316 hash_val = do_hash(key, table); 317 bin_pos = hash_val % table->num_bins; 318 ADD_DIRECT(table, key, value, hash_val, bin_pos); 319 } (st.c) ``` 和刚才一样为了求哈希值使用了宏do_hash(),接下来的计算也在FIND_ENTRY()的开头出现过，哈希值就实际的索引号。 然后插入过程自身是依靠ADD_DIRECT执行。从名字就可以看出这是一个宏。 ``` 268 #define ADD_DIRECT(table, key, value, hash_val, bin_pos) \ 269 do { \ 270 st_table_entry *entry; \ 271 if (table->num_entries / (table->num_bins) \ > ST_DEFAULT_MAX_DENSITY) { \ 272 rehash(table); \ 273 bin_pos = hash_val % table->num_bins; \ 274 } \ 275 \ /*（A）*/ \ 276 entry = alloc(st_table_entry); \ 277 \ 278 entry->hash = hash_val; \ 279 entry->key = key; \ 280 entry->record = value; \ /*（B）*/ \ 281 entry->next = table->bins[bin_pos]; \ 282 table->bins[bin_pos] = entry; \ 283 table->num_entries++; \ 284 } while (0) (st.c) ``` 开头的if是例外处理的内容，我们稍后看，首先看下面的。 (A)分配st_table_entry，进行初始化 (B)向链表开头追加entry。这个是处理链表的风格。也就是说通过 ``` entry->next = list_beg; list_beg = entry; ``` 可以向链表的开头追加元素。这也是Lisp的术语"cons"的意思。就算list_beg是NULL，这段代码也是可以通用的。 最后看一下被我们搁置的代码。 ADD_DIRECT()－rehash ``` 271 if (table->num_entries / (table->num_bins) \ > ST_DEFAULT_MAX_DENSITY) { \ 272 rehash(table); \ 273 bin_pos = hash_val % table->num_bins; \ 274 } \ (st.c) ``` DENSITY就是所谓浓度，也就是使用这个条件式判断哈希表是否已经趋于拥挤。st_table中如果所在同一个bin_pos的值过多的话，链表就会变成，搜索速度就会变慢。所以当元素个数过多的时候，我们增加bin的大小来缓解这种拥挤。 现在所设定的ST_DEFAULT_MAX_DENSITY如下 ``` 23 #define ST_DEFAULT_MAX_DENSITY 5 (st.c) ``` 这个浓度被设置成了5，也就是说当所有的bin_pos链表的元素st_table_entry都已经达到5个的情况下，我们就要增大容量。 ####st_insert() st_insert()不过是st_add_direct()和st_lookup()的组合而已。只要了解后两者就ok了。 ``` 286 int 287 st_insert(table, key, value) 288 register st_table *table; 289 register char *key; 290 char *value; 291 { 292 unsigned int hash_val, bin_pos; 293 register st_table_entry *ptr; 294 295 hash_val = do_hash(key, table); 296 FIND_ENTRY(table, ptr, hash_val, bin_pos); 297 298 if (ptr == 0) { 299 ADD_DIRECT(table, key, value, hash_val, bin_pos); 300 return 0; 301 } 302 else { 303 ptr->record = value; 304 return 1; 305 } 306 } (st.c) ``` 首先查询元素是否已经被添加到哈希表中，如果还没有，就向哈希表中添加元素，实际上添加了元素则返回真，如果没有添加就返回假。 ###ID和符号 我们已经说明过ID是什么东西。ID是和任意的字符串一一对应的数值，可以表示各种名称。实际的ID的类型是 unsigned int。 ####从char到ID 字符串到ID的变化通过rb_intern()进行。这个函数略长我们省略其中一部分。 rb_intern()（缩减版） ``` 5451 static st_table *sym_tbl; /* char* → ID */ 5452 static st_table *sym_rev_tbl; /* ID → char* */ 5469 ID 5470 rb_intern(name) 5471 const char *name; 5472 { 5473 const char *m = name; 5474 ID id; 5475 int last; 5476 /* 既にnameに対応するIDが登録されていたらそれを返す */ 5477 if (st_lookup(sym_tbl, name, &id)) 5478 return id; /* 省略……新しいIDを作る */ /* nameとIDの関連を登録する */ 5538 id_regist: 5539 name = strdup(name); 5540 st_add_direct(sym_tbl, name, id); 5541 st_add_direct(sym_rev_tbl, id, name); 5542 return id; 5543 } (parse.y) ``` 字符串和ID的一一对应使用st_table来实现。应该不是什么难点。 要说我们省略了什么，那就是当遇到全局变量或者实例变量的时候我们会进行特殊处理插入标记位。因为ruby的语法解析器需要从ID获取变量的类型。但是这些又和ID的原理没多大联系所以这里就不贴出来了。 ####从ID到char* rb_intern()的逆向，从ID获取char*使用的是rb_id2name()这个函数。大家应该已经明白id2name的2是to的意思。因为to和two发音相同所以被替代使用了。这个写法出乎意料相当常见。 这个函数也是根据ID的种类设立各种flag标记，所以变得很长。我们尽量删掉无关紧要的部分来看这个函数。 rb_id2name(阉割版) ``` char * rb_id2name(id) ID id; { char *name; if (st_lookup(sym_rev_tbl, id, &name)) return name; return 0; } ``` 是不是觉得有些过于简单了。其实只是删除掉了一些小细节。 这里需要注意，我们没有拷贝需要检索的name。Ruby的API的返回值不需要free()(绝对不能free)。另外传递参数的时候通常会通过拷贝来使用。也就是说生成和释放通常是用户或者ruby的一方来执行完成的。(谁生成谁释放) 那么对于生成和释放无法相对应的值(一旦被传递就无法控制)是如何处理的呢？这个时候会要求使用Ruby对象。Ruby对象会在我们不需要的时候自动释放。 ####VALUE和ID的互相转换 ID在Ruby层面上是Symbol类的实例,`"string".intern`会返回对应的ID。这个String#intern的实体就是rb_str_intern()。 ▼rb_str_intern() ``` 2996 static VALUE 2997 rb_str_intern(str) 2998 VALUE str; 2999 { 3000 ID id; 3001 3002 if (!RSTRING(str)->ptr || RSTRING(str)->len == 0) { 3003 rb_raise(rb_eArgError, "interning empty string"); 3004 } 3005 if (strlen(RSTRING(str)->ptr) != RSTRING(str)->len) 3006 rb_raise(rb_eArgError, "string contains `\\0'"); 3007 id = rb_intern(RSTRING(str)->ptr); 3008 return ID2SYM(id); 3009 } (string.c) ``` 这个函数作为ruby的类库的代码例子来说真是信手拈来。注意其中使用RSTRING()强制转换来访问构造体成员的技巧。 读读代码吧。首先rb_raise()只是出错处理所以先无视。这个函数里面有刚才刚解释过的rb_intern(),ID2SYM().ID2SYM()是将ID转换成Symbol的宏。 这个操作的逆向是Symbol#to_s。其实体函数为sym_to_s。 ▼sym_to_s() ``` 522 static VALUE 523 sym_to_s(sym) 524 VALUE sym; 525 { 526 return rb_str_new2(rb_id2name(SYM2ID(sym))); 527 } (object.c) ``` SYM2ID是将Symbol(VALUE)转换成ID的的宏。 看上去很不常见的写法，应该注意的是内存处理相关的地方。rb_id2name()返回一个不允许free()的char*, rb_str_new2()将参数char*拷贝使用(不会改变参数)。因为贯彻了这个方针所以可以写成函数套函数的连锁形式。 (第三章完)