程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一個簡單的HashMap C語言實現

一個簡單的HashMap C語言實現

編輯:關於C語言

用C語言實現一個簡單實用的hashmap,具有一定的實際意義。尤其我們不想使用STL裡面的map<...>類的時候。我實現的這個hashmap,用來做key---value的映射,key必須是有效的字符串,value是調用者分配的任意類型的數據。這個hashmap適合在一些簡單的場合下,消耗極少的資源。

首先定義頭文件如下:

/*
 * hashmap.h
 *        Generic hash map: key(string)-value(any type).
 *        cheungmine
 *      Sep. 22, 2007.  All rights reserved.
 */
#ifndef HASHMAP_H_INCLUDED
#define HASHMAP_H_INCLUDED

#include "unistd.h"

/* You should always use 1024 */
#define     HASHMAP_SIZE    1024

/* Opaque struct pointer to _hash_map_t */
typedef struct    _hash_map_t*        hash_map;

typedef void(*pfcb_hmap_value_free)(void* value);

/* An example of free value function implemented by caller:
void my_hmap_free_value(void* pv)
{
    free(pv);
}
*/


/* Create before use. eg:
 * hash_map  hm;
 * hmap_create (&hm, HASHMAP_SIZE);
 * assert (hm);     // out of memory if hm==NULL
 * void* mydata=malloc(n);
 * hmap_insert(hm, "shanghai", -1, mydata);
   ...
 * hmap_destroy(hm, my_hmap_free_value);
 */
extern void
hmap_create(hash_map *hmap, int size);

/* Destroy after use */
extern void
hmap_destroy(hash_map hmap, pfcb_hmap_value_free);

/* Insert a key-value into hash map. value is a pointer to callee-allocated memory */
extern void
hmap_insert(hash_map hmap, const char* key, int key_len/* -1 for strlen to be called */, void* value);

/* Search a hash map for value of given key string */
extern void*
hmap_search(hash_map hmap, const char  *key);


#endif  /* HASHMAP_H_INCLUDED */

實現文件如下:

/*
 * hashmap.c
 *        Generic hashmap implementation.
 *      a map for pair of key-value. key must be a null-end string, value is any type of data.
 *        cheungmine
 *      Sep. 22, 2007.  All rights reserved.
 */

#include "hashmap.h"
#include "list.h"

typedef struct _hash_map_t
{
    size_t            size;
    listnode_t**    key;
    listnode_t**    value;
}hash_map_t;

/* Hash a string, return a hash key */
static ulong  hash_string(const char  *s, int len)
{
    ulong h = 0;
    int   i = 0;
    assert (s);
    if (len < 0)
        len = (s? (int)strlen(s): 0);
    while(i++ < len) { h = 17*h + *s++; }
    return h;
}

static void _free_map_key(listnode_t* node)
{
    listnode_t    *old;
    while(node)
    {       
        old = node;
        node = node->next;

        free(old->data);
        free (old);
    }
}

static void _free_map_value(listnode_t* node, pfcb_hmap_value_free pfunc)
{
    listnode_t    *old;
    while(node)
    {       
        old = node;
        node = node->next;

        if (pfunc)
            (*pfunc)(old->data);
        free (old);
    }
}

/*=============================================================================
                            Public Functions
=============================================================================*/
/* Create before use */
void
hmap_create(hash_map *hmap, int size)
{
    (*hmap) = (hash_map_t*) malloc(sizeof(hash_map_t));
    (*hmap)->size = size;
    (*hmap)->key = (listnode_t**) calloc(size, sizeof(listnode_t*));
    (*hmap)->value = (listnode_t**) calloc(size, sizeof(listnode_t*));
}

/* Destroy after use */
extern void
hmap_destroy(hash_map hmap, pfcb_hmap_value_free pfunc)
{
    size_t i;
    for(i=0; i<hmap->size; i++){
        _free_map_key(hmap->key[i]);
        _free_map_value(hmap->value[i], pfunc);
    }

    free(hmap->key);
    free(hmap->value);
    free(hmap);
}


/* Insert a key-value into hash map. value is a pointer to callee-allocated memory */
void
hmap_insert(hash_map hmap, const char* key, int key_len, void* value)
{
    listnode_t    *node_key, *node_val;
    ulong        h;
    char        *s;
    assert (key);

    if (key_len<0) key_len = (int) strlen (key);
    s = (char*) malloc (key_len+1);
    assert(s);

#pragma warning(push)    /* C4996 */
#pragma warning( disable : 4996 )
    strncpy (s, key, key_len);
#pragma warning(pop)    /* C4996 */
    s[key_len] = 0;

    node_key = list_node_create ( (void*)s );
    node_val = list_node_create ( value );
    assert(node_key && node_val);

    h = hash_string (s, key_len) % hmap->size;

    node_key->next = hmap->key[h];
    hmap->key[h] = node_key;

    node_val->next = hmap->value[h];
    hmap->value[h] = node_val;
}

/* Search a hash map for value of given key string */
void*
hmap_search(hash_map hmap, const char *key)
{
    ulong        h    = hash_string (key, -1) % hmap->size;
    listnode_t  *pk = hmap->key[h];
    listnode_t  *pv = hmap->value[h];

    while (pk)
    {
        if (strcmp(key, pk->str) == 0)
            return pv->data;
        pk = pk->next;
        pv = pv->next;
    }

    return NULL;
}

好了,其中用到的其他文件(unistd.h,list.h,list.c)看我下一篇文章!

C語言實現一個簡單的單向鏈表list

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved