Hashtables/assoz. Arrays

kurze Antwort:
in C++ ja, in C nein

oder etwas genauer:
Man kann sich in C natürlich sowas bauen (bzw. gibt es sicher
schon tausendmal fertig), aber dann muss man die Schreibweise
mit table["key"] knicken; das geht nicht.

In C++ gibt es das in der Std-Lib als std::map; wobei darunter
keine Hashtabelle steckt, sondern ein RB-Baum.
Von boost (und mutmaßlich im nächsten Standard) gibt es dann auch
ein assoziatives Array als Hashtabelle (oder notfalls von mir,
wenn ich danach suche - irgendwann hatte ich das mal selbst gebaut).

Es ist die Frage, ob sich das lohnt.
Wenn der Rechner so schwach auf der Brust ist, daß man C++-Templates
nicht nehmen mag (die wenig Overhead haben), wird man mit Hashtabellen
in C auch nicht glücklich.
Dann lohnt es sich eher, nicht Hashtabellen zu nehmen, sondern z.B.
sortierte Feldern (bei Bedarf sortieren mit qsort() aus der Standard-
bibliothek, suchen darin mit bsearch()).

Das Suchen hat dann ebenso wie bei den maps in C++ die
Laufzeitordnung O(log n), Hashtabellen hätten O(1).
Durch den höheren Aufwand bei Hashtabellen hätten diese erst Vorteile
bei ziemlich vielen Elementen; das wird auf einem MC nie sein.

Hat man umgekehrt ein System, das entsprechende Datenmengen im
Speicher hat, ist C++ das Mittel der Wahl.

Insofern sind Hashtabellen in C m.E. verlorene Liebesmühe; es
bringt nichts außer viel Arbeit.

Hier die C-Variante (schnell, einfach, sparsam):

1

#include <stdlib.h>

2

#include <stddef.h>

3

#include <stdio.h>

4

#include <string.h>

5

#include <stdint.h>

6

7

8

// Datentyp für einen Tabelleneintrag:

9

typedef struct

10

{

11

  const char *key;

12

  uint8_t     value;

13

} wertepaar_t;

14

15

// Vergleichsfunktion dazu:

16

int compareWertePaar( const void *a, const void *b )

17

{

18

  return strcmp( ((const wertepaar_t*)a)->key, ((const wertepaar_t*)b)->key );

19

}

20

21

#define ANZAHL   (5)

22

23

int main( int nargs, char **args )

24

{

25

  // Feld füttern:

26

  wertepaar_t    tabelleWertePaare[ANZAHL] =

27

    {

28

      { "abc", 12 },

29

      { "def", 13 },

30

      { "xyz", 14 },

31

      { "klm", 15 },

32

      { "bla", 16 },

33

    };

34

35

  // einmalig sortieren:

36

  qsort( tabelleWertePaare, ANZAHL, sizeof( wertepaar_t ), compareWertePaar );

37

38

  // nach dem Wert zu "klm" suchen (15):

39

  wertepaar_t   key = { "klm", 0 /* Wert egal */ };

40

  wertepaar_t  *p_gefunden = bsearch( &key, tabelleWertePaare,

41

                                      ANZAHL, sizeof( wertepaar_t ),

42

                                      compareWertePaar

43

                                      );

44

  if( p_gefunden )

45

  {

46

    printf( "Wert: %d\n", (int)p_gefunden->value );

47

  }

48

49

  return 0;

50

}