C言語のHashTableを簡単に実現

HashTableは実際の応用において重要な構造であり,以下では簡単な実装について議論するが,その一部はまだある.
一、アクセスインタフェース
hashtableを作成します.
hashtable hashtable_新(int size)/sizeは含む接点個数を表す.
key-valueをhashtableに格納します.
void hashtable_put(hashtable h,const char* key,void *val);
キーに基づいてhashtableからvalue値を取り出します.
void * hashtable_get(hashtable h,const char *key);
hashtableを解放します.
void hashtable_free(hashtable h);
単一hash接点の解放
void hashtable_delete_node(hashtable h, const char *key);
二、データ構造
hash接点の構造:

typedef struct hashnode_struct{
      struct hashnode_struct *next;
      const char *key;
      void *val;
}*hashnode,_hashnode;

この構造は、必要なkey-valueに加えて、競合するためのチェーンテーブル構造を含むことが容易に理解できます.
hashtableのデータ構造:

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

この構成について以下に説明する.
pool_t:メモリプール構造はhashtableが使用するメモリを管理する.構造参照「C言語メモリプール使用モデル」
size:現在のhashの接点空間サイズ.
count:現在の接点空間で使用可能なhash接点の数を表します.
z:接点空間に接点を格納するために使用します.
三、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;
}

この関数は比較的簡単で、まずメモリプールを定義して初期化し、サイズはsizeによって決まるので、実際に使用するときは、私たちのsizeは相対的に大きい点を割り当てるべきで、比較的良いです.
四、key-value値を格納
この操作の前に、KEY値に基づいてhashcodeを計算する関数を定義します.

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 ，    ASCII  hash  
        if ((g = (h & 0xF0000000UL))!=0)     
            h ^= (g >> 24);
        h &= ~g;  //  28-31 。 
    }

    return (int)h;
}

この関数は、エレガントなELF hash関数を使用します.
コードは次のとおりです.

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)  //      ，        ，        。
    {
        n->key = key;
        n->val = val;
        return;
    }

    node = hashnode_node_new(h, index);  //     HASH NODE  。
    node->key = key;
    node->val = val;
}

hashtable_node_getは、KEYがHASHに既に存在するかどうかを検索するために使用され、以下のように簡単に実現される.

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 ]     HASH      
        if(node->key != NULL && (strlen(node->key)==len) && (strncmp(key, node->key, len) == 0))
            return node;
    return NULL;
}

新しいHASH NODE接点は以下の通りである:

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       ，KEY   ，           ，                 。
            return node;

    node = pool_malloc(h->p, sizeof(_hashnode)); //       
    node->next = h->z[i].next;   //      ，            。
    h->z[i].next = node;
    return node;
}

五、HASHTABLEから接点を取得する
KEYに従ってhashtableから接点を取得するには、まずKEYに基づいてhash値を計算し、hashtableから指定した接点または接点チェーンテーブルを見つける.次のようになります.

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をリリース
hashtableの解放は簡単です.私たちのすべてのメモリ申請はメモリプールで完了しているので、メモリプールを解放するだけです.以下のようにします.

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

七、単一hash接点を解放する
コードは次のとおりです.

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)  //      
        return;

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

    h->count--;
}

これは単純なHASHTABLE構造を実現しているが、もちろん後には不足している.例えばHASHTABLEを遍歴し、配列で遍歴すれば効率が低いに違いない.以下、hashtableを遍歴するための実現案を議論する.
八,hashtableの遍歴討論
直接配列を使うとhashtableのstruct hashnode_struct配列は遍歴可能ですが、1つの接点だけが含まれている場合は、次のようにすべての配列を遍歴します.

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  //        。
}

このように効率が低く,実際には接点にnextドメインが含まれており,これを用いて遍歴を実現できる.
前のhashtableデータ構造を簡単に変更し、2つのドメインを追加する必要があります.

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

はbucketとnodeの2つのドメインを追加し、この2つのドメインを追加する考え方です.

nodeは現在の遍歴カーソルを表し、遍歴中にこの接点が指す接点を絶えず移動する.

bucketは、現在のnodeがどのバケツにあるかを記録するためにnodeに関連付けられている.

まず接続を確立することは、すべての接点を接続することであり、慣例に従って、XXX_を採用することである.iter_first関数は、以下のように初期化されます.

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

hashtable_iter_nextは次の接点を取得するために使用され、カーソルが確定した場合、次の接点はすぐに確定され、以下のように定義されます.

int xhash_iter_next(xht h) {
    if(h == NULL) return 0;
    while(h->node != NULL) {
        h->node = h->node->next;   //        ，      ，    
        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;  //         。
    h->node = NULL;
    return 0;
}

上記の2つの方法の後、遍歴操作は以下の通りである.

hashtable ht
if(hashtable_iter_first(ht))   //      。 
do{
    //       ht->node，       。
}while(hashtable_iter_next(ht));  //      

このように処理すると、より効率的になるのではないでしょうか.もちろん1回目では、配列全体と配列の下のバケツの接点を巡る必要があります.しかし、このような操作の後、ノードを削除するときは、いくつかの操作が必要です.1つの接点を削除する場合は、現在のh->nodeが現在削除されている接点であるかどうかを考慮し、もしそうであれば、h->nodeを次の接点と呼ぶ.削除した後、削除した場合は、次のように処理します.
削除された接点がnodeの場合、次の処理が必要です.

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

h->nodeを次の接点に移動します.