Auf der Suche nach einer guten Hash-Tabellen-Implementierung in C [closed]

Lesezeit: 5 Minuten

Benutzeravatar von Setjmp
Setjmp

Ich interessiere mich hauptsächlich für Saitenschlüssel. Kann mir jemand eine Bibliothek nennen?

Benutzeravatar von Karthik Gurusamy
Karthik Gurusamy

Ich hatte das gleiche Bedürfnis und recherchierte und benutzte es schließlich libcfu

Es ist einfach und lesbar. Wenn ich also Änderungen vornehmen muss, kann ich es tun, ohne zu viel Zeit für das Verständnis aufwenden zu müssen. Es ist auch von der BSD-Lizenz. Keine Notwendigkeit, meine Strukturen zu ändern (um beispielsweise einen nächsten Zeiger einzubetten)

Die anderen Optionen musste ich aus folgenden Gründen ablehnen (meine persönlichen Gründe, YMMV):

  • sglib –> es ist ein Makro-Labyrinth und ich fühlte mich nicht wohl beim Debuggen/Ändern an einer solchen Codebasis nur mit Makros
  • cbfalconer –> viele Redflags bei der Lizenzierung, und die Seite war ausgefallen und zu viele ungünstige Diskussionen im Web über Support/Autor; wollte das Risiko nicht eingehen
  • google sparce-hash –> wie bereits erwähnt, ist es für C++, nicht für C
  • glib (Gnome-Hash) –> sah sehr vielversprechend aus; aber ich konnte keinen einfachen Weg finden, das Developer Kit zu installieren; Ich brauchte nur die C-Routinen/Dateien – nicht die vollständige Entwicklungsumgebung
  • Judy –> scheint zu komplex für eine einfache Verwendung. Ich war auch nicht bereit, mich selbst zu debuggen, wenn ich auf Probleme stoßen musste
  • npsml (hier erwähnt) -> kann die Quelle nicht finden
  • strmap sehr einfach und nützlich gefunden – es ist einfach zu einfach, dass sowohl Schlüssel als auch Wert Zeichenfolgen sein müssen; Der Wert als Zeichenfolge scheint zu restriktiv zu sein (sollte void * akzeptieren)
  • uthash –> scheint gut zu sein (wurde auf Wikipedia auf Hashtable erwähnt); festgestellt, dass struct geändert werden muss – das wollte ich nicht tun, da die Leistung für meine Verwendung nicht wirklich ein Problem darstellt – es geht eher um die Entwicklungsgeschwindigkeit.

Zusammenfassend ist strmap für eine sehr einfache Verwendung gut; uthash, wenn Sie sich Sorgen um die zusätzliche Speichernutzung machen. Wenn nur die Geschwindigkeit der Entwicklung oder die Benutzerfreundlichkeit das Hauptziel ist, gewinnt libcfu [note libcfu internally does memory allocation to maintain the nodes/hashtables]. Es ist überraschend, dass nicht viele einfache C-Hash-Implementierungen verfügbar sind.

  • mir ist aufgefallen, dass uthash aktiver entwickelt zu sein scheint als libcfu (jahrgang 2005). Vielleicht ist dies aber kein Problem für ein bisschen Code – sind Sie seit diesem Beitrag auf andere Konkurrenten gestoßen?

    – bph

    23. Januar 2012 um 10:27 Uhr

  • Ich habe einen riesigen Datensatz und Glib unterstützt diese großen Daten (32-Bit-Schlüssel) nicht. Ich brauche mehr als glatt. Wie wäre es mit libcfu?

    – Baskaya

    25. Februar 2013 um 19:14 Uhr

  • Der libcfu-Link zeigt einen Fehler an …

    – spritzig

    7. Juli 2014 um 15:06 Uhr

  • Die Hashtable-Implementierung in CPython basiert auf libcfu: github.com/python/cpython/blob/master/Modules/hashtable.c

    – Ryan Li

    2. Juli 2015 um 18:04 Uhr

  • Dokument von Libcfu: libcfu.sourceforge.net/libcfu.html

    – Zhou Hongbo

    2. Juni um 7:49

Benutzeravatar von Daniel M
Daniel m

GLib ist eine großartige Bibliothek, die Sie als Grundlage in Ihren C-Projekten verwenden können. Sie haben einige anständige Datenstrukturangebote, einschließlich Hash-Tabellen: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (Link aktualisiert am 6.4.2011)

  • +1: Glib ist in der Tat eine großartige Bibliothek.

    – Stefan Borini

    17. Juli 2009 um 1:24 Uhr

  • Gehe ich richtig in der Annahme, dass Sie normalerweise dynamisch auf die Glib-Bibliothek verlinken, um diese Datenstrukturen zu verwenden, was möglicherweise zu Portierungsproblemen führt, wenn Sie von Linux zu Windows wechseln?

    – bph

    23. Januar 2012 um 10:35 Uhr

  • Glib unterstützt nur 32-Bit. Wenn Sie mit riesigen Datenmengen arbeiten, ist Glib keine gute Wahl

    – Baskaya

    25. Februar 2013 um 19:10 Uhr

niks Benutzeravatar
Nik

Für Saiten, die Judy Array könnte gut sein.

Ein Judy-Array ist eine komplexe, aber sehr schnelle assoziative Array-Datenstruktur zum Speichern und Suchen von Werten mithilfe von Integer- oder Zeichenfolgenschlüsseln. Im Gegensatz zu normalen Arrays können Judy-Arrays spärlich sein; Das heißt, sie können große Bereiche nicht zugewiesener Indizes haben.

Hier ist ein Judy-Bibliothek in C.

AC-Bibliothek, die eine hochmoderne Kerntechnologie bereitstellt, die ein spärliches dynamisches Array implementiert. Judy-Arrays werden einfach mit einem Nullzeiger deklariert. Ein Judy-Array verbraucht Speicher nur, wenn es bestückt ist, kann jedoch wachsen, um den gesamten verfügbaren Speicher zu nutzen, wenn dies gewünscht wird.


Andere Referenzen,
Dies Wikipedia-Hash-Implementierungsreferenz hat welche C Open-Source-Links.
Ebenfalls, cmph — Eine Minimal Perfect Hashing Library in Cunterstützt mehrere Algorithmen.

Benutzeravatar von Nick Van Brunt
Nick van Brunt

Hier gibt es gute Antworten:
Containerklasse/Bibliothek für C

http://sglib.sourceforge.net.

http://cbfalconer.home.att.net/download/

Dave Hansons C-Schnittstellen und Implementierungen enthält eine feine Hash-Tabelle und mehrere andere ausgereifte Datenstrukturen. Es gibt auch eine nette String-Verarbeitungsschnittstelle. Das Buch ist großartig, wenn Sie es sich leisten können, aber selbst wenn nicht, fand ich diese Software sehr gut gestaltet, klein genug, um sie vollständig zu erlernen, und einfach in mehreren verschiedenen Projekten wiederzuverwenden.

  • Verdammt! Ich muss das kaufen!

    – kirbyfan64sos

    2. Oktober 2015 um 22:50 Uhr

Benutzeravatar von Setjmp
Setjmp

Es ist lange her, seit ich diese Frage gestellt habe … Ich kann jetzt meine eigene Public Domain Library zur Liste hinzufügen:

http://sourceforge.net/projects/npsml/

  • Verdammt! Ich muss das kaufen!

    – kirbyfan64sos

    2. Oktober 2015 um 22:50 Uhr

sblairs Benutzeravatar
sblair

C-Schnittstellen und Implementierungen diskutiert Hash-Tabellen-Implementierungen in C. Der Quellcode ist Online verfügbar. (Mein Exemplar des Buches ist in Arbeit, daher kann ich nicht genauer sein.)

  • Danke für die Vorstellung dieses Buches. Habe gerade eine Bestellung bei Amazon aufgegeben.

    – Qiang Xu

    4. Januar 2013 um 21:11 Uhr

1416830cookie-checkAuf der Suche nach einer guten Hash-Tabellen-Implementierung in C [closed]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy