3.2.3表格元素查找
表格元素查找是表格的一個非常重要的功能。目前存在很多的線性表查找算法，最基本的無非三種：順序查找，二分查找以及哈希查找。相對而言，順序查找是最簡單也是最輕易實(shí)現(xiàn)，但是其通常在插入數(shù)據(jù)時候較為快捷，而查找的時候則就相對較慢。二分查找是一個較快的查找方法，但是其前提必須數(shù)據(jù)進(jìn)行排序，因此排序使得插入較慢，因此也不是所有場合均適合。而哈希查找則既實(shí)現(xiàn)簡單，又插入和查找速度較快。因此在Apache中隊(duì)表格的插入和查找則采取了哈希算法。
Apache中在表格中查找一個鍵值為key的元素的函數(shù)為a
PR_table_get，其定義如下：
APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_uint32_t checksum;
int hash;
if (key == NULL) {
return NULL;
}
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
return NULL;
}
COMPUTE_KEY_CHECKSUM(key, checksum);
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
return next_elt->val;
}
}
return NULL;
}
正如前面的apr_table_entry_t中看到的，對于表格中的每一個元素我們都維護(hù)一個key成員，為字符指針變量，該key用來標(biāo)識該元素，在Apache中由于答應(yīng)重復(fù)key的存在，因此在表格中可能存在多個key相同的元素，不過apr_table_get函數(shù)只返回查找到的第一個符合要求的元素。
對于任何一個鍵值，我們可以通過TABLE_HASH(key)找到對應(yīng)元素在表格中存放的索引。 TABLE_HASH為一個宏，定義為(TABLE_INDEX_MASK & *(unsigned char *)(key))。一旦得到哈希索引hash，函數(shù)將判定該索引所定應(yīng)的內(nèi)存塊是否已經(jīng)被初始化。假如該索引塊還沒有初始化，則理所當(dāng)然，里面什么都沒有，也就沒法取了，此時直接返回NULL。
當(dāng)然假如內(nèi)存中確實(shí)有“貨”可用，則函數(shù)將進(jìn)一步調(diào)用宏COMPUTE_KEY_CHECKSUM(key, checksum)來計(jì)算鍵值key所對應(yīng)的校驗(yàn)值，校驗(yàn)結(jié)果即為checksum，該checksum主要作為宏TABLE_HASH的參數(shù)。
現(xiàn)在我們再往返顧前面提到的apr_table_t中的剩余的兩個輔助成員變量：
int index_first[TABLE_HASH_SIZE];
int index_last[TABLE_HASH_SIZE];
前面我們提到這二個輔助成員主要用在加速對表格中成員的查找，那么我們現(xiàn)在看看這兩個成員變量是如何實(shí)現(xiàn)查找加速的。
我們首先來看宏TABLE_HASH(key)的實(shí)現(xiàn)：
#define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key))
從上面的哈希值得計(jì)算中可以看出，不管對于任何一個鍵值key，只有該鍵值的第一個字母參與了運(yùn)算，因此比如對于“hello”和“house”而言，其計(jì)算出來的結(jié)果都是8。我們將整個表格分為多個“類別”，這些類別通過TABLE_HASH(key)進(jìn)行區(qū)分，實(shí)際上也就是按照key的第一個字母進(jìn)行分類。因此“hello”和“house”屬于同一個類，而和“cat”則屬于不同的類別。Apache中對鍵值的查找是基于類別進(jìn)行的。假如一個類別在表格中具有多個元素，那么毫無疑問，肯定就發(fā)生了哈希沖突。
為了解決索引沖突的問題，apr_table_t中引入index_first和index_last數(shù)組，分別記錄給定的類別在表格中的起始索引和終止索引。對于某個類別，比如“h”類別(所有的以h開始的鍵值都屬于這個類)，它在index_first和index_last中的索引可以通過TABLE_HASH(key)計(jì)算得到，結(jié)果為8。因此整個表格中第一個h類元素在表格中的索引保存在index_first[8](即index_first[TABLE_HASH(key)]中，而最后一個h類的成員的索引則保存在index_last[8]中。同理假如對于“c”類別，它的TABLE_HASH(key)為3，因此整個表格的第一個c類元素的索引則保存在index_first[3]中，最后一個在保存在index_last[3]中。
比如，目前在表格中僅存在三個鍵值以字母h開頭，分別為“house”、“hello”、“horse”，它們在表格中的索引分別為7、9、12，同時還存在四個以c開始的鍵值，分別是“cat”、“copy”、“catch”、“cite”，它們在表格中的索引分別為5、6、8、10。對于h類而言，它們對應(yīng)的index_first中的索引為8，值為7，意味著所有的以h開始的鍵值第一次出現(xiàn)是在表格的索引為7的位置，同樣從上表可以看出，所有以c開始的鍵值第一次出現(xiàn)是在表格的索引為5的位置。同樣對于h類而言，它們對應(yīng)的index_last中的索引也是8，值為12，意味著表格中最后一個以h開始的鍵值在表格中的索引為12，同時，表格中的最后一個以c起始的鍵值的索引是10。
假如現(xiàn)在需要查找”hello”，經(jīng)過COMPUTE_KEY_CHECKSUM(key, checksum)計(jì)算后，它的checksum為8。因此函數(shù)此時將檢查index_first[8]和index_last[8]中的數(shù)據(jù)，如圖，分別為7和11。這意味著所有的以’h’開始的鍵值都在表格的第 7和第11之間，因此此時只需要搜索索引從7到11的元素就可以了。
一旦明確index_first和index_last數(shù)組的用途，我們就可以使用這兩個數(shù)組加快搜索速度。比如假如需要搜索“hello”，我們不再需要從第一個元素查找到最后一個元素，相反，我們僅僅需要搜索表格中索引位于index_first[TABLE_HASH(“hello”)]和index_last[TABLE_HASH(“hello”)]之間的元素，即表格中第7個和第12個之間的元素。通過這種策略，可以大大縮小查詢的范圍。對于縮小范圍之內(nèi)的查找，我們則使用普通的查找方法，逐一比較。
上述算法的實(shí)現(xiàn)代碼如下：
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
for (; next_elt <= end_elt; next_elt++)
{
if ((checksum == next_elt->key_checksum) &&!strcasecmp(next_elt->key, key))
{
return next_elt->val;
}
}
在進(jìn)行比較的時候，上面的代碼采取了一定的變通。正常情況下，將需要查詢的鍵值與查詢范圍內(nèi)的每一個字符串鍵值進(jìn)行比較的時候可以調(diào)用strcmp實(shí)現(xiàn)，對于Apache而言則就是strcasecmp。為了能夠加快查找的速度，Apache中對于每一個字符串，取其前面的4個字符計(jì)算該字符串的校驗(yàn)碼：
#define COMPUTE_KEY_CHECKSUM(key, checksum) /
{ /
const char *k = (key); /
apr_uint32_t c = (apr_uint32_t)*k; /
(checksum) = c; /
(checksum) <<= 8; /
if (c) { /
c = (apr_uint32_t)*++k; /
checksum = c; /
} /
(checksum) <<= 8; /
if (c) { /
c = (apr_uint32_t)*++k; /
checksum = c; /
} /
(checksum) <<= 8; /
if (c) { /
c = (apr_uint32_t)*++k; /
checksum = c; /
} /
checksum &= CASE_MASK; /
}
宏COMPUTE_KEY_CHECKSUM計(jì)算給定key的校驗(yàn)碼checksum，因此對于任何的字符串比較都會分為兩個步驟：
checksum == next_elt->key_checksum) &&!strcasecmp(next_elt->key, key
首先比較它們的校驗(yàn)碼，即前四個字符，假如相等，才會進(jìn)一步調(diào)用strcasecmp進(jìn)行比較；假如校驗(yàn)整數(shù)值不相等，那么就沒有必要調(diào)用strcasecmp進(jìn)一步比較。由于整數(shù)之間的比較速度比較快，因此通過這種兩階段比較能夠有效的提高比較速度。
關(guān)于作者
張中慶，目前主要的研究方向是嵌入式瀏覽器，移動中間件以及大規(guī)模服務(wù)器設(shè)計(jì)。目前正在進(jìn)行Apache的源代碼分析，計(jì)劃出版《Apache源代碼全景分析》上下冊。Apache系列文章為本書的草案部分，對Apache感愛好的朋友可以通過flydish1234 at sina.com.cn與之聯(lián)系!
假如你覺得本文不錯，請點(diǎn)擊文后的“推薦本文”鏈接！！
