c语言第4章：map键为string的实现

分享未结  0  680

李延 LV6 2022-05-13

悬赏：20积分

# 1 说明

在上一章节中，我们实现了map的结构，但对于string 类型的hash值没有实现，所有无法计算key为string 的map。本章实现hash算法，并设置一个dictType，实现key为string的存储。

# 2 murmurHash实现

murmur_hash.h

```c
#ifndef MURMURHASH
#define MURMURHASH

#include <stdint.h>

uint64_t murmurHash64B( const void * key, int len, unsigned int seed );

#endif
```

murmur_hash.c

```c
#include "murmur_hash.h"

uint64_t murmurHash64B(const void *key, int len, unsigned int seed) {

const unsigned int m = 0x5bd1e995;

const int r = 24;

unsigned int h1 = seed ^ len;

unsigned int h2 = 0;

const unsigned int *data = (const unsigned int *) key;

while (len >= 8) {

unsigned int k1 = *data++;

k1 *= m;
        k1 ^= k1 >> r;
        k1 *= m;

h1 *= m;
        h1 ^= k1;

len -= 4;

unsigned int k2 = *data++;

k2 *= m;
        k2 ^= k2 >> r;
        k2 *= m;

h2 *= m;
        h2 ^= k2;

len -= 4;

}

if (len >= 4) {

unsigned int k1 = *data++;

k1 *= m;
        k1 ^= k1 >> r;
        k1 *= m;

h1 *= m;
        h1 ^= k1;

len -= 4;

}

switch (len) {

case 3:
            h2 ^= ((unsigned char *) data)[2] << 16;

case 2:
            h2 ^= ((unsigned char *) data)[1] << 8;

case 1:
            h2 ^= ((unsigned char *) data)[0];

h2 *= m;

};

h1 ^= h2 >> 18;
    h1 *= m;

h2 ^= h1 >> 22;
    h2 *= m;

h1 ^= h2 >> 17;
    h1 *= m;

h2 ^= h1 >> 19;
    h2 *= m;

unsigned long long h = h1;

h = (h << 32) | h2;

return h;

}
```

# 3 dictType 的实现

dict_type.c

```c
dictType strObjectDictType = {
        (uint64_t (*)(const void *)) dictStrHash,            /* hash function */
        NULL,                       /* key dup */
        NULL,                       /* val dup */
        hashKeyCompare,      /* key compare */
        NULL,          /* key destructor */
        NULL        /* val destructor */
};

uint64_t dictStrHash(const void *key) {

return murmurHash64B(key, strlen(key), 0);
}

int hashKeyCompare(const void *key1, const void *key2) {
    return dictStrHash(key1) == dictStrHash(key2);
}
```

# 4 测试用例

```c
#include "../util/dict.h"
#include "stdio.h"
#include "../util/dict_type.h"

int main() {
    dict *di = dictCreate(&strObjectDictType);
    char *a = 0;
    char *a1 = "123";
    char *a2 = "123";
    char *a3 = "123";
    char *a4 = "123";
    char *a5 = "123";
    char *a6 = "123";
    char *a7 = "123";
    char *b = "123";
    char *c = "123";
    dictAdd(di, &a, &c);
    dictAdd(di, &a1, &b);
    dictAdd(di, &a2, &b);
    dictAdd(di, &a3, &b);
    dictAdd(di, &a4, &b);
    dictAdd(di, &a5, &b);
    //    dictDelete(di, &a5);
    dictEntry *value = dictFind(di, &a5);
    dictAdd(di, &a6, &b);
    dictAdd(di, &a7, &b);

if(value == NULL){
        printf("null");
    } else{
        printf("%d", *(int *)value->v.val);
    }
    return 0;
}
```

回帖

消灭零回复