##第三章 名稱和命名表 ####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*拷貝使用(不會改變參數)。因為貫徹了這個方針所以可以寫成函數套函數的連鎖形式。 (第三章完)