Хэш хэша в C

Question

Я новичок в Си, потому что возвращаюсь к этому через 6 лет!хочу реализовать код для хранения дерева для этих данных, например:

string1 = "foo.bar.foo.\*" string2 = "foo.baz.\*" string3 = "foo.\*.bar"

     foo
      |
  |   |   |
 bar baz  *
  |   |   |
 foo  *  bar
  |
  *

, пытаясь сделать это с помощью HashTable:

struct entry_s {
    char *key;
    struct entry_s *value;
    struct entry_s *next;
};

но я не думаю, что это работает, каков наилучший способ сделать это, и хотя Hash Map - лучшая структура данных, которую можно использовать в C?

Answer 1

Кажется, что вы хотите реализовать карту с двумя уровнями: первый уровень отображает строки на карты второго уровня, а второй уровень отображает другой ключ на значение.Например, в синтаксисе Javascript:

data = {
    "London": {
        "Paris": 450
    },
    "Paris": {
       "Madrid": 600,
       "Algiers": 700
    }
}

Есть несколько способов достичь этого.

Переменные Javascript содержат свои типы, поэтому yozu может использовать одну и ту же реализацию Map для обоихуровни.В C вы можете реализовать две хеш-таблицы с разными типами значений, например:

struct OItem {                  // Outer map item
    const char *key;                // string key
    struct IMap *value;             // inner map value
    struct OItem *next;         
};

struct OMap {                   // Outer map
    struct OItem *head[oSize];      // hash table
};

struct IItem {                  // Inner map item
    const char *key;                // string key
    int value;                      // integer value
    struct IItem *next;
};

struct IMap {                   // Inner map
    struct IItem *head[iSize];      // hash table
};

Это даст вам двухуровневую структуру выше.(Эти хеш-таблицы имеют фиксированные размеры, так что вы можете в конечном итоге тратить много места, когда, например, карты второго уровня немногочисленны. Возможно, здесь может быть лучше использовать только один список или сбалансированное дерево. Если вы используетекарта второго уровня просто эмулирует объект, который всегда хэширует одни и те же или похожие данные, рассмотрите возможность использования структуры здесь.)

Вы можете использовать эту структуру и, например, lookup("London", "Paris").Если вам не нужен доступ к внутренней карте, вы также можете упаковать оба уровня в одну большую хеш-таблицу с помощью двух ключей:

struct Item {
    const char *key1;
    const char *key2;
    int value;
    struct Item *next;
};

struct Map {
    struct Item *head[hSize];
};

Когда вы вычисляете хеш, используйте оба ключа, например:

static unsigned int hash(const char *s1, const char *s2)
{
    unsigned long hash = 5381u;

    while (*s1) hash = hash * 33 ^ *s1++;
    hash = hash *33;
    while (*s2) hash = hash * 33 ^ *s2++;

    return hash;
}

При поиске элемента убедитесь, что оба ключа совпадают:

int map_find(const struct Map *map,
    const char *k1, const char *k2)
{
    unsigned int h = hash(k1, k2) % hSize;
    struct Item *item = map->head[h];

    while (item) {
        if (strcmp(item->key1, k1) == 0
         && strcmp(item->key2, k2) == 0) {
            return item->value;
        }

        item = item->next;
    }

    return 0;
}

Этот подход, возможно, более ограничительный, но имеет то преимущество, что у вас не так много потенциальнобольшие хеш-таблицы, но только одна структура данных.

Наконец, что бы вы ни делали, не используйте реализацию хеш-таблиц, которую вы нашли в GitHub.Автор признает, что это было скорее упражнение по кодированию.Он не имеет дело с освобождением памяти после использования и имеет плохую хэш-функцию.

---

После того, как вы отредактировали в своем реальном случае использования, становится ясно, что вы хотите trie ,Вы можете реализовать Trie, как вы предложили.Ключами и значениями могут быть все что угодно в вашей реализации, поэтому они также могут быть строками и узлами Trie.Вы можете адаптировать вашу существующую реализацию, чтобы использовать указатель на структуру узлов в качестве значений.(К счастью, все сравнительные данные остаются неизменными.)

Одна проблема, которую я вижу, состоит в том, что при фиксированном размере хеш-таблицы вы в конечном итоге будете тратить много места.Если ваше дерево редко, лучше использовать просто связанный список или сбалансированное двоичное дерево в качестве карты.В любом случае вам придется найти подходящую библиотеку или свернуть свою собственную.

Answer 2

Ваш вопрос на самом деле не имеет смысла, и я думаю, что это потому, что вы на самом деле не понимаете, как будут работать хеш-таблицы, поэтому вот некоторый (грубый и непроверенный) код, чтобы показать вам, как они будут работать:

typedef struct entry_s {
    char *key;
    char *value;
    struct entry_s *next;
} entry_t;

#define MAX_HASH 1234;

entry_t *myHashTable[MAX_HASH];


void insert(char *key, char *value);
    entry_t *entry;

    hash = calculateHash(key) % MAX_HASH;

    // Create entry

    entry = malloc(sizeof(entry_t));
    if(entry == NULL) exit(EXIT_FAILURE);
    entry->key = key;
    entry->value = value;

    // Add entry to the singly linked list for this hash

    entry->next = myHashTable[hash];
    myHashTable[hash] = entry;
}


entry *find(char *key) {
    entry_t *entry;

    hash = calculateHash(key) % MAX_HASH;
    entry = myHashTable[hash];
    while(entry != NULL) {
        if(strcmp(key, entry->key) == 0) {
            return entry;
        }
        entry = entry->next;
    }
    return NULL;
}


void delete(char *key) {
    entry_t *previous = NULL;
    entry_t *entry;

    hash = calculateHash(key) % MAX_HASH;
    entry = myHashTable[hash];
    while(entry != NULL) {
        if(strcmp(key, entry->key) == 0) {

            // Remove entry from the singly linked list for this hash

            if(previous == NULL) {
                myHashTable[hash] = entry->next;
            } else {
                previous->next = entry->next;
            }

            // Free the memory and return

            free(entry);
            return;
        }
        previous = entry;
        entry = entry->next;
    }
}

Примечание: хорошее понимание односвязных списков поможет вам понять, что делает этот пример.