本文剖析hash.h/c，從源代碼來剖析eSNACC哈希結構的設計和實現。
為什么要在這里剖析hash呢？一個順理成章的理由是：我們準備剖析eSNACC對ANY(s)類型的編碼和解碼，可是ANY的實現依賴于hash，所以我們就需要先把這條路打通了。O(∩_∩)O哈哈~是不是很有說服力呀？
好，閑話少述，言規(guī)正傳。我們知道hash對一個系統(tǒng)而言，一般都是一個很有價值的底層基礎設施。從作用上來說，他實現的優(yōu)劣極大的影響著整個系統(tǒng)的性能。從技術上來說，也是很能體現含金量的一個模塊。所以，對eSNACC實現的這個寶藏，我們下定決心要刨根問底、直搗黃龍！
友情說明：本文不討論eSNACC用的hash函數，因為我們用了另外獨立的一篇文章來研究：剖析eSNACC的hash函數。本文研究的是eSNACC哈希結構的設計和實現。
先看頭文件：
#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 */在這里，就利用這個頭文件，我想先和大家講清楚eSNACC的hash表的設計結構。
首先，eSNACC的每一個hash值用unsigned int來定義：typedef unsigned int Hash。
然后，定義的hash表結構——Table：typedef void *Table[TABLESIZE]，是一個256維的指針數組。
那這個數組每個元素的內容是什么呢？是指向HashSlot結構的指針，也就是這個hash表的每一維是一個HashSlot。但是如果這樣，只能存放256個值呀，怎樣實現hash的呢？這個我們就要理解HashSlot的各個變量的意義了：
int leaf : 當前HashSlot是不是樹的葉子。
Hash hash ：當前HashSlot元素的hash值。
void *value ：對應當前hash值元素內容，也就是實際值。
Table *table ：如果當前HashSlot不是葉子，也就是說在當前hash有多個共用的元素，那么本字段就不為空，而是指向再次hash的表。
我做了一張簡單的示意圖來描述：
雖然不美觀，但還是希望你能從中看明白這個hash表的結構哦。
/******************************休息一下************************************
好了，有了對整個hash表設計的理解，我們就來研究具體的hash表操作函數
/**//* 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;
}
上面三個很簡單，前兩個調用new創(chuàng)建HashSlot和Table,第三個就是用來初始最上層hash表的函數。
下面我們來看看將一個hash值為hash_value的元素element插入到哈希表table的具體實現：
/**//* 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);
}
函數利用hash_value的最后一個字節(jié)來判斷該元素應該放在table中的維數，并且取出該維對應的HashSlot entry。
如果entry為空，那么也就是對應該hash_value還沒有元素，可以直接創(chuàng)建HashSlot，設定entry的value為element,hash為hash_value，因為當前只有這一個值，所以本HashSlot就是葉子，其table成員也為空。然后將該新的entry連到table的對應維上，完成。
如果entry不為空，依次判斷以下三種情況：
1、如果當前entry的hash等于hash_value，那就是hash值沖突，直接返回false。
2、如果當前entry是葉子，那么就得拆分當前HashSlot，使得他用table來存放多個值。
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分配一個Table，接著再將entry中原來存的值(entry->vlaue,entry->hash)插到表里，然后還將新加入的值(element,hash_value)插入表里。最后將entry的葉子屬性改為非葉子。
注意：在級聯的hash表里存的不是原來的hash值，而是依次將hash>>8.也就是出了最高層的哈希表，其他的都依次去掉最末尾的一個字節(jié)！！！
我們模擬插入兩個元素，假設其值和hash分別為A("tim",0xAA02),B("eSNACC",0xBB02).只是為了說明，我們假設原始table為空：
1，插入A:hash_value=0xAA02，所以應當插入到table的第三維，插入以后應當為：
2.插入B：hash_value=0xBB02，hash_value & 0xFF=2，所以又找到第三位，然后此時有HashSlot葉子，所以需要拆分，在插入后應當為：
利用這兩個圖，應該說得很清楚了吧，還是圖最清楚了！O(∩_∩)O哈哈~
好了，讓我們來看最后兩個函數：
/**//* 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;
}
這兩個函數功能很清晰，就是在給定的哈希表table查找對應哈希值為hash的元素。只是CheckFor只是檢查table存在此hash否。而CheckForAndReturnValue則在存在時，將元素值存在value中返回。
好了，到此，eSNACC哈希結構的設計就已經全部分析完成了！祝大家學習愉快~