c - HashMap 与 search.h

Question

我有一个带有坐标(经度、纬度)和 ID 的 xml 文件。问题是我想将这些信息存储在 HashMap 中，但我不知道文件的最大大小。我在网上看到了一些例子:

#define _GNU_SOURCE

#include <search.h> // hcreate_r() hdestroy_r() struct hsearch_data
#include <string.h> // memset()
#include <stdio.h>  // perror()
#include <stdlib.h> //exit()

#define TAB 4

...

struct hsearch_data hash;
size_t max_element = 42; // of elements in search table

...

char *food[] = { "Apple",
                 "Banana",
                 "Lemon",
                 "Carrot"
};
char *color[] = { "red",
                  "yellow",
                  "yellow",
                  "orange"
};

// we create the hash
memset(&hash, 0, sizeof(hash));
if (hcreate_r(max_element, &hash) == 0) {
    perror("hcreate_r");
    exit(1);
}

/*
  adding some elements
*/

// we destroy the hash
hdestroy_r(&hash);

max_element 在我的情况下不知道，我不知道如何解决这个问题，这里是我的代码:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <libxml/tree.h>
#include <libxml/parser.h>

#define MAX_REF_LEN 10

static char der_ref[MAX_REF_LEN + 1];
static xmlChar *der_intitule = NULL;

void debut_document(void *user_data) {
    *der_ref = '\0';
    der_intitule = NULL;
}

void debut_element(void *user_data, const xmlChar *name, const xmlChar **attrs) {
    if (xmlStrEqual(name, BAD_CAST "node")) {
        if (NULL != attrs) {
            int i;
            for (i = 0; attrs[i] != NULL; i += 2) {
                if (xmlStrEqual(attrs[i], BAD_CAST "lat")) {
                    strncpy(der_ref, (char *)attrs[i + 1], MAX_REF_LEN);
                    printf("lat %s\n", der_ref);
                } else
                if (xmlStrEqual(attrs[i], BAD_CAST "lon")) {
                    strncpy(der_ref, (char *)attrs[i + 1], MAX_REF_LEN);
                    printf("lon %s\n", der_ref);
                }
            }
        }
    } 
}

int main() {

    xmlSAXHandler sh = { 0 };

    sh.startDocument = debut_document;
    sh.startElement = debut_element;

    if (xmlSAXUserParseFile(&sh, NULL, "map.osm") != 0) {
        fprintf(stderr, "Une erreur est survenue lors du parsing\n");
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

我还没有实现搜索库，但我想在 debut_element 函数中创建 HashMap。

“map.osm”是我的xml文件，但大小不固定。

Answer 1

<search.h>中的哈希表实现有几个限制:您必须事先知道尺寸并且不能删除项目。

就您而言，您仍然可以使用它，前提是您的元素列表在您阅读后不会更改。首先将所有项目读入动态数组。读取所有位置后，创建具有所需维度的哈希表并添加所有位置。

值是指向数组中项目的指针，键必须是字符串。因此，您应该保留 id 和位置的字符串表示形式。

这是一个示例实现。它不是从文件中读取位置，而是创建一些随机值。

#include <stdio.h>
#include <stdlib.h>
#include <search.h>
#include <math.h>
#include <time.h>

struct loc {
    int id;
    char label[12];
    double lat, lon;
};

struct map {
    size_t size;
    size_t count;
    struct loc *loc;
    struct hsearch_data hash;
};

double urand(void)
{
    return rand() / (1.0 + RAND_MAX);
}

void loc_print(struct loc *loc)
{
    printf("%s: (%g%c, %g%c)\n", loc->label,
        fabs(loc->lon), loc->lon > 0 ? 'E' : 'W',
        fabs(loc->lat), loc->lat > 0 ? 'N' : 'S');
}

void map_destroy(struct map *map)
{
    free(map->loc);
    hdestroy_r(&map->hash);
    free(map);
}

struct map *map_create(void)
{
    struct map *map = calloc(1, sizeof(*map));
    size_t i;

    while (0.005 * map->count < urand()) {
        struct loc *p;

        if (map->count == map->size) {
            map->size *= 2;
            if (map->size == 0) map->size = 1024;

            p = realloc(map->loc, map->size * sizeof(*p));
            if (p == NULL) {
                map_destroy(map);
                exit(1);
            }
            map->loc = p;
        }

        p = &map->loc[map->count];
        p->lon = 360.0 * urand() - 180.0;
        p->lat = 180.0 * urand() - 90.0;
        p->id = map->count + 1;
        snprintf(p->label, sizeof(p->label), "%d", p->id);
        map->count++;

        loc_print(p);
    }

    hcreate_r(3 * map->count / 2, &map->hash);

    for (i = 0; i < map->count; i++) {
        struct loc *p = &map->loc[i];        
        ENTRY e, *res = NULL;

        e.key = p->label;
        e.data = p;
        hsearch_r(e, ENTER, &res, &map->hash);
    }

    return map;
}

struct loc *map_find(struct map *map, int id)
{
    char label[12];
    ENTRY e, *res;

    snprintf(label, sizeof(label), "%d", id);
    e.key = label;
    hsearch_r(e, FIND, &res, &map->hash);

    if (res) return res->data;
    return NULL;
}

int main()
{
    struct map *map;
    int i;

    srand(time(NULL));

    puts("Creating map");
    map = map_create();

    puts("Looking up values");
    for (i = 5; i < 80; i += 5) {
        struct loc *loc = map_find(map, i);

        if (loc) {
            loc_print(loc);
        } else {
            printf("%d not found.\n", i);
        }
    }

    map_destroy(map);

    return 0;
}

当您的位置列表稍后增加时，您甚至可以使用此技术:如果达到某个阈值(例如哈希表大小的 75%)，只需销毁旧哈希表即可，然后创建一个更大大小的新哈希表。这应该可行，因为哈希表只是现有数据的辅助表示，可以实现快速查找。