hashmap 无法识别相同的键

Question

我已经尝试使用哈希图有一段时间了，使用我的讲师提供的代码，但它只是无法将两个相同的字符识别为相同。

我真的不知道我还能说些什么——我尝试过修改我的代码和讲师，尝试过各种不同的发送参数的方式，以及各种其他我不太记得的事情我的头顶。它似乎无法识别 'a' = 'a'。

我的相关代码：

#include <stdio.h>
#include <string.h>
#include "hash.h"

int main(int argc, char* argv[]) {
    int len = strlen(argv[1]);

    hashmap map = hash_init();

    for (int i = 0; i < len; i++) {
        char cha = argv[1][i];

        put(&map, cha, 1);
    }

    char* mapStr = to_str(map);
    printf("%s", mapStr);

    return 0;
}

我导师的相关代码：

hashmap.c

#include "hash.h"

hashmap hash_init(void) {
    hashmap h = {(map_node **)malloc(BINS * sizeof(map_node *)), 0, BINS};
    for (int i = 0; i < BINS; i++)
        h.table[i] = NULL;
    return h;
}

static int hash(char *key, int bins) {
    unsigned hashval = 0;
    for (int i = 0; i < strlen(key); i++)
        hashval = 31 * hashval + key[i];
    return hashval % bins;
}

int put(hashmap *h, char *key, int value) {
    int index = hash(key, h->bins);
    for (map_node *iterator = h->table[index]; iterator; iterator = iterator->next)
        if (!strcmp(iterator->key, key)){// I found the key
            int old_val = iterator->value;
            iterator->value = value;
            return old_val;//return old value
        }
    if (h->size >= h->bins)//load factor >= 100%
        rehash(h);
    map_node *new_element = (map_node *)malloc(sizeof(map_node));
    new_element->next = h->table[index];
    new_element->key = strdup(key);
    new_element->value = value;
    h->table[index] = new_element;
    h->size++;
    return 0;//return old value
}

char* to_str(hashmap h){
    char* rv = (char*) malloc(h.size * 100 + 1);
    for(int i = 0; i < h.bins;i++)
        for (map_node *it = h.table[i]; it; it = it->next)
            sprintf(rv, "%s\n%s: %d", rv, it->key, it->value);
    return rv;
}

Input: abcba
expected output: a:2 b:2 c:1
actual output: b:1 b:1 c:1 a:1 a:1

感谢您至少阅读本文。

Answer 1

1. 如果没有 hash.h，你的代码是不完整的。这意味着我已经添加了缺失的包含，对 typedef

   map_node

   ，

   hashmap

   进行了逆向工程。为

   BINS

   补一个值。为函数

   rehash()

   .
   创建占位符

2. 避免全局变量

   BINS

   。在这种情况下，只需向

   hash_init()

   添加一个参数即可。

3. （不固定）

   hash_init()

   ：按值返回哈希图。最好返回一个

   hashmap *

   （所以你需要同时分配一个hashmap和hashmap.table）。

4. 不用计算字符串（特别是循环）的长度，只需使用

   str[i]

   在终止

   \0

   时为 false 的事实即可。

5. put()

   ：您需要查找某个键的现有值并传入它

   value + 1

   以放置或更改逻辑，从而更新值。我在这里做了后者。

6. to_str()

   ：

   sprintf(rv, ..., rv, ...)

   是未定义的行为，因为您只是打印它，无论如何将其更改为

   hashmap_print()

   。

7. main()

   ：在尊重

   argc

   之前检查

   argv

   。

8. main()

   ：

   put()

   需要一个字符串，但

   argv[1][i]

   是一个

   char

   。例如，使用初始化器构造一个字符串。

#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct map_node {
    char *key;
    int value;
    struct map_node *next;
} map_node;

typedef struct {
    map_node **table;
    int size;
    int bins;
} hashmap;

int BINS = 13;

hashmap hash_init(void) {
    hashmap h = { calloc(BINS, sizeof(map_node *)), 0, BINS };
    return h;
}

static int hash(char *key, int bins) {
    unsigned hashval = 0;
    for (int i = 0; key[i]; i++)
        hashval = 31 * hashval + key[i];
    return hashval % bins;
}

void rehash(hashmap *h) {
    assert("TBD" && 0);
}

int put(hashmap *h, char *key, int value) {
    int index = hash(key, h->bins);
    for (map_node *iterator = h->table[index]; iterator; iterator = iterator->next)
        if (!strcmp(iterator->key, key)){
            iterator->value += value;
            return iterator->value;
        }
    if (h->size >= h->bins)
        rehash(h);
    map_node *new_element = malloc(sizeof *new_element);
    new_element->next = h->table[index];
    new_element->key = strdup(key);
    new_element->value = value;
    h->table[index] = new_element;
    h->size++;
    return 0;
}

void hashmap_print(hashmap h){
    for(int i = 0; i < h.bins;i++)
        for (map_node *it = h.table[i]; it; it = it->next)
            printf("%s: %d\n", it->key, it->value);
}

int main(int argc, char* argv[]) {
    if(argc < 2) {
        printf("usage: program keys\n");
        return 1;
    }
    hashmap map = hash_init();
    for (int i = 0; i < argv[1][i]; i++)
        put(&map, (char []) { argv[1][i], '\0' }, 1);
    hashmap_print(map);
    return 0;
}

和示例运行：

$ ./a.out abcba
a: 2
b: 2
c: 1