c - hashmap 的动态数组访问冲突

Question

我在尝试实现一个小 HashMap 的表时遇到问题。

map .h

typedef struct Map Map;

Map *map_create();
int map_set(Map *map, char *key, void *val);

map .c

const int MAP_INITIAL_SIZE = 100;

typedef struct MapPair MapPair;
struct MapPair
{
    char *key;
    void *val;
};

struct Map
{
    MapPair **table;
    int count;
    int limit;
};

Map *map_create(void)
{
    Map *map = (Map*)malloc(sizeof(Map));
    if (!map) return NULL;

    map->table = (MapPair**)malloc(MAP_INITIAL_SIZE * sizeof(MapPair));
    if (!map->table)
    {
        free(map);
        return NULL;
    }

    map->count = 0;
    map->limit = MAP_INITIAL_SIZE;

    return map;
}

void add(MapPair **context, int start, MapPair *pair, int limit)
{
    int i = start;
    while (context[i] != NULL && strcmp(context[i]->key, pair->key) != 0) // crashing here
    {
        i++;
        if (i == limit) i = 0;
    }
    context[i] = pair;
}

int map_set(Map *map, char *key, void *val)
{
    if (map->count >= map->limit / 2)
    {
        if (!expand(map)) return 0;
    }

    MapPair *pair = (MapPair*)malloc(sizeof(MapPair));
    if (!pair) return 0;

    pair->key = key;
    pair->val = val;

    add(map->table, hash(key, map->limit), pair, map->limit);

    ++map->count;
    return 1;
}

我最初是在 pelles c 中开发的，但当我遇到问题时转向 vs2013 进行调试。然后在 vs2013 中，程序会在 add 函数处崩溃，但在 pelles c 中不会。我假设它与我计划以后能够扩展的动态数组有关。

谁能告诉我为什么当我尝试访问动态数组的索引时程序似乎崩溃了？

Answer 1

在 add 函数中，您正在检查表，直到到达 NULL 指针:

while (context[i] != N ...

但是当您分配这个表时，您永远不会将这些指针中的任何一个设置为 NULL:

map->table = (MapPair**)malloc(MAP_INITIAL_SIZE * sizeof(MapPair));

您应该将它们设置为 NULL:

for( size_t i = 0 ; i < MAP_INITIAL_SIZE ; i++ )
    map->table[i] = NULL ;

否则你将超出该数组的范围。