C tablice asocjacyjne, jak zaimplementować?

[_LM_]

Cześć, poszukuję przykładów w języku C dla tablic, gdzie do pól mogę się odwołać przez klucz. W javie istnieje coś takiego jak typ map, gdzie zarówno klucz jak i wartość mogą przyjmować dowolny typ danych. W C trzeba to napisać od podstaw, lub skorzystać z gotowych przykładów ale coś mało jest w tym temacie materiałów, a jeśli już są to korzystają z C++ gdzie jest nawet biblioteka wbudowana <map.h> 

EDIT zapomniałem dorzucić link do tego co już znalazłem: https://ucgosu.pl/2019/07/tablice-przyspieszajace-wyszukiwanie-elementow/ oraz link z artykułu https://github.com/jamesroutley/write-a-hash-table

Edytowano Styczeń 5, 2022 przez _LM_

[ethanak]

Taka ładna implementacja: Glib (ogólnie dość często używam tej biblioteki do różnych celów).

I jeszcze przykład w konkretnej aplikacji: MBROLA

Edytowano Styczeń 5, 2022 przez ethanak

[_LM_]

Dzięki @ethanak zaraz się zapoznam. Mam pytanie co do kodu haszującego z gita:

https://github.com/jamesroutley/write-a-hash-table/tree/master/03-hashing

// hash_table.c
static int ht_hash(const char* s, const int a, const int m) {
    long hash = 0;
    const int len_s = strlen(s);
    for (int i = 0; i < len_s; i++) {
        hash += (long)pow(a, len_s - (i+1)) * s[i];
        hash = hash % m;
    }
    return (int)hash;
}

Czy jest jakaś możliwość aby to preprocesor poukładał zestawy danych w tablicach? Chodzi mi dane const aby nie zużywać pamięci ram?

[ethanak]

No, jeśli chcesz bardzo oszczędzać pamięć to tego typu tablice akurat pamięciooszczędne nie są. W przypadku małej tablicy lepiej po prostu przemiatać tablicę pętlą. Przy większych możesz sobie przygotować posortowane klucze i przeszukiwać np. bsearchem (ja tak robię w przypadku słowników syntezatora, a one raczej małe nie są).

Ogólnie hash tables są raczej do tablic dynamicznych które ze swej natury siedzą w RAM-ie.

[_LM_]

17 minut temu, ethanak napisał:

Ogólnie hash tables są raczej do tablic dynamicznych które ze swej natury siedzą w RAM-ie.

Aha, po zapoznaniu tematu też doszedłem do takiego wniosku, i fakt można by ręcznie poustawiać indeksy dla elementów stałych np: wygenerować je wcześniej, ale to mija się z celem bo dodanie kolejnego zestawu wymusi przeliczenie indeksów na nowo. Dzięki za odpowiedź!