Подтвердить что ты не робот

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

В первую очередь меня интересуют строковые ключи. Может кто-нибудь указать мне на библиотеку?

4b9b3361

ОТВЕТЫ

Ответ 1

У меня была такая же потребность, и я провел некоторое исследование и в итоге использовал libcfu

Это просто и понятно, поэтому, если мне нужно изменить, я могу это сделать, не тратя слишком много времени, чтобы понять. Это также лицензия BSD. Не нужно менять мои структуры (чтобы вставлять слова следующего указателя)

Мне пришлось отклонить другие варианты по следующим причинам (мои личные причины, YMMV):

  • sglib → это макро-лабиринт, и мне было неудобно отлаживать/делать изменения на такой базе кода, используя только макросы
  • cbfalconer → много лицензионных красных флагов, а сайт был опущен и слишком много неблагоприятных обсуждений в Интернете о поддержке/авторе; не хотел рисковать
  • google sparce-hash → как уже сказано, это для С++, а не C
  • glib (gnome hash) → выглядел очень многообещающим; но я не мог найти простой способ установить комплект разработчика; Я просто нуждался в C-подпрограммах/файлах - не в полной раздутой среде разработки
  • Judy → кажется слишком сложным для простого использования.. также не был готов отлаживать себя, если мне приходилось сталкиваться с любыми проблемами.
  • npsml (упомянутый здесь) → не может найти источник
  • strmap найдено очень просто и полезно - просто слишком просто, что и ключ, и значение должны быть строками; Значение string является слишком строгим (должно принимать void *)
  • uthash → кажется хорошим (упоминается в википедии на хэш-таблице); обнаружил, что он требует, чтобы структура была модифицирована - не хотела этого делать, поскольку performace на самом деле не является проблемой для моего использования - это большая скорость разработки.

В заключение для очень простого использования strmap является хорошим; uthash, если вы заинтересованы в использовании дополнительной памяти. Если только скорость разработки или простота использования является основной целью, libcfu выигрывает [note libcfu внутренне выделяет память для поддержки узлов/хэш-таблиц]. Удивительно, что существует не так много простых реализаций хэш-кода C.

Ответ 2

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

Ответ 3

Для строк, Judy Array может быть хорошо.

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

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

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

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

Ответ 5

Dave Hanson C Интерфейсы и реализации включает в себя мелкую хеш-таблицу и несколько других хорошо спроектированных структур данных. Существует также красивый интерфейс обработки строк. Книга великолепна, если вы можете себе это позволить, но даже если это не так, я нашел это программное обеспечение очень хорошо разработанным, достаточно маленьким, чтобы учиться целиком и легко использовать его в нескольких разных проектах.

Ответ 6

Прошло много времени с тех пор, как я задал этот вопрос... Теперь я могу добавить свою собственную библиотеку общедоступного домена в список:

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

Ответ 10

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

Ответ 11

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

Ответ 13

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)" */

Ответ 14

stl имеет карту и hash_map (hash_map только в некоторых реализациях), которые являются ключом к значению, если вы можете использовать С++.

http://www.cplusplus.com/reference/stl/map/