memcached源碼分析-----哈希表基本操作以及擴(kuò)容過程
來源：程序員人生 發(fā)布時間：2015-01-20 08:42:39 閱讀次數(shù)：4360次
轉(zhuǎn)載請注明出處：http://blog.csdn.net/luotuo44/article/details/42773231
溫馨提示：本文用到了1些可以在啟動memcached設(shè)置的全局變量。關(guān)于這些全局變量的含義可以參考《memcached啟動參數(shù)詳解》。對這些全局變量，處理方式就像《如何瀏覽memcached源代碼》所說的那樣直接取其默許值。
assoc.c文件里面的代碼是構(gòu)造1個哈希表。memcached快的1個緣由是使用了哈希表。現(xiàn)在就來看1下memcached是怎樣使用哈希表的。
哈希結(jié)構(gòu)：
main函數(shù)會調(diào)用assoc_init函數(shù)申請并初始化哈希表。為了減少哈希表產(chǎn)生沖突的可能性，memcached的哈希表是比較長的，并且哈希表的長度為2的冪。全局變量hashpower用來記錄2的冪次。main函數(shù)調(diào)用assoc_init函數(shù)時使用全局變量settings.hashpower_init作為參數(shù)，用于指明哈希表初始化時的冪次。settings.hashpower_init可以在啟動memcached的時候設(shè)置，具體可以參考《memcached啟動參數(shù)詳解和關(guān)鍵配置的默許值》。
//memcached.h文件
#define HASHPOWER_DEFAULT 16
//assoc.h文件
unsigned int hashpower = HASHPOWER_DEFAULT;
#define hashsize(n) ((ub4)1<<(n))//這里是1 左移 n次
//hashsize(n)為2的冪，所以hashmask的值的2進(jìn)制情勢就是后面全為1的數(shù)。這就很像位操作里面的 &
//value & hashmask(n)的結(jié)果肯定是比hashsize(n)小的1個數(shù)字.即結(jié)果在hash表里面
//hashmask(n)也能夠稱為哈希掩碼
#define hashmask(n) (hashsize(n)⑴)
//哈希表數(shù)組指針
static item** primary_hashtable = 0;
//默許參數(shù)值為0。本函數(shù)由main函數(shù)調(diào)用，參數(shù)的默許值為0
void assoc_init(const int hashtable_init) {
if (hashtable_init) {
hashpower = hashtable_init;
}
//由于哈希表會漸漸增大，所以要使用動態(tài)內(nèi)存分配。哈希表存儲的數(shù)據(jù)是1個
//指針，這樣更省空間。
//hashsize(hashpower)就是哈希表的長度了
primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
if (! primary_hashtable) {
fprintf(stderr, "Failed to init hashtable.
");
exit(EXIT_FAILURE);//哈希表是memcached工作的基礎(chǔ)，如果失敗只能退出運(yùn)行
}
}
說到哈希表，那末就對應(yīng)有兩個問題，1個是哈希算法，1個怎樣解決沖突。
對哈希函數(shù)(算法)，memcached直接使用開源的MurmurHash3和jenkins_hash兩個中的1個。默許是使用jenkins，可以在啟動memcached的時候設(shè)置設(shè)置為MurmurHash3。memcached是直接把客戶端輸入的鍵值作為哈希算法的輸入，得到1個32位的無符號整型輸出(用變量hv存儲)。由于哈希表的長度沒有2^32- 1這么大，所以需要用到前面代碼中的hashmask宏進(jìn)行截斷。由因而位操作，所以常常能在memcached代碼中看的hv & hashmask(hashpower)。
memcached使用最多見的鏈地址法解決沖突問題。從前面的代碼可以看到，primary_hashtable是1個的2級指針變量，它指向的是1個1維指針數(shù)組，數(shù)組的每個元素指向1條鏈表(鏈表上的item節(jié)點(diǎn)具有相同的哈希值)。數(shù)組的每個元素，在memcached里面也稱為桶(bucket)，所以后文的表述中會使用桶。下圖是1個哈希表，其中第0號桶有2個item，第2、3、5號桶各有1個item。item就是用來存儲用戶數(shù)據(jù)的結(jié)構(gòu)體。
基本操作：
插入item:
接著看1下怎樣在哈希表中插入1個item。它是直接根據(jù)哈希值找到哈希表中的位置(即找到對應(yīng)的桶)，然后使用頭插法插入到桶的沖突鏈中。item結(jié)構(gòu)體有1個專門的h_next指針成員變量用于連接哈希沖突鏈。
static unsigned int hash_items = 0;//hash表中item的個數(shù)
/* Note: this isn't an assoc_update. The key must not already exist to call this */
//hv是這個item鍵值的哈希值
int assoc_insert(item *it, const uint32_t hv) {
unsigned int oldbucket;
//使用頭插法 插入1個item
//第1次看本函數(shù)，直接看else部份
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
...
} else {
//使用頭插法插入哈希表中
it->h_next = primary_hashtable[hv & hashmask(hashpower)];
primary_hashtable[hv & hashmask(hashpower)] = it;
}
hash_items++;//哈希表的item數(shù)量加1
…
return 1;
}
查找item：
往哈希表插入item后，就能夠開始查找item了。下面看1下怎樣在哈希表中查找1個item。item的鍵值hv只能定位到哈希表中的桶位置，但1個桶的沖突鏈上可能有多個item，所以除查找的時候除需要hv外還需要item的鍵值。
