読者です 読者をやめる 読者になる 読者になる

Cでハッシュテーブルを使うときのメモ

C

Cでハッシュテーブルを使いたくなったので、調べてみたら APR(Apache Portability Runtime) のハッシュテーブルのパフォーマンスが良いらしい。名前的に移植性も良さそうな気がする。
簡単な使い方を兼ねたサンプルをメモがわりに残す。プラットフォームはCentOS5.2。

#include <stdio.h>
#include <string.h>
#include <apr_hash.h>

#define MAX_KEY_LENGTH 512
#define MAX_VAL_LENGTH 512

static apr_pool_t* pool;
static apr_hash_t* hash;

main(){
  //おまじない
  apr_initialize();
  apr_pool_create(&pool, NULL);
  hash = apr_hash_make(pool);

  //ハッシュに値をセット
  char *key, *val;
  int i;
  for(i=0; i<20; i++){
	key = apr_palloc(pool, MAX_KEY_LENGTH);
	val = apr_palloc(pool, MAX_VAL_LENGTH);
	sprintf(key, "KEY_%d", i);
	sprintf(val, "VAL_%d", i);
	apr_hash_set(hash, key, APR_HASH_KEY_STRING, val);
  }

  //キーを指定して値を取り出す
  val = apr_hash_get(hash, key, APR_HASH_KEY_STRING);
  printf("key=%s, val=%s\n\n", key,val);

  //ハッシュに入っているキーと値をすべて取り出す
  apr_hash_index_t *hi;
  apr_ssize_t klen;
  for( hi=apr_hash_first(pool, hash); hi; hi=apr_hash_next(hi) ){
	apr_hash_this(hi, (const void **)&key, &klen,(void **)&val);
	printf("key=%s, val=%s,  key_length=%d\n", key,val,(int)klen);
  }
}
# gcc -g -I /usr/include/apr-1 -L/usr/lib/apr-1 -lapr-1 my_hash.c -o my_hash
  • 実行
# ./my_hash
key=KEY_19, val=VAL_19

key=KEY_8, val=VAL_8,  key_length=5
key=KEY_9, val=VAL_9,  key_length=5
key=KEY_10, val=VAL_10,  key_length=6
key=KEY_11, val=VAL_11,  key_length=6
key=KEY_12, val=VAL_12,  key_length=6
key=KEY_13, val=VAL_13,  key_length=6
key=KEY_14, val=VAL_14,  key_length=6
key=KEY_15, val=VAL_15,  key_length=6
key=KEY_16, val=VAL_16,  key_length=6
key=KEY_17, val=VAL_17,  key_length=6
key=KEY_18, val=VAL_18,  key_length=6
key=KEY_19, val=VAL_19,  key_length=6
key=KEY_0, val=VAL_0,  key_length=5
key=KEY_1, val=VAL_1,  key_length=5
key=KEY_2, val=VAL_2,  key_length=5
key=KEY_3, val=VAL_3,  key_length=5
key=KEY_4, val=VAL_4,  key_length=5
key=KEY_5, val=VAL_5,  key_length=5
key=KEY_6, val=VAL_6,  key_length=5
key=KEY_7, val=VAL_7,  key_length=5

意外と簡単。

追加でglibc版も試した。どうやらiteration の機能が無いみたいなので注意が必要。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#define __USE_GNU
#include <search.h>

#define MAX_KEY_LENGTH 512
#define MAX_VAL_LENGTH 512

main(void) {
  int ret;
  struct hsearch_data tab;
  
  /* おまじない */
  memset(&tab, 0, sizeof(tab));
  ret = hcreate_r(512, &tab);
  
  ENTRY e;
  ENTRY* search_result;

  /* ハッシュに値をセット */
  int i;
  for(i=0; i < 20; i++) {
	e.key = (char*)malloc(MAX_KEY_LENGTH);
	e.data = (char*)malloc(MAX_VAL_LENGTH);
	sprintf(e.key, "KEY_%d", i);
	sprintf(e.data, "VAL_%d", i);
    ret = hsearch_r(e, ENTER, &search_result, &tab);
  }

  /* キーを指定して値を取り出す */
  ret = hsearch_r(e, FIND, &search_result, &tab);
  printf("key=%s, val=%s\n", search_result->key, search_result->data);

  /* 全データを取り出す  */

  /* 全データをfree  */
  
}


参考
C/C++ で使える Hashtable - BOOLEANLABEL
hcreate_rなどを使ってみた - Limitの日記