count：用于表示當(dāng)前接點(diǎn)空間中可用的hash接點(diǎn)個(gè)數(shù)。

z：用于在接點(diǎn)空間中存儲(chǔ)接點(diǎn)。

三，創(chuàng)建hashtable

代碼如下：

hashtable hashtable_new(int size)
{
    hashtable ht;
    pool_t p;

    p = _pool_new_heap(sizeof(_hashnode)*size + sizeof(_hashtable));
    ht= pool_malloc(p, sizeof(_hashtable));
    ht->size = size;
    ht->p = p;
    ht->z = pool_malloc(p, sizeof(_hashnode)*prime);
    return ht;
}

四，存入key-value值

在這個(gè)操作之前，先要定義一個(gè)根據(jù)KEY值計(jì)算hashcode的函數(shù)。

static int hashcode(const char *s, int len)
{
    const unsigned char *name = (const unsigned char *)s;
    unsigned long h = 0, g;
    int i;

    for(i=0;i<len;i++)
    {
        h = (h << 4) + (unsigned long)(name[i]); //hash左移4位，當(dāng)前字符ASCII存入hash  
        if ((g = (h & 0xF0000000UL))!=0)     
            h ^= (g >> 24);
        h &= ~g;  //清空28-31位。 
    }

    return (int)h;
}

代碼如下：

void hashtable_put(hashtable h, const char *key, void *val)
{
    if(h == NULL || key == NULL) 
	return;

    int len = strlen(key);
    int index = hashcode(key,len);
    hashtable node;
    h->dirty++;

    if((node = hashtable_node_get(h, key,len, index)) != NULL)  //如果已經(jīng)存在，就替換成現(xiàn)在的值，因?yàn)楝F(xiàn)在的比較新。
    {
        n->key = key;
        n->val = val;
        return;
    }

    node = hashnode_node_new(h, index);  // 新建一個(gè)HASH NODE接點(diǎn)。
    node->key = key;
    node->val = val;
}

static hashnode hashtable_node_get(hashtable h, const char *key, int len, int index)
{
    hashnode node;
    int i = index % h->size;
    for(node = &h->z[i]; node != NULL; node = node->next) // 在index值 [HASH值] 所對(duì)應(yīng)的HASH桶上遍歷尋找
        if(node->key != NULL && (strlen(node->key)==len) && (strncmp(key, node->key, len) == 0))
            return node;
    return NULL;
}

static hashnode hashnode_node_new(hashtable h, int index)
{
    hashnode node;
    int i = index % h->size;

    h->count++;

    for(node = &h->z[i]; node != NULL; node = node->next)
        if(node->key == NULL)   //這里的處理是：如果在HASH桶中存在某個(gè)值，KEY是空的，表明這個(gè)值已經(jīng)沒有用了，就用它來替換為現(xiàn)在準(zhǔn)備寫入的新接點(diǎn)。
            return node;

    node = pool_malloc(h->p, sizeof(_hashnode)); // 新建一個(gè)接點(diǎn)
    node->next = h->z[i].next;   // 加入到桶中，就是加到鏈表的第一個(gè)接點(diǎn)。
    h->z[i].next = node;
    return node;
}

根據(jù)KEY從hashtable中獲取接點(diǎn)，步驟是先根據(jù)KEY計(jì)算hash值，然后從hashtable中找到指定的接點(diǎn)或者接點(diǎn)鏈表。如下：

void *hashtable_get(hashtable h, const char *key)
{
    if(h == NULL || key == NULL) 
	return NULL;
    hashnode node;
    int len = strlen(key);
    if(h == NULL || key == NULL || len <= 0 || (node = hashtable_node_get(h, key, len, hashcode(key,len))) == NULL)
    {
        return NULL;
    }
    return node->val;
}

hashtable的釋放就比較簡(jiǎn)單了，因?yàn)槲覀兯械膬?nèi)存申請(qǐng)都在內(nèi)存池上完成的，就只需要釋放內(nèi)存池，如下：

void hashtable_free(hashtable h)
{
    if(h != NULL)
        pool_free(h->p);
}

代碼如下：

void hashtable_delete_node(hashtable h, const char *key)
{
    if(h == NULL || key == NULL) 
	return;
    hashnode node;
    int len = strlen(key);
    if(h == NULL || key == NULL || (node = hashtable_node_get(h, key, len, hashcode(key,len))) == NULL)  //沒有這個(gè)接點(diǎn)
        return;

    node->key = NULL;
    node->val = NULL;

    h->count--;
}

這個(gè)就實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的HASHTABLE結(jié)構(gòu)，當(dāng)然后還是有不足的，比如遍歷HASHTABLE，如果用數(shù)組的方式來遍歷，效率肯定很低，下面討論一種實(shí)現(xiàn)方案，用于遍歷hashtable.

八，hashtable的遍歷討論

 直接用數(shù)組，就是hashtable中的struct hashnode_struct數(shù)組是可以遍歷，但如果只包含一個(gè)接點(diǎn)，也要遍歷所有的數(shù)組，如下遍歷：

void hashtable_traverse(hashtable h)
{
    int i;
    hashnode node;
    if(h == NULL)
        return;
    for(i = 0; i < h->prime; i++)
        for(node = &h->z[i]; node != NULL; node = node->next)
            if(node->key != NULL && node->val != NULL)
                XXXXXXXXXXXXXXXXX  // 這里是一些操作。
}

這樣效率很低，其實(shí)在接點(diǎn)中包含了next域，可以用這個(gè)來實(shí)現(xiàn)遍歷。

需要對(duì)前面hashtable數(shù)據(jù)結(jié)構(gòu)做簡(jiǎn)單的改動(dòng)，增加兩個(gè)域：

typedef struct hashtable_struct{
     pool_t p;
     int size;
     int count;
     struct hashnode_struct *z;
     int bucket;
     hashnode node;
}*hashtable,_hashtable;

1. node表示當(dāng)前遍歷的游標(biāo)，在遍歷過程中，不斷的移動(dòng)這個(gè)接點(diǎn)所指向的接點(diǎn)。
2. bucket是和node相關(guān)聯(lián)的，用于記錄當(dāng)前的node在哪個(gè)桶上。

首先建立連接，就是將所有的接點(diǎn)都連接起來，按照慣例，也采用XXX_iter_first函數(shù)，先初始化，如下：

int hashtable_iter_first(hashtable h) {
    if(h == NULL) 
	return 0;
    h->bucket = -1;
    h->node = NULL;
    return hashtable_iter_next(h);
}

int xhash_iter_next(xht h) {
    if(h == NULL) return 0;
    while(h->node != NULL) {
        h->node = h->node->next;   // 移向下一個(gè)接點(diǎn)，如果接點(diǎn)合法，返回成功
        if(h->node != NULL && h->node->key != NULL && h->node->val != NULL)
            return 1;
    }
    for(h->bucket++; h->bucket < h->prime; h->bucket++) {
        h->node = &h->z[h->bucket];

        while(h->node != NULL) {
            if(h->node->key != NULL && h->node->val != NULL)
                return 1;
            h->node = h->node->next;
        }
    }
    h->bucket = -1;  // 不存在下一個(gè)接點(diǎn)。
    h->node = NULL;
    return 0;
}

hashtable ht
if(hashtable_iter_first(ht))   //取第一個(gè)接點(diǎn)。 
do{
    // 此時(shí)可以處理ht->node，表示當(dāng)前的接點(diǎn)。
}while(hashtable_iter_next(ht));  //取下一個(gè)接點(diǎn)

假如被刪除的接點(diǎn)為node,需要如下處理：

    if(h->node == n)
        hashtable_iter_next(h);