Ищете хорошую реализацию хеш-таблицы в C [закрыто]

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

65 голосов | спросил SetJmp 16 J000000Thursday09 2009, 20:22:33

14 ответов


0

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

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

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

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

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

ответил Karthik Gurusamy 12 MonEurope/Moscow2011-12-12T10:39:15+04:00Europe/Moscow12bEurope/MoscowMon, 12 Dec 2011 10:39:15 +0400 2011, 10:39:15
0

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

ответил Daniel M 16 J000000Thursday09 2009, 20:56:29
0

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

  

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

Вот библиотека Джуди в C .

  

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


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

ответил nik 16 J000000Thursday09 2009, 20:27:46
0

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

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

ответил Nick Van Brunt 16 J000000Thursday09 2009, 20:43:06
0

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

ответил Norman Ramsey 17 J000000Friday09 2009, 05:16:42
0

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

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

ответил SetJmp 28 MarpmMon, 28 Mar 2011 20:23:16 +04002011-03-28T20:23:16+04:0008 2011, 20:23:16
0

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

ответил sblair 16 J000000Thursday09 2009, 20:52:42
0

Библиотека Apache APR имеет свою собственную хеш-реализацию . Он уже перенесен на все, на чем работает Apache, и лицензия Apache также довольно либеральна .

ответил Mikhail T. 12 FebruaryEurope/MoscowbTue, 12 Feb 2013 02:34:49 +0400000000amTue, 12 Feb 2013 02:34:49 +040013 2013, 02:34:49
0
ответил alex 25 PMpThu, 25 Apr 2013 23:45:10 +040045Thursday 2013, 23:45:10
0

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

ответил Nick 16 J000000Thursday09 2009, 20:29:06
0

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

ответил xcramps 16 J000000Thursday09 2009, 20:45:54
0

Gperf - генератор идеальных хеш-функций

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

ответил 17 J000000Friday09 2009, 01:47:24
0

http://www.cl.cam.ac.uk/~ cwc22 /хеш /

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

* 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)" */
ответил Ryan Christensen 16 J000000Thursday09 2009, 20:31:05
0

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

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

ответил Ryan Christensen 27 MarpmSun, 27 Mar 2011 21:44:06 +04002011-03-27T21:44:06+04:0009 2011, 21:44:06

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132