LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@taqu

C言語でハッシュテーブル

Last updated at Posted at 2022-09-25

はじめに

C言語でハッシュテーブルが欲しくなったため, 最速のハッシュテーブルを求めてを再考しながら実装してみます.
やはり書いておく, ハッシュテーブル, ハッシュマップ, 連想配列は万能のデータ構造ではない.
最速のハッシュテーブルを求めてのときは, ハッシュ関数はFNVのような品質のよくないものを想定していました. Designing a fast Hash Tableのように, ハッシュ関数の品質が良いものと仮定するともっと小さい実装ができるのでは？, という方針で実装しました.

ハッシュテーブルの実装においての方針は次のようにしました.

  • ハッシュ値の衝突時は線形探索
    • 値を入れる場所がすでに埋まっていた場合は, 空きを線形探索します. ハッシュ関数の品質が良いのでこのようなことはほとんど起きません.
  • 容量の拡張は70%以上埋まった場合に行う
  • 容量は2の冪乗
    • 素数のほうがハッシュ値の全ビット情報を使い切ることができるといわれますが, ハッシュ関数の品質が良いので検索時の剰余計算の高速化のために2の冪乗を選択します.
    • キーに対する値を保存する場所として, （ハッシュ値/容量）の余りを計算するわけですが, 約分できてしまうとテーブルの前半部分に偏るため素数を容量に選択するという理屈です.
  • ハッシュ値のキャッシュ
    • ハッシュ値の31ビットをキャッシュし, 検索やリサイズ時に再利用します. 値が存在するかどうかのフラグを最上位ビットに, 残りをハッシュ値のキャッシュにします.

ハッシュ関数

SMHasherで品質が良い結果になっているものならどれでもいいと思います. hash floodingについては外部にさらされていない用途しか考えていないので考慮しません.
wyhashやkomihashなどの品質が良くコンパクトな実装を選択してみるといいと思います.

SMHasherへの組み込み

SMHasherへ自作のハッシュ関数を組み込む場合, main.cppのg_hashesにテスト関数を追加します.

HashInfo g_hashes[] =
{
...
  { myhash_test, 64, 0, "myhash", "myhash 64-bit", GOOD, {}},
};

テスト関数は次のようなインターフェイスで, Hashes.cppなどに追加します.

void myhash_test(const void *key, int len, uint32_t seed, void *out) {
  *(uint64_t*)out = myhash64(len, key, seed);
}

実装

特殊なことは全くしていないので, 書くことがないのですが, 最近仕事でとんでもないコードに出会ったため, インターフェイスは一点こだわりました.

C++のマップなどのoperator[]は存在しないキーが渡された場合に例外を投げる仕様です. コンパイラで強制的に例外が無効にされている場合は未定義動作と思います（調べていない）. operator[]は存在確認には使いにくいですし, 実際使い道がないと思います.

sm_try_getはC#などにみられるインターフェイスですが, 誰でも間違いなく使えるという意味ではこちらの方が優れていると思います. ハッシュ値を何回も計算する必要もないので効率的でもあります. SMHasherを眺めてもらえればわかりますが, 品質のよいハッシュ値を計算するにはそれなりの計算時間が必要です.

インターフェイスの一部
#ifndef INC_SMALLMAP_H_
#define INC_SMALLMAP_H_
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>

struct smallmap_t;
typedef struct smallmap_t smallmap;
#define SM_INVALID (0xFFFFFFFFUL) //!< Invalid ID

/**
 * @brief construct a map context
 * @param [in] key_size ... size of key in bytes
 * @param [in] value_size ... size of value in bytes
 * @param [in] key_constructor ...
 * @param [in] key_move ...
 * @param [in] key_destructor ...
 * @param [in] value_constructor ...
 * @param [in] value_move ...
 * @param [in] value_destructor ...
 * @param [in] hasher ...
 * @param [in] compare ...
 * @param [in] allocate ...
 * @param [in] deallocate ...
 */
smallmap* sm_construct(
        uint32_t key_size,
        uint32_t value_size,
        bool (*key_constructor)(smallmap*, void*, const void*),
        void (*key_move)(smallmap*, void*, const void*),
        void (*key_destructor)(smallmap*, void*),
        bool (*value_constructor)(smallmap*, void*, const void*),
        void (*value_move)(smallmap*, void*, const void*),
        void (*value_destructor)(smallmap*, void*),
        uint32_t (*hasher)(const void*),
        bool (*compare)(const void*, const void*),
        void*(*allocate)(size_t),
        void(*deallocate)(void*));

bool sm_try_get(const smallmap* map, const void* key, void* value);

使い方としてはどうしても次のようにコード量が増えてしまって悩みます.

テスト
#include "smallmap.h"
#include "tshash.h"
#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>

static uint64_t pcg32_state = 0x853C49E6748FEA9BULL;

static uint32_t pcg32_rotr32(uint32_t x, uint32_t r)
{
    return (x >> r) | (x << ((~r + 1) & 31U));
}

uint32_t pcg32_rand()
{
    uint64_t x = pcg32_state;
    uint32_t count = (uint32_t)(x >> 59);
    pcg32_state = x * 0x5851F42D4C957F2DULL + 0xDA3E39CB94B95BDBULL;
    x ^= x >> 18;
    return pcg32_rotr32((uint32_t)(x >> 27), count);
}

void pcg32_srand(uint64_t seed)
{
    do {
        pcg32_state = 0xDA3E39CB94B95BDBULL + seed;
    } while(0 == pcg32_state);
    pcg32_rand();
}

/**
 * @brief return [0, s)
 */
uint32_t pcg32_range_ropen(uint32_t s)
{
    uint32_t x = pcg32_rand();
    uint64_t m = (uint64_t)x * (uint64_t)s;
    uint32_t l = (uint32_t)m;
    if(l < s) {
        uint32_t t = ((uint32_t)(-(int64_t)s)) % s;
        while(l < t) {
            x = pcg32_rand();
            m = (uint64_t)x * (uint64_t)s;
            l = (uint32_t)m;
        }
    }
    return m >> 32;
}

void shuffle(uint32_t size, char** items0, uint32_t* items1)
{
    for(uint32_t i = size; 0 != i; --i) {
        uint32_t offset = pcg32_range_ropen(i);
        assert(offset<size);
        char* tmp0 = items0[offset];
        items0[offset] = items0[i-1];
        items0[i-1] = tmp0;

        uint32_t tmp1 = items1[offset];
        items1[offset] = items1[i-1];
        items1[i-1] = tmp1;
    }
}

static bool key_constructor(smallmap* map, void* dst_key, const void* src_key)
{
    const char* src = (const char*)src_key;
    size_t len = strlen(src);
    char* dst = (char*)sm_allocate(map, (len + 1) * sizeof(char));
    if(NULL == dst) {
        return false;
    }
    memcpy(dst, src, len);
    dst[len] = '\0';
    *((char**)dst_key) = dst;
    return true;
}

static void key_move(smallmap* map, void* dst_key, const void* src_key)
{
    (void)map;
    const char** dst = (const char**)dst_key;
    const char** src = (const char**)src_key;
    *dst = *src;
    *src = NULL;
}

static void key_destructor(smallmap* map, void* key)
{
    char** dst = (char**)key;
    sm_deallocate(map, *dst);
    *dst = NULL;
}

static bool value_constructor(smallmap* map, void* dst_value, const void* src_value)
{
    (void)map;
    uint32_t* dst = (uint32_t*)dst_value;
    const uint32_t* src = (const uint32_t*)src_value;
    *dst = *src;
    return true;
}

static void value_move(smallmap* map, void* dst_value, const void* src_value)
{
    (void)map;
    int32_t* dst = (int32_t*)dst_value;
    const uint32_t* src = (const uint32_t*)src_value;
    *dst = *src;
}

static void value_destructor(smallmap* map, void* value)
{
    (void)map;
    (void)value;
}

static uint32_t hasher(const void* key)
{
    const char* str = *(const char**)(key);
    size_t len = strlen(str);
    return tshash32(len, str, TSHASH_DEFUALT_SEED);
}

static bool compare(const void* x0, const void* x1)
{
    const char* s0 = *(const char**)x0;
    const char* s1 = *(const char**)x1;
    return 0 == strcmp(s0, s1);
}

#define SAMPLE_NUM (0x1UL<<8U)

int main(void)
{
    pcg32_srand(12345);
    size_t size = sizeof(char*)*SAMPLE_NUM;
    char** keys = (char**)malloc(size);
    if(NULL == keys){
        return -1;
    }
    uint32_t* values = (uint32_t*)malloc(sizeof(uint32_t)*SAMPLE_NUM);
    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        char buffer[64] = {0};
        sprintf(buffer, "key_%010d", i);
        size_t len = strlen(buffer);
        keys[i] = (char*)malloc(len+1);
        if(NULL == keys[i]){
            return -1;
        }
        strcpy(keys[i], buffer);
        values[i] = i;
    }
    shuffle(SAMPLE_NUM, keys, values);

    smallmap* map = sm_construct(
        sizeof(char*),
        sizeof(uint32_t),
        key_constructor,
        key_move,
        key_destructor,
        value_constructor,
        value_move,
        value_destructor,
        hasher,
        compare,
        NULL, NULL);
    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        sm_add(map, keys[i], &values[i]);
    }
    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        uint32_t index = sm_find(map, keys[i]);
        assert(index != SM_INVALID);
        uint32_t value;
        bool result = sm_try_get(map, keys[i], &value);
        assert(result);
        assert(value == values[i]);
    }
    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        sm_remove(map, keys[i]);
    }
    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        uint32_t index = sm_find(map, keys[i]);
        assert(index == SM_INVALID);
    }
    sm_destruct(map);
    map = NULL;

    for(uint32_t i=0; i<SAMPLE_NUM; ++i){
        free(keys[i]);
    }
    free(values);
    free(keys);
    return 0;
}

まとめ

明らかな欠点として, 存在しないキーを検索すると全探索します. 配列内でチェインを模倣する方法がメモリ消費と引き換えにあらゆる状況に対応できると思います.

TODO

パフォーマンス測定はまったく行っていません.

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?