Hashtables/assoz. Arrays

[zak (Gast)]

Hi,

gibt es in C auch Hashtables bzw. assoziative Arrays wie in PHP u.Ä.?
Beispiel:

$array = array();
$array["key"] = "value";
$array["key2"] = "value2";
$array["key3"] = "value3";
$array["key4"] = "value4";

Gruß,
  zak

[Klaus W. (mfgkw)]

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).

[zak (Gast)]

hm.. sollte schon in C sein.. die Schreibweise ist mir egal, hauptsache 
es funktioniert..

ich werd mich dann mal auf die suche begeben, wenn es sowas schon 
umgesetzt wurde.. vielleicht haben es ja hier auch ein paar umgesetzt 
und möchten ihren source hier preisgeben? ;)

[zak (Gast)]

wobei man in arduino-sketches sicher auch C++ benutzen kann, da die 
arduino-bibliotheken auch in c++ geschrieben sind.. stellt sich nur die 
frage, wie

[Sven P. (Gast)]

Es gibt geschätzte zehntausend verschiedene Implementierungen von 
Hash-Tabellen, Bäumchen, Karten, Ketten und dergleichen in/für C.

Man sollte sich aber auch da im Klaren darüber sein, ob und wozu man 
sowas tatsächlich braucht, oder ob man Probleme sieht, wo keine sind...

[Klaus W. (mfgkw)]

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.

[zak (Gast)]

Ich will Strings zu Bytes speichern.. In PHP hätt ich zu einem 
assoziativem Array gegriffen mit dem byte als Key und dem String als 
Value..

[zak (Gast)]

Der rechner is ein ATmega168 oder ATmega328,
ob ich C++ in Arduino-Sketches benutzen kann weis ich nich, denk schön, 
wüsste aber nicht wie.

[Klaus W. (mfgkw)]

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

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>


// Datentyp für einen Tabelleneintrag:
typedef struct
{
  const char *key;
  uint8_t     value;
} wertepaar_t;

// Vergleichsfunktion dazu:
int compareWertePaar( const void *a, const void *b )
{
  return strcmp( ((const wertepaar_t*)a)->key, ((const wertepaar_t*)b)->key );
}

#define ANZAHL   (5)

int main( int nargs, char **args )
{
  // Feld füttern:
  wertepaar_t    tabelleWertePaare[ANZAHL] =
    {
      { "abc", 12 },
      { "def", 13 },
      { "xyz", 14 },
      { "klm", 15 },
      { "bla", 16 },
    };

  // einmalig sortieren:
  qsort( tabelleWertePaare, ANZAHL, sizeof( wertepaar_t ), compareWertePaar );

  // nach dem Wert zu "klm" suchen (15):
  wertepaar_t   key = { "klm", 0 /* Wert egal */ };
  wertepaar_t  *p_gefunden = bsearch( &key, tabelleWertePaare,
                                      ANZAHL, sizeof( wertepaar_t ),
                                      compareWertePaar
                                      );
  if( p_gefunden )
  {
    printf( "Wert: %d\n", (int)p_gefunden->value );
  }

  return 0;
}