ハッシュの実装(演習版)

K&R本 演習6-5

ハッシュの実装は一度やっていますが、K&R本に載っていたハッシュ実装(チェイン法)がなかなか良さそうだったので参考にしながら自分で再実装してみます。

また、演習もやってみます。

lookupとinstallによって保守されるテーブルから、名前と定義を削除する関数undefを書け。

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

#define TABLEMAX 100

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

HASH *lookup(HASH **hash,char *key);

unsigned int gethash (char *s) {
    unsigned int hashval;
    for (hashval=0;*s!='\0';s++){
        hashval = *s + 31 * hashval;
    }
    return hashval % TABLEMAX;
}

HASH *create(char *key,char *s) {
    HASH *p;
    p = (HASH *)malloc(sizeof(HASH));
    if ( p == NULL ) return NULL;
    p->next = NULL;
    p->key  = _strdup(key);
    p->data = _strdup(s);
    return p;
}

HASH *install(HASH **hash,char *key,char *s) {
    unsigned int id;
    HASH *p;
    p = lookup(hash,key);
    if ( p == NULL ) {
        p = create(key,s);
        id = gethash(key);
        p->next = hash[id];
        hash[id] = p;
    }
    else {
        free(p->data);
        p->data = _strdup(s);
    }
    return p;
}

HASH *lookup(HASH **hash,char *key) {
    unsigned int id = gethash(key);
    HASH *p;
    for (p=hash[id];p!=NULL;p=p->next) {
        if ( strcmp(p->key,key) == 0 ) {
            return p;
        }
    }
    return NULL;
}

void undef(HASH **hash,char *key) {
    unsigned int id = gethash(key);
    HASH **p;
    HASH *del;
    for (p=&hash[id];*p!=NULL;p=&(*p)->next) {
        if ( strcmp((*p)->key,key) == 0 ) {
            del = *p;
            *p = (*p)->next;
            free(del->key);
            free(del->data);
            free(del);
            break;
        }
    }
}

int main (void) {
    HASH *hash[TABLEMAX] = {0};
    
    install(hash,"aaaa","123");
    install(hash,"bbbb","222");
    install(hash,"bbbb","333");
    install(hash,"cccc","444");
    install(hash,"dddd","567");
    
    undef(hash,"cccc");
    
    printf("%s\n",lookup(hash,"aaaa")->data);
    printf("%s\n",lookup(hash,"bbbb")->data);
    printf("%s\n",lookup(hash,"dddd")->data);
    
    if ( lookup(hash,"cccc") == NULL ) {
        printf("cccc is NULL\n");
    }
    
    return 0;
}

123
333
567
cccc is NULL

できました。

結構綺麗に実装できたと思うのですがどうでしょう。

データが連結してる場合でもundefがちゃんと削除されているか検証するためにgethashの戻り値を必ず1になるようにして検証もしてみました。

ちゃんと再連結されていたので問題ないと思います。