Поиск хорошей реализации хеш-таблицы в [закрытом] C

https://github.com/dozylynx/C-hashtable

[обновлен URL-адрес как исходный, теперь 404: http://www.cl.cam.ac.uk/~cwc22/hashtable/ ]

Определенные функции

* create_hashtable
* hashtable_insert
* hashtable_search
* hashtable_remove
* hashtable_count
* hashtable_destroy

Пример использования

  struct hashtable  *h;
  struct some_key   *k;
  struct some_value *v;

  static unsigned int         hash_from_key_fn( void *k );
  static int                  keys_equal_fn ( void *key1, void *key2 );

  h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);

  insert_key   = (struct some_key *) malloc(sizeof(struct some_key));
  retrieve_key = (struct some_key *) malloc(sizeof(struct some_key));

  v = (struct some_value *) malloc(sizeof(struct some_value));

  (You should initialise insert_key, retrieve_key and v here)

  if (! hashtable_insert(h,insert_key,v) )
  {     exit(-1);               }

  if (NULL == (found = hashtable_search(h,retrieve_key) ))
  {    printf("not found!");                  }

  if (NULL == (found = hashtable_remove(h,retrieve_key) ))
  {    printf("Not found\n");                 }

  hashtable_destroy(h,1); /* second arg indicates "free(value)" */

Загрузите tcl и используйте их проверенную временем хеш-функцию tcl. Это просто. TCL API хорошо документирован.

Никогда не использовал, но Google Sparsehash может работать

Здесь есть несколько хороших ответов:
Класс / библиотека контейнера для C

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

Для строк может подойти Judy Array .

Массив Джуди - это сложная, но очень быстрая ассоциативная структура данных массива для хранения и поиска значений с использованием целочисленных или строковых ключей. В отличие от обычных массивов, массивы Judy могут быть разреженными; то есть они могут иметь большие диапазоны неназначенных индексов.

Вот библиотека Judy в C .

Библиотека AC, которая обеспечивает современное состояние основная технология, реализующая разреженный динамический массив. Массивы Judy объявляются просто с нулевым указателем. Массив Judy потребляет память только тогда, когда он заполнен, но при желании может увеличиваться, чтобы использовать всю доступную память.

Другие ссылки,
Эта ссылка на реализацию хэша в Википедии содержит несколько ссылок на открытый исходный код C .
Кроме того, cmph - библиотека минимального идеального хеширования в C , поддерживает несколько алгоритмов.

Интерфейсы и реализации C обсуждают реализации хеш-таблиц на C. Исходный код доступен в Интернете . (Мой экземпляр книги находится в работе, поэтому я не могу сказать более конкретно.)

GLib - отличная библиотека для использования в качестве основы в ваших проектах C. У них есть неплохие предложения по структуре данных, включая хеш-таблицы: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (ссылка обновлена ​​06.04.2011)

Gperf - Perfect Hash Function Generator

http://www.ibm.com/developerworks/linux/library /l-gperf.html

Dave Hanson's C Interfaces and Implementations includes a fine hash table and several other well-engineered data structures. There is also a nice string-processing interface. The book is great if you can afford it, but even if not, I have found this software very well designed, small enough to learn in its entirety, and easy to reuse in several different projects.