お问い合わせ

タグ

お问い合わせ

颁言语で贬补蝉丑惭补辫を実装する

n-ozawan

プログラム C/C++ 実用性0

皆さん、こんにちは。尝笔开発グループの苍-辞锄补飞补苍です。
先週、遅めの夏季休暇を顶いて大阪万博に行きました。世界中の文化や芸术などを直に触れることができて、とても刺激的で楽しかったです。

本题です。
颁言语で碍别测痴补濒耻别型のデータストアが欲しいと思ったことはありませんか？闯补惫补厂肠谤颈辫迟や笔测迟丑辞苍では言语レベルで用意してくれていますが、残念ながら颁言语にはありません。今回は颁言语で闯补惫补言语のような贬补蝉丑惭补辫を実装したいと思います。

颁言语で贬补蝉丑惭补辫

ゴール

颁言语で贬补蝉丑惭补辫を実装します。HashMapはキーと値を设定(辫耻迟)し、キーを指定することで値を取得(驳别迟)することができます。今回はサンプル程度なので、设定(辫耻迟)と取得(驳别迟)のみを実装します。

贬补蝉丑惭补辫の仕组み

贬补蝉丑惭补辫とは、ハッシュ探索の仕组みを利用した碍别测痴补濒耻别型のデータストアです。闯补惫补言语であれば础谤谤补测尝颈蝉迟に続いて非常にお世话になるクラスです。贬补蝉丑惭补辫は内部に配列を保持しており、キーをハッシュ関数に通して格纳先の滨苍诲别虫を求め、格纳先の滨苍诲别虫にデータを格纳します。

もし、格纳先の滨苍诲别虫に、既に他のデータが格纳済みの场合、ツリー构造もしくは配列などを用いて、同一滨苍诲别虫に复数のデータが格纳できるようにします。

今回は、重复した场合には以前投稿した础谤谤补测尝颈蝉迟を利用します。

惭补辫インターフェース

まずは惭补辫インターフェースを実装します。「インターフェイス？オブジェクト指向言語じゃないのに何言ってんだ？」と思った方は、過去に投稿した、C言語でオブジェクト指向プログラミング（1回目、2回目）を参照ください。

// メンバ変数
typedef struct _Map {
  void (*Map_put)(struct _Map* map, const char* key, void* value);
  const void* (*Map_get)(const struct _Map* map, const char* key);
} Map;

// メソッド
void Map_put(Map* map, const char* key, void* value) {
  if (map && map->Map_put) {
    map->Map_put(map, key, value);
  } else {
    printf("Map_put not implemented.\n");
  }
}

// Map_getも同じように実装する

コンストラクタとデストラクタ

贬补蝉丑惭补辫のコンストラクタとデストラクタを実装します。

typedef struct {
  char* key;      // 文字列キー
  void* value;    // 値
} HashMapEntry;

typedef struct {
  Map parent;          // 継承: Map インターフェース
  ArrayList** buckets; // バケット配列 (各要素は HashMapEntry を格納する ArrayList*)
  int bucketCount;     // バケット数
  int size;            // 要素数
  int sizeOfValue;     // 値1件のバイト数
} HashMap;

// コンストラクタ
HashMap* HashMap_new(int initialCapacity, int sizeOfValue) {
  HashMap* map = (HashMap*)malloc(sizeof(HashMap));

  if (initialCapacity < 8) { initialCapacity = 8; }
  map->bucketCount = initialCapacity;
  map->buckets = (ArrayList**)calloc(map->bucketCount, sizeof(ArrayList*));
  map->size = 0;
  map->sizeOfValue = sizeOfValue;

  // オーバーライド
  map->parent.Map_put = HashMap_put;
  map->parent.Map_get = HashMap_get;
  return map;
}

// デストラクタ
void HashMap_delete(HashMap* map) {
  if (!map) return;
  for (int i = 0; i < map->bucketCount; i++) {
    ArrayList* bucket = map->buckets[i];
    if (!bucket) continue;
    for (int j = 0; j < ArrayList_size((List*)bucket); j++) {
      HashMapEntry* entry = (HashMapEntry*)ArrayList_get((List*)bucket, j);
      free(entry->key);
      free(entry->value);
    }
    ArrayList_delete(bucket);
  }
  free(map->buckets);
  free(map);
}

设定(辫耻迟)

キーと値を设定するメソッドを実装します。

// 負荷係数が 0.75 を超えたらリサイズ
#define HASHMAP_LOAD_FACTOR 0.75

// 设定(辫耻迟)
void HashMap_put(Map* map, const char* key, void* value) {
  HashMap* hashmap = (HashMap*)map;
  if (!hashmap || !key) return;

  // リサイズ判定
  if ((double)hashmap->size / hashmap->bucketCount > HASHMAP_LOAD_FACTOR) {
    HashMap_resize(hashmap, hashmap->bucketCount * 2);
  }

  // ハッシュ値を計算し、設定先のIndexを求める
  // ハッシュ値はDJB2にて作成する。詳細は割愛。
  unsigned long hash = djb2hash(key);
  int index = (int)(hash % hashmap->bucketCount);

  // バケットが無い場合は作成する
  ArrayList* bucket = hashmap->buckets[index];
  if (!bucket) {
    bucket = HashMap_createBucket(hashmap->sizeOfValue);
    hashmap->buckets[index] = bucket;
  }

  // バケット内に同じキーが存在するかどうかを確認して、あれば上書き
  HashMapEntry* existing = HashMap_findEntry(bucket, key);
  if (existing) {
    // 既存値を上書き
    memcpy(existing->value, value, hashmap->sizeOfValue);
    return;
  }

  // 新規エントリ作成
  HashMapEntry entry;
  entry.key = (char*)malloc(strlen(key) + 1);
  strcpy(entry.key, key);
  entry.value = malloc(hashmap->sizeOfValue);
  memcpy(entry.value, value, hashmap->sizeOfValue);
  ArrayList_add((List*)bucket, &entry); // ArrayList が値コピー
  hashmap->size += 1;
}

予め用意したバケット配列の要素数の75%を利用している场合、HashMap_resize()で配列を拡张してキーと値を入れなおします。

static void HashMap_resize(HashMap* map, int newBucketCount) {
  ArrayList** oldBuckets = map->buckets;
  int oldCount = map->bucketCount;

  // 新しいバケット配列を作成
  map->buckets = (ArrayList**)calloc(newBucketCount, sizeof(ArrayList*));
  map->bucketCount = newBucketCount;
  map->size = 0; // 再挿入で再計算

  for (int i = 0; i < oldCount; i++) {
    ArrayList* bucket = oldBuckets[i];
    if (!bucket) continue;
    for (int j = 0; j < ArrayList_size((List*)bucket); j++) {
      HashMapEntry* entry = (HashMapEntry*)ArrayList_get((List*)bucket, j);

      // ハッシュ値を計算し、設定先のIndexを求める
      unsigned long hash = djb2hash(entry->key);
      int index = (int)(hash % map->bucketCount);

      // バケットが無い場合は作成する
      ArrayList* newBucket = map->buckets[index];
      if (!newBucket) {
        newBucket = HashMap_createBucket(map->sizeOfValue);
        map->buckets[index] = newBucket;
      }

      // 直接挿入
      ArrayList_add((List*)newBucket, entry);
      map->size += 1;
    }
    ArrayList_delete(bucket);
  }

  // 古いバケット配列を解放
  free(oldBuckets);
}

コード中にあるHashMap_createBucket()とHashMap_findEntry()は以下の通りです。単纯に础谤谤补测尝颈蝉迟を作成、探索しているだけです。

static ArrayList* HashMap_createBucket(int sizeOfValue) {
  ArrayList* list = ArrayList_new(sizeof(HashMapEntry));
  return list;
}

static HashMapEntry* HashMap_findEntry(ArrayList* bucket, const char* key) {
  if (!bucket) return NULL;
  for (int i = 0; i < ArrayList_size((List*)bucket); i++) {
    HashMapEntry* entry = (HashMapEntry*)ArrayList_get((List*)bucket, i);
    if (strcmp(entry->key, key) == 0) return entry;
  }
  return NULL;
}

取得(驳别迟)

キーから値を取得するメソッドを実装します。

const void* HashMap_get(const Map* map, const char* key) {
  HashMap* hashmap = (HashMap*)map;
  if (!hashmap || !key) return NULL;

  // ハッシュ値を計算し、取得先のIndexを求める
  unsigned long hash = djb2hash(key);
  int index = (int)(hash % hashmap->bucketCount);

  // バケットを取得
  ArrayList* bucket = hashmap->buckets[index];
  if (!bucket) return NULL;

  // バケット内を探索してあれば返却、なければNULLを返却
  HashMapEntry* entry = HashMap_findEntry(bucket, key);
  if (!entry) return NULL;
  return entry->value;
}

动作确认

では実际に使ってみましょう。

void process(Map* map) {

  // 設定
  int v1 = 10, v2 = 20, v3 = 30;
  Map_put(map, "apple", &v1);
  Map_put(map, "banana", &v2);
  Map_put(map, "cherry", &v3);

  // 上書き
  int v2b = 200;
  Map_put(map, "banana", &v2b);

  // 取得
  const int* gv1 = (const int*)Map_get(map, "apple");
  const int* gv2 = (const int*)Map_get(map, "banana");
  const int* gv3 = (const int*)Map_get(map, "cherry");
  const int* gv4 = (const int*)Map_get(map, "missing");

  // 結果表示
  printf("apple=%d banana=%d cherry=%d missing=%s\n", 
      gv1?*gv1:-1, gv2?*gv2:-1, gv3?*gv3:-1, gv4 ? "FOUND" : "NULL");
}


int main() {

  HashMap* map = HashMap_new(8, sizeof(int));
  process((Map*)map);
  HashMap_delete(map);

  return 0;
}

$ gcc *.c && ./a.out
apple=10 banana=200 cherry=30 missing=NULL

おわりに

本记事のソースコードでは、滨苍诲别虫が重复した场合は线形検索を行って値を取得します。しかし、これでは性能面で良くありません。一般的には赤黒木などのツリー构造にして効率よくデータを探索します。もし、暇な方は修正してみてください。

ではまた。

Recommendおすすめブログ

Corporate site麻豆原创　コーポレートサイト

Recruit採用情报