チェイン法によるハッシュ探索

http://www.geocities.jp/ky_webid/algorithm/014.html

ハッシュの話が出てきました。

LL等、他の言語では言語仕様として存在しているものですね。

Cの場合は自分で実装しないといけません。

どういう仕組みなのかちゃんと理解するためにもここはマスターする必要がありますね。

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

#define HASHMAX 10

struct HASH {
    int data;
    char *key;
    struct HASH *next;
};
typedef struct HASH HASH;

int hashkey (char *s);
HASH *create_hash(char *s,int data);
void set_hash (HASH **hash,char *s,int data);
int get_hash (HASH **hash,char *s);
void del_hash (HASH **hash,char *s);
    
HASH *create_hash(char *s,int data) {
    HASH *p;
    p = (HASH *)malloc(sizeof(HASH));
    if ( p == NULL ) {
        return NULL;
    }
    p->next = NULL;
    p->data = data;
    p->key  = s;
    return p;
}

void set_hash (HASH **hash,char *s,int data) {
    int key = hashkey(s);
    HASH *p = hash[key];
    
    if ( p != NULL ) {
        HASH *n;
        for (n=p;p!=NULL;n=p,p=p->next ) {
            // 同じキー名があったら上書き
            if ( strcmp(p->key,s) == 0 ) {
                p->key = s;
                p->data = data;
                return;
            }
        }
        n->next = create_hash(s,data);
    }
    else {
        hash[key] = create_hash(s,data);
    }
    
}

int get_hash (HASH **hash,char *s) {
    int key = hashkey(s);
    HASH *p = hash[key];
    
    for (;p!=NULL;p=p->next ) {
        if ( strcmp(p->key,s) == 0 ) {
            return p->data;
        }
    }
    
    // 無い場合どうしようか
    return 0;
}

void del_hash (HASH **hash,char *s) {
    int key = hashkey(s);
    HASH *p = hash[key];
    HASH *n;
    
    if ( p == NULL ) {
        return;
    }
    
    for (n=p;p!=NULL;n=p,p=p->next ){
        if ( strcmp(p->key,s) == 0 ) {
            n->next = p->next;
            free(p);
            p = NULL;
            return;
        }
    }
}

int hashkey (char *s) {
    int key = 0;
    
    while(*s) {
        key += *s++;
    }
    
    return key % HASHMAX;
}

int main (void) {
    HASH *hash[HASHMAX] = {0};
    
    // ハッシュ値が同じケース
    set_hash(hash,"aaytaa",100);
    set_hash(hash,"aytaaa",300);
    set_hash(hash,"ytaaaa",500);
    
    // 300のを上書き
    set_hash(hash,"aytaaa",350);
    
    // 100 350 500と表示されるはず
    printf("%d\n",get_hash(hash,"aaytaa"));
    printf("%d\n",get_hash(hash,"aytaaa"));
    printf("%d\n",get_hash(hash,"ytaaaa"));
    puts("---");
    
    // 350のキーを削除してみる
    del_hash(hash,"aytaaa");
    
    // 100 0 500と表示されるはず
    printf("%d\n",get_hash(hash,"aaytaa"));
    printf("%d\n",get_hash(hash,"aytaaa"));
    printf("%d\n",get_hash(hash,"ytaaaa"));
    puts("---");
    
    // 空文字
    set_hash(hash,"",1000);
    printf("%d\n",get_hash(hash,""));
    puts("---");
    
    // 存在しないキー
    printf("%d\n",get_hash(hash,"oooo"));
    
    return 0;
}
100
350
500
---
100
0
500
---
1000
---
0

出来ました。

データの格納、取得、削除を行う関数を作りました。

またハッシュ値の計算方法は配列の要素で割った余りというシンプルなものを利用しました。

他にも色々な計算方法があるみたいです。シフト演算子で計算するものとか?

とりあえず要素数を10としましたが、100くらいが妥当なのかもしれません。というか扱うデータの多さによって変更できるといいのかもしれません。


今回の実装でリスト構造の扱いに大分慣れてきました。そろそろリスト構造のソート処理などにもチャレンジしてみようかなと思っています。