Offset von Feldern einer Struktur

[Stefan F. (Gast)]

  struct person {
    int   alter;
    float gewicht;
    char  name[25];
    long  personalnummer;
  } adam, eva;  

function putIntoHashMap(void* object, int keyOffset, int keySize) {
   ...
}

putIntoHashMap(&adam, ?, sizeof(name));
// oder: putIntoHashMap(&adam, ?, sizeof(personalnummer));

Ich möchte eine HashMap programmieren, die Zeiger auf beliebige Objekte 
(Strukturen) speichern kann. Um den HashCode zu erzeugen, muss die 
Funktion putIntoHashMap() jedoch wissen, wo das Schlüsselfeld innerhalb 
der Struktur beginnt, und wie groß es ist.

Nur, wie rufe ich die Funktion korrekt auf? Was muss ich anstelle von 
"?" schreiben?

Anmerkung: Mir ist klar das String-Arrays hinter dem Ende des Strings 
zufällige Zeichen enthalten. Dafür denke ich mir später eine Lösung aus.

[Johann L. (gjlayde)]

Die Funktion hat das falsche Interface:  Als 2. Parameter würde man die 
Startadresse des Werts angeben, aus dem der Hash berechnet werden soll, 
also z.B.

&eva.personalnummer

Das 3. Argument ist tückisch, weil sizeof nicht unbedingt die Größe 
Objekts angibt sondern auch Füllbytes und oder -bits enthalten kann. 
Und auch innerhalb eines Objekts können Lücken auftreten.

Man braucht also zusätzliche Restriktionen oder zusätzliches Wissen über 
das Objekt, auf das der 2. Parameter zeigt.

[Dr. Sommer (Gast)]

offsetof(person, name);

http://en.cppreference.com/w/cpp/types/offsetof

Wie wäre es aber stattdessen mit einer Funktion in diesem Stil:
void putIntoHashMap (char* key, size_t keySize, void* object);
d.h. seperatem Key.

Außerdem verwendet man als Datentyp für Array-Größen size_t und nicht 
int (unter x86_64 zB braucht man nämlich einen 64bit-Typ dafür, aber 
"int" ist dort typischerweise nur 32bit)

[Stefan F. (Gast)]

Ach wie doof: idexof / offsetof - hätte ich ja erraten können sollen.

> Wie wäre es aber stattdessen mit einer Funktion in diesem Stil:
> void putIntoHashMap (char* key, size_t keySize, void* object);
> d.h. seperatem Key.

Danke für den Tip, ich denk drüber nach.

> &eva.personalnummer

Ja sicher, so war das auch gedacht. Ich hab's nur falsch hingeschrieben.

> Das 3. Argument ist tückisch, weil sizeof nicht unbedingt die Größe
> Objekts angibt sondern auch Füllbytes und oder -bits enthalten kann.

Bei einfachen Typen (nicht structs) liefert sizeof() aber die richtige 
größer, oder? Wenn ja, dann müsste ich als Restriltion notieren, dass 
der Key ein einfacher Typ sein muss - was meinerm Anwendungsfall 
entspricht.

[Stefan F. (Gast)]

Die Unsicherheiten bei sizeof() gefallen mir nicht. Ich werde einen ganz 
anderen Ansatz versuchen:

  struct person {
    int   alter;
    float gewicht;
    char  name[25];
    long  personalnummer;
  } adam, eva;  

void putIntoHashMap(void* object, long hashCode) {...};

long stringHash(char* text) {...};

long longHash(long i) {...};

putIntoHashMap(&adam, stringHash(adam.name));
// oder: putIntoHashMap(&adam, longHash(adam.personalnummer));

Ist das so besser?

By the way: ich sehe gerade, dass ich oben das Schlüsseldort "function" 
verwendet habe. Ich beginne wohl, Programmiersprachen durcheinander zu 
werfen. Aber ihr habt dennoch verstanden, was ich meinte. Super.

[Dr. Sommer (Gast)]

Hättest du jetzt eine Programmiersprache mit Overloads (wie C++) 
könntest du die verschiedenen Hash-Funktionen für die verschiedenen 
Typen alle gleich nennen (zB "hash") und könntest dann einfach 
hash(adam.name) oder hash(adam.personalnummer) schreiben, und es würde 
automatisch die korrekte Funktion genutzt.
Hättest du außerdem eine Programmiersprache mit templates (wie C++) 
bräuchtest du für all die verschiedenen Integer-Typen nur eine einzige 
Hash-Funktion schreiben (da die verschiedenen Typen ja wahrscheinlich 
gleich behandelt werden), die automatisch vom Compiler an den jeweiligen 
Typ angepasst wird.
Hättest du allerdings eine Programmiersprache, die HashMaps bereits 
integriert hat (wie C++), könntest du die einfach verwenden und dir 
diese Frickelei ersparen...

[Stefan F. (Gast)]

Hätte Hätte fahradkette.

Du hast da natürlich Recht. In diesem Fall möchte ich mich (wegen 
Mikrocontroller) jedoch auf C beschränken. Mit den haken und Ösen von 
C++ auf diesen kleinen Dingern habe ich mich (noch) nicht beschäftigt. 
Kommt aber sicher auch bald auf meinen privaten Lehrplan.

[Peter II (Gast)]

Da er Hash nur intern für einen Hash-map gebraucht wird. Warum nicht 
einfach die Stuktur am Anfang mit 0 initialisieren

memset( @t, 0, sizeof(t) );

und dann einfach über die gesamte stuktur (incl. vorhanden Füllbytes) 
den Hash berechnen?

[Jörg W. (dl8dtl) (Moderator)]

Stefan us schrieb:
> In diesem Fall möchte ich mich (wegen Mikrocontroller) jedoch auf C
> beschränken.

Das mit dem „wegen Mikrocontroller“ ist kein Argument. ;-)

> Mit den haken und Ösen von C++ auf diesen kleinen Dingern
> habe ich mich (noch) nicht beschäftigt.

Das schon eher.  Aber solange du nirgends das Wort „virtual“
schreibst und keine Exceptions benutzt, ist das Risiko ziemlich gering,
dass dir da irgendwas „explodiert“.

offsetof() ist übrigens auch Bestandteil von C99.

[Lukas K. (carrotindustries)]

Ich gehe mal davon aus, dass deine Hashmap je Instanz nur gleiche 
Datentypen speichert. Beim Erstellen der Hashmap gibt man eine Funktion 
mit, die zum Hashen der Daten verwendet wird.

Wenn das nicht der Fall ist, kannst du ja der putIntoHashMap Funktion 
nen Funktionspointer auf die Funktion die den Hash berechnet übergeben.

[Karl H. (kbuchegg)]

Peter II schrieb:
> Da er Hash nur intern für einen Hash-map gebraucht wird. Warum nicht
> einfach die Stuktur am Anfang mit 0 initialisieren
>
> memset( @t, 0, sizeof(t) );
>
> und dann einfach über die gesamte stuktur (incl. vorhanden Füllbytes)
> den Hash berechnen?

Weil man in den meisten Fällen über einen Schlüsselwert den kompletten 
Datensatz in der Hash-map wiederfinden möchte. Was nützt es mir, wenn 
ich zum Suchen des Datensatzes bereits den kompletten Datensatz haben 
müsste, nur damit ich dessen Hash-Wert berechnen kann um dann in der 
Hash-map das zu finden, was ich sowieso schon habe.

[Peter II (Gast)]

Karl Heinz schrieb:
> Weil man in den meisten Fällen über einen Schlüsselwert den kompletten
> Datensatz in der Hash-map wiederfinden möchte. Was nützt es mir, wenn
> ich zum Suchen des Datensatzes bereits den kompletten Datensatz haben
> müsste?

eventuell will er ja doppelte Objekte finden.

[Karl H. (kbuchegg)]

Peter II schrieb:
> Karl Heinz schrieb:
>> Weil man in den meisten Fällen über einen Schlüsselwert den kompletten
>> Datensatz in der Hash-map wiederfinden möchte. Was nützt es mir, wenn
>> ich zum Suchen des Datensatzes bereits den kompletten Datensatz haben
>> müsste?
>
> eventuell will er ja doppelte Objekte finden.

Dann ist aber eine Sortierung der Datensätze mit anschliessendem 
Nachfolgervergleich einfacher als eine Hash-map mit Kollisionsstrategie 
:-)

[Stefan F. (Gast)]

> Ich gehe mal davon aus, dass deine Hashmap je Instanz
> nur gleiche Datentypen speichert.
Ich auch.

> Beim Erstellen der Hashmap gibt man eine Funktion
> mit, die zum Hashen der Daten verwendet wird.
Und genau dann muss ich der Hashmap beim Erstellen auch mitteilen, wo 
das key Feld im Objekt liegt und wie groß es ist. Womit wir wieder be 
meiner Ursprünglichen Frage nach offsetof() wären.

> Wenn das nicht der Fall ist, kannst du ja der putIntoHashMap
> Funktion nen Funktionspointer auf die Funktion die den Hash
> berechnet übergeben.
Das entspricht fast meinem zweiten Ansatz, wo ich den Rückgabewert der 
Hashfunktion übergebe.

[Stefan F. (Gast)]

> Warum nicht einfach die Stuktur am Anfang mit 0 initialisieren
> und dann einfach über die gesamte stuktur (incl. vorhanden Füllbytes)
> den Hash berechnen?

1.) Weil ich die Hashmap verwenden will, um Personen anhand ihrer Namen 
oder Personalnummern zu finden. Die anderen Felder kenne ich beim Suchen 
nicht. Wenn ich die Werte alle Felder kennen würde, müsste ich nich 
suchen.

2.) Weil ich die Datensätze ändern können möchte - ausgenommen die 
beiden Key-Felder.

[Lukas K. (carrotindustries)]

Stefan us schrieb:

>> Beim Erstellen der Hashmap gibt man eine Funktion
>> mit, die zum Hashen der Daten verwendet wird.
> Und genau dann muss ich der Hashmap beim Erstellen auch mitteilen, wo
> das key Feld im Objekt liegt und wie groß es ist. Womit wir wieder be
> meiner Ursprünglichen Frage nach offsetof() wären.

Die Hashfunktion bekommt nen pointer auf die gesamte Struktur. Wie sie 
die dann hasht, ist ihr Problem. Auch kann sie dabei mehrere Felder zum 
Hashen verwenden.

[Karl H. (kbuchegg)]

Stefan us schrieb:

>> Beim Erstellen der Hashmap gibt man eine Funktion
>> mit, die zum Hashen der Daten verwendet wird.
> Und genau dann muss ich der Hashmap beim Erstellen auch mitteilen, wo
> das key Feld im Objekt liegt und wie groß es ist. Womit wir wieder be
> meiner Ursprünglichen Frage nach offsetof() wären.

Ich finde ebenfalls diesen Ansatz nicht so schlau.
Warum willst du unbedingt das WIssen darüber, wo der Key herkommt, in 
die Hash-map Funktionen mit renigeben. Die Einfügefunktion kriegt einen 
Pointer auf den Key und dessen Länge und gut ists.

[Stefan F. (Gast)]

Na dann sind wir uns ja einig. Die erste idee war nicht so doll.

Ich finde den zweiten Ansatz eleganter, wo ich beim Einfügen des 
Objektes den Hashcode mit übergebe, welchen ich mit einer Hash-Funktion 
entsprechend dem Feldtyp berechne.

So sind sowohl HashMap als als auch die Hash Funktionen für andere 
Strukturen wiederverwendbar.

[Rolf M. (rmagnus)]

Karl Heinz schrieb:
> Stefan us schrieb:
>
>>> Beim Erstellen der Hashmap gibt man eine Funktion
>>> mit, die zum Hashen der Daten verwendet wird.
>> Und genau dann muss ich der Hashmap beim Erstellen auch mitteilen, wo
>> das key Feld im Objekt liegt und wie groß es ist. Womit wir wieder be
>> meiner Ursprünglichen Frage nach offsetof() wären.
>
> Ich finde ebenfalls diesen Ansatz nicht so schlau.
> Warum willst du unbedingt das WIssen darüber, wo der Key herkommt, in
> die Hash-map Funktionen mit renigeben.

Warum nicht?

> Die Einfügefunktion kriegt einen Pointer auf den Key und dessen Länge und
> gut ists.

Das hätte dann einen Vorteil, wenn ich für jedes Objekt ein anderes 
Element als Key verwenden möchte. Aber das ist doch gar nicht sinnvoll. 
Die Art, wie der Hash gebildet wird, muß doch eh immer gleich sein.

[Karl H. (kbuchegg)]

Rolf Magnus schrieb:

>> Ich finde ebenfalls diesen Ansatz nicht so schlau.
>> Warum willst du unbedingt das WIssen darüber, wo der Key herkommt, in
>> die Hash-map Funktionen mit renigeben.
>
> Warum nicht?

Weil ich denke, dass es nicht schlau ist, in die Hashfunktionen 
derartige implizten Zusammenhänge mit reinzugeben. Näher kann ichs nicht 
begründen. Es war in der Vergangenheit immer so, dass eine zu starke 
Verquickung (die nicht wirklich notwendig ist) auf lange Sicht zu 
Problemen geführt hat.

> Das hätte dann einen Vorteil, wenn ich für jedes Objekt ein anderes
> Element als Key verwenden möchte.

Zum Beispiel

> Aber das ist doch gar nicht sinnvoll.
> Die Art, wie der Hash gebildet wird, muß doch eh immer gleich sein.

Ich hab ja nicht gesagt, dass man nicht rund um die eigentliche 
Hashfunktion noch weitere Funktionen legen kann

  struct person {
    int   alter;
    float gewicht;
    char  name[25];
    long  personalnummer;
  } adam, eva;  

void putIntoHashMap(void* object, void* key, size_t keyLength )
{
...
};

void addByName( struct person* person )
{
  putIntoHashMap( person, person->name, strlen( person->name ) );
}

void addByPersonalNr( struct person* person )
{
  putIntoHashMap( person, person->personalnummer, sizeof( person->personalnummer ) );
}

void addByBeerConsumption( struct person* person, int consumption )
{
  putIntoHashMap( person, consumption , sizeof( consumption ) );
}

So kann ich unterschiedliche Hashmaps aufbauen, die eine nach Namen, die 
andere nach Personalnummer, ohne dass ich mich dauernd mit den Details 
der Keygenerierung rumschlagen muss.
Was ich natürlich nicht machen darf. In ein und derselben Hashmap 
mischen. Das ist schon klar. Aber warum soll ich die eigentliche 
Hashgenerierung jedesmal neu schreiben, nur weil ich eine weitere Map 
brauche die nach irgendwas anderem indiziert ist? In die Map kommen 
Pointer zu den Objekten rein, die abseits der Map zb in einem Array 
gespeichert sind. Die einzelnen Maps indizieren dann je nach gehaster 
Eigenschaft in dieses Array.