Hashtables in ANSI-C

M

mansenpansen

Mitglied
Also: ich habe eine Menge Input (IP-Daten), den ich über die Standardeingabe bekomme. Diese Daten möchte ich nun anhand bestimmter Kriterien in einen Hash schreiben. Der Key selbst soll immer eine IP sein (wenn die IP schon als Schlüssel vorhanden ist, wird der Inhalt angehängt). Neben meinen Daten möchte ich aber auch noch für jeden Eintrag einen Timestamp anlegen, da ich Daten, an denen länger als 10 Sekunden nichts hinzugefügt wurde ausgeben möchte. Sind für dieses Problem die "Standard"-Hashtables von ANSI-C geeignet? Wenn ja, hat dann jemand vielleicht einen Link, der sich mit solchen Problemen beschäftigt, oder einen Tipp?

Vielen Dank im Voraus.

Susanne Kaufmann
 
Hi,
meine Frage muss es unbedingt Ansi C sein?
Wenn es C++ auch tut, bietet dir die STL mit ihren assoziativen Containern eine brauchbar
Lösung an.
Ein Beispiel wäre die Verwendung einer multimap, in der man zu einem Schlüssel
mehrere Values speichern kann: (sprich eine surjektive Abbildung von Schlüsseln
auf Werte:

Ungefähr so:



Code: 
#include <map>
#include <iostream>

using namespace std;

int main(){

        string ip;
        multimap<string, int, greater<string> > ipmap; //Anordnung nach lexikographischer Größe des strings
        
        while(ip != "q"){

                cout << "Ip:? ";
                cin >> ip;
                ipmap.insert(pair<string, int >(ip, time(NULL)));   //insert into the multimap
                cout << "There are " <<  ipmap.count(ip) << " values associated with the key " << ip << endl;
        }
        
        for(multimap<string, int, greater<string> >::iterator ptr = ipmap.begin(); ptr != ipmap.end(); ++ptr) //iterate through all elements 
                cout << "Key: " << ptr->first << " Value: " << ptr->second << endl; 
}

Es gibt natürlich noch ne Menge anderer brauchbarer assoziatove Container in der STL:
http://www.sgi.com/tech/stl/table_of_contents.html

Gruß

RedWing
 
Danke erstmal für die schnelle Antwort. Leider muss es ANSI-C sein....bin da leider ein wenig gebunden, da wir uns auf dieses geeinigt hatten (frag mich nicht warum, ich würde liebend gerne c++ oder c# verwenden...). Ich werde mal schauen ob ich so eine Art Mapping, mit dem ich einem Schlüssel mehrere Values zuweisen kann als Library finde.... oder vielleicht weiß da ja noch jemand Rat?
 
Also wenn du an ANIS C gebunden bist, warum erstellst du dir nicht eine struct die deine Daten incl. der IP aufnimmt. Z.B:
Code: 
typdef struct
{
   unsigned char IP[4];
   int idata;
   char *sdata
   int itime;
} myIP;

Dann organisiserts du die Einzelnen IP's in einer Liste (einfach oder doppelt verkettete Liste) Ich denke das sollte für deine Zwecke genügen.

Gruß Homer
 
Danke erstmal für die Idee structs in ne Liste zu packen. klingt gut. Nur habe ich dann das Problem, dass ich die IPs ja auch finden muss, da das ganze so ablaufen soll: ich bekomme ein Paket, welches eine IP und Daten enthält. Beides wird eingetragen. Nun bekomme ich Daten für genau dieselbe IP, welche (die Daten) ich an den bestehenden Dateneintrag anhängen möchte. Wie finde ich denn in einer normalen Liste diesen Eintrag dann schnellst möglich? Bei einem Hash könnte ich ja direnkt die IP als Schlüssel verwenden, aber bei einer Liste geht ja nichts in dieser Richtung, oder?
 
Du musst die Liste halt von vorne nach hinten durchlaufen,
um die IP zu finden. Das kannst du ja mit strcmp() machen...
Allerdings endet die Suche im schlimmsten Fall auch nach n Schritten bei n
Schlüsseln.
Eine Alternative wäre die Datenstruktur als binären Suchbaum zu realisieren.
Da müsstest du dir allerdings Gedanken um einen Ausgleichsalgorithmus machen,
da ein solcher Baum im schlimmsten Fall zu einer Liste entarten kann => du
bist wieder beim gleichen Problem
Ein Suchbaum ist so aufgebaut das alle Elemente die kleiner sind als der
momentane Knoten Links vom Knoten gespeichert werden, und alle Elemente die
größer sind rechts davon.
Bei einem ausgeglichenen Suchbaum liegt die Suche dann in O(log(n)) bei n
Schlüsseln(IP) und geht optimal schnell.
Die Container der STL sind schon so organisiert allerdings kannst du ja kein
C++ dahernehmen..
http://de.wikipedia.org/wiki/AVL-Baum
Gruß

RedWing
 
Gut, das werde ich mir mal näher ansehen. Werde aber auch mal noch schauen, ob ich ein Hash-Modul zum laufen bekomme (strhash). Habe das gefunden, will allerdings nicht so ganz funktionieren.....
 
hi mansenpansen

wenn du diese Daten für ein einzelnes Class C Netz aufbaust, hast du du max 255 verschiedene Adressen.
Dann wäre sicher ein einfaches Array, wo du auf jeden Eintrag direkt zugreifen kannst, die einfachste und schnellste Lösung.
Auch bei einem einzelnen Class B Netz hättest du nur 64k Einträge, was auch noch nicht allzuviel wäre. Da du jedesmal nur 4 Byte für den Pointer auf die Daten benötigst, wären das eben 1kB bzw 256kB (und zusätzlich der Bedarf für die Daten, den du aber in jedem Fall hast).

Wenn es sich um eine zeitkritische Anwendung handelt, darfst du den Zeitbedarf für Seitenaus-/einlagerung durch das OS nicht vergessen.

Gruss
Dora
 
dorado hat gesagt.:
hi mansenpansen

wenn du diese Daten für ein einzelnes Class C Netz aufbaust, hast du du max 255 verschiedene Adressen.
Dann wäre sicher ein einfaches Array, wo du auf jeden Eintrag direkt zugreifen kannst, die einfachste und schnellste Lösung.
Auch bei einem einzelnen Class B Netz hättest du nur 64k Einträge, was auch noch nicht allzuviel wäre. Da du jedesmal nur 4 Byte für den Pointer auf die Daten benötigst, wären das eben 1kB bzw 256kB (und zusätzlich der Bedarf für die Daten, den du aber in jedem Fall hast).

Wenn es sich um eine zeitkritische Anwendung handelt, darfst du den Zeitbedarf für Seitenaus-/einlagerung durch das OS nicht vergessen.

Gruss
Dora
Zum Vergrößern anklicken....

Auch eine Möglichkeit, und man könnte dann mittels Binary Search ein
suboptimales Suchen nach dem Schlüssel ermöglichen...
 
@RedWing

Der Schlüssel ist der Index im Array. Da brauchst du gar nicht suchen.
Die ersten 3 Byte sind für das gesamte Array gleich und brauchen nicht in die Indexierung miteinfliessen.

z.B. 212.144.55.123 -> Array Index 122, da die ersten 3 Byte ja fest sind.

Nicht belegte I/P Einträge erhalten einen NULL Pointer.

Gruss
Dora :)
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück