本文剖析hash.h/c，從源代碼來(lái)剖析eSNACC哈希結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)。
為什么要在這里剖析hash呢？一個(gè)順理成章的理由是：我們準(zhǔn)備剖析eSNACC對(duì)ANY(s)類型的編碼和解碼，可是ANY的實(shí)現(xiàn)依賴于hash，所以我們就需要先把這條路打通了。O(∩_∩)O哈哈~是不是很有說(shuō)服力呀？
好，閑話少述，言規(guī)正傳。我們知道hash對(duì)一個(gè)系統(tǒng)而言，一般都是一個(gè)很有價(jià)值的底層基礎(chǔ)設(shè)施。從作用上來(lái)說(shuō)，他實(shí)現(xiàn)的優(yōu)劣極大的影響著整個(gè)系統(tǒng)的性能。從技術(shù)上來(lái)說(shuō)，也是很能體現(xiàn)含金量的一個(gè)模塊。所以，對(duì)eSNACC實(shí)現(xiàn)的這個(gè)寶藏，我們下定決心要刨根問(wèn)底、直搗黃龍！
友情說(shuō)明：本文不討論eSNACC用的hash函數(shù)，因?yàn)槲覀冇昧肆硗猹?dú)立的一篇文章來(lái)研究：剖析eSNACC的hash函數(shù)。本文研究的是eSNACC哈希結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)。
先看頭文件：
#ifndef _asn_hash_h_
#define _asn_hash_h_
#ifdef __cplusplus
extern "C" 
{
#endif
#define TABLESIZE 256
#define INDEXMASK 0xFF
#define INDEXSHIFT 8
typedef void *Table[TABLESIZE];
typedef unsigned int Hash;
typedef struct HashSlot
{
int leaf;
Hash hash;
void *value;
Table *table;
} HashSlot;
Hash MakeHash PROTO ((char *str, unsigned long len));
Table *InitHash();
int Insert PROTO ((Table *table, void *element, Hash hash));
int CheckFor PROTO ((Table *table, Hash hash));
int CheckForAndReturnValue PROTO ((Table *table, Hash hash, void **value));
#ifdef __cplusplus
}
#endif
#endif /* conditional include */在這里，就利用這個(gè)頭文件，我想先和大家講清楚eSNACC的hash表的設(shè)計(jì)結(jié)構(gòu)。
首先，eSNACC的每一個(gè)hash值用unsigned int來(lái)定義：typedef unsigned int Hash。
然后，定義的hash表結(jié)構(gòu)——Table：typedef void *Table[TABLESIZE]，是一個(gè)256維的指針數(shù)組。
那這個(gè)數(shù)組每個(gè)元素的內(nèi)容是什么呢？是指向HashSlot結(jié)構(gòu)的指針，也就是這個(gè)hash表的每一維是一個(gè)HashSlot。但是如果這樣，只能存放256個(gè)值呀，怎樣實(shí)現(xiàn)hash的呢？這個(gè)我們就要理解HashSlot的各個(gè)變量的意義了：
int leaf : 當(dāng)前HashSlot是不是樹(shù)的葉子。
Hash hash ：當(dāng)前HashSlot元素的hash值。
void *value ：對(duì)應(yīng)當(dāng)前hash值元素內(nèi)容，也就是實(shí)際值。
Table *table ：如果當(dāng)前HashSlot不是葉子，也就是說(shuō)在當(dāng)前hash有多個(gè)共用的元素，那么本字段就不為空，而是指向再次hash的表。
我做了一張簡(jiǎn)單的示意圖來(lái)描述：
雖然不美觀，但還是希望你能從中看明白這個(gè)hash表的結(jié)構(gòu)哦。
/******************************休息一下************************************
好了，有了對(duì)整個(gè)hash表設(shè)計(jì)的理解，我們就來(lái)研究具體的hash表操作函數(shù)
/**//* Creates and clears a new hash slot */
static HashSlot * NewHashSlot()
{
HashSlot *foo;
foo = new HashSlot;
if (foo == NULL)
return NULL;
memset (foo, 0, sizeof (HashSlot));
return foo;
}
/**//* Create a new cleared hash table */
static Table *NewTable()
{
Table *new_table;
// new_table = new Table;
// whose bug is it that gcc won't compile the above line?
new_table = (Table *) new Table;
if (new_table == NULL)
return NULL;
memset (new_table, 0, sizeof (Table));
return new_table;
}
/**//* This routine is used to initialize the hash tables. When it is called
* it returns a value which is used to identify which hash table
* a particular request is to operate on.
*/
Table * InitHash()
{
Table *table;
table = NewTable();
if (table == NULL)
return 0;
else
return table;
}
上面三個(gè)很簡(jiǎn)單，前兩個(gè)調(diào)用new創(chuàng)建HashSlot和Table,第三個(gè)就是用來(lái)初始最上層hash表的函數(shù)。
下面我們來(lái)看看將一個(gè)hash值為hash_value的元素element插入到哈希表table的具體實(shí)現(xiàn)：
/**//* This routine takes a hash table identifier, an element (value) and the
* coresponding hash value for that element and enters it into the table
* assuming it isn't already there.
*/
int Insert (Table *table, void *element, Hash hash_value)
{
HashSlot *entry;
entry = (HashSlot *) (*table)[hash_value & INDEXMASK];
if (entry == NULL) {
/**//* Need to add this element here */
entry = NewHashSlot();
if (entry == NULL)
return false;
entry->leaf = true;
entry->value = element;
entry->hash = hash_value;
(*table)[hash_value & INDEXMASK] = entry;
return true;
}
if (hash_value == entry->hash)
return false;
if (entry->leaf)
return SplitAndInsert (entry, element, hash_value);
return Insert (entry->table, element, hash_value >> INDEXSHIFT);
}
函數(shù)利用hash_value的最后一個(gè)字節(jié)來(lái)判斷該元素應(yīng)該放在table中的維數(shù)，并且取出該維對(duì)應(yīng)的HashSlot entry。
如果entry為空，那么也就是對(duì)應(yīng)該hash_value還沒(méi)有元素，可以直接創(chuàng)建HashSlot，設(shè)定entry的value為element,hash為hash_value，因?yàn)楫?dāng)前只有這一個(gè)值，所以本HashSlot就是葉子，其table成員也為空。然后將該新的entry連到table的對(duì)應(yīng)維上，完成。
如果entry不為空，依次判斷以下三種情況：
1、如果當(dāng)前entry的hash等于hash_value，那就是hash值沖突，直接返回false。
2、如果當(dāng)前entry是葉子，那么就得拆分當(dāng)前HashSlot，使得他用table來(lái)存放多個(gè)值。
3、如果entry不是葉子了，那么就將本元素插到entry->table里面。
我們看一下SplitAndInsert：
/**//* When a hash collision occurs at a leaf slot this routine is called to
* split the entry and add a new level to the tree at this point.
*/
static int SplitAndInsert (HashSlot *entry, void *element, Hash hash_value)
{
if (((entry->table = NewTable()) == NULL) ||
!Insert (entry->table, entry->value, entry->hash >> INDEXSHIFT) ||
!Insert (entry->table, element, hash_value >> INDEXSHIFT))
return false;
entry->leaf = false;
return true;
}
恩，很清楚，首先為entry的table分配一個(gè)Table，接著再將entry中原來(lái)存的值(entry->vlaue,entry->hash)插到表里，然后還將新加入的值(element,hash_value)插入表里。最后將entry的葉子屬性改為非葉子。
注意：在級(jí)聯(lián)的hash表里存的不是原來(lái)的hash值，而是依次將hash>>8.也就是出了最高層的哈希表，其他的都依次去掉最末尾的一個(gè)字節(jié)?。?！
我們模擬插入兩個(gè)元素，假設(shè)其值和hash分別為A("tim",0xAA02),B("eSNACC",0xBB02).只是為了說(shuō)明，我們假設(shè)原始table為空：
1，插入A:hash_value=0xAA02，所以應(yīng)當(dāng)插入到table的第三維，插入以后應(yīng)當(dāng)為：
2.插入B：hash_value=0xBB02，hash_value & 0xFF=2，所以又找到第三位，然后此時(shí)有HashSlot葉子，所以需要拆分，在插入后應(yīng)當(dāng)為：
利用這兩個(gè)圖，應(yīng)該說(shuō)得很清楚了吧，還是圖最清楚了！O(∩_∩)O哈哈~
好了，讓我們來(lái)看最后兩個(gè)函數(shù)：
/**//* This routine looks to see if a particular hash value is already stored in
* the table. It returns true if it is and false otherwise.
*/
int CheckFor (Table *table, Hash hash)
{
HashSlot *entry;
entry = (HashSlot *) table[hash & INDEXMASK];
if (entry == NULL)
return false;
if (entry->leaf)
return entry->hash == hash;
return CheckFor (entry->table, hash >> INDEXSHIFT);
}
/**//* In addition to checking for a hash value in the tree this function also
* returns the coresponding element value into the space pointed to by
* the value parameter. If the hash value isn't found false is returned
* the the space pointed to by value is not changed.
*/
int CheckForAndReturnValue (Table *table, Hash hash, void **value)
{
HashSlot *entry;
if (table)
{
entry = (HashSlot *) (*table)[hash & INDEXMASK];
if (entry == NULL)
return false;
if (entry->leaf)
{
if (entry->hash == hash)
{
*value = entry->value;
return true;
}
else
return false;
}
return CheckForAndReturnValue (entry->table, hash >> INDEXSHIFT, value);
}
else
return false;
}
這兩個(gè)函數(shù)功能很清晰，就是在給定的哈希表table查找對(duì)應(yīng)哈希值為hash的元素。只是CheckFor只是檢查table存在此hash否。而CheckForAndReturnValue則在存在時(shí)，將元素值存在value中返回。
好了，到此，eSNACC哈希結(jié)構(gòu)的設(shè)計(jì)就已經(jīng)全部分析完成了！祝大家學(xué)習(xí)愉快~