C에서 좋은 해시 테이블 구현을 찾고

C에서 좋은 해시 테이블 구현을 찾고

---

저는 주로 문자열 키에 관심이 있습니다. 누군가 나를 도서관으로 안내 할 수 있습니까?

---

나는 똑같은 필요가 있었고 약간의 조사를했고 결국 libcfu 를 사용 했습니다.

간단하고 읽기 쉬우므로 수정이 필요하면 이해하는 데 너무 많은 시간을 들이지 않고도 할 수 있습니다. BSD 라이센스이기도합니다. 내 구조체를 변경할 필요가 없습니다 (다음 포인터를 포함하기 위해)

다음과 같은 이유로 다른 옵션을 거부해야했습니다 (개인적인 이유로 YMMV).

• sglib-> 매크로 미로이고 매크로 만 사용하여 이러한 코드 기반에서 디버깅 / 변경하는 것이 불편했습니다.
• cbfalconer-> 많은 라이센싱 레드 플래그, 사이트 다운 및 지원 / 저자에 대한 웹상에서 너무 많은 불리한 토론; 위험을 감수하고 싶지 않았다
• google sparce-hash-> 이미 언급했듯이 C가 아닌 C ++ 용입니다.
• glib (그놈 해시)-> 매우 유망 해 보였습니다. 하지만 개발자 키트를 설치하는 쉬운 방법을 찾을 수 없었습니다. 완전한 개발 환경이 아닌 C 루틴 / 파일 만 필요했습니다.
• Judy-> 간단한 사용으로는 너무 복잡해 보입니다 .. 또한 문제가 발생하면 직접 디버깅 할 준비가되지 않았습니다.
• npsml (여기에 언급 됨)-> 소스를 찾을 수 없습니다.
• strmap 은 매우 간단하고 유용 하다는 것을 발견했습니다. 키와 값이 모두 문자열이어야한다는 것은 너무 단순합니다. 문자열 값이 너무 제한적인 것 같습니다 (void * 허용해야 함).
• uthash- > 좋은 것 같습니다 (해시 테이블의 위키피디아 에 언급되었습니다); struct를 수정해야한다는 사실을 발견했습니다. 성능은 제 사용에 대한 관심이 아니기 때문에 그렇게하고 싶지 않았습니다. 개발 속도에 더 가깝습니다.

요약하면 매우 간단한 사용을 위해 strmap이 좋습니다. 추가 메모리 사용이 우려되는 경우 uthash. 개발 속도 나 사용 편의성이 주요 목표 인 경우 libcfu가 이깁니다. [libcfu는 노드 / 해시 테이블을 유지하기 위해 내부적으로 메모리 할당을 수행합니다]. 사용 가능한 간단한 C 해시 구현이 많지 않다는 것은 놀랍습니다.

---

GLib는 C 프로젝트의 기초로 사용할 수있는 훌륭한 라이브러리입니다. 그들은 해시 테이블을 포함하여 괜찮은 데이터 구조를 제공합니다 : http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (link updated 4/6/2011)

---

문자열의 경우 Judy Array 가 좋을 수 있습니다.

Judy 배열은 복잡하지만 정수 또는 문자열 키를 사용하여 값을 저장하고 조회하기위한 매우 빠른 연관 배열 데이터 구조입니다. 일반 배열과 달리 Judy 배열은 희소 할 수 있습니다. 즉, 할당되지 않은 인덱스의 범위가 넓을 수 있습니다.

다음은 C로 된 Judy 라이브러리 입니다 .

희소 동적 배열을 구현하는 최신 핵심 기술을 제공하는 AC 라이브러리입니다. Judy 배열은 단순히 널 포인터로 선언됩니다. Judy 어레이는 채워질 때만 메모리를 사용하지만 원하는 경우 사용 가능한 모든 메모리를 활용하도록 확장 할 수 있습니다.

---

기타 참조,
이 Wikipedia 해시 구현 참조 에는 일부 C오픈 소스 링크가 있습니다.
또한 cmph -A Minimal Perfect Hashing Library in C은 (는) 여러 알고리즘을 지원합니다.

---

여기에 몇 가지 좋은 답변이 있습니다.
C 용 컨테이너 클래스 / 라이브러리

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

---

Dave Hanson의 C 인터페이스 및 구현 에는 훌륭한 해시 테이블과 기타 잘 설계된 데이터 구조가 포함되어 있습니다. 멋진 문자열 처리 인터페이스도 있습니다. 이 책은 당신이 감당할 수 있다면 훌륭하지만, 그렇지 않더라도이 소프트웨어는 매우 잘 디자인되어 있고 전체적으로 배울 수있을만큼 작으며 여러 다른 프로젝트에서 재사용하기 쉽다는 것을 알았습니다.

---

이 질문을 한 지 오랜 시간이 지났습니다 ... 이제 내 공개 도메인 라이브러리를 목록에 추가 할 수 있습니다.

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

---

C 인터페이스 및 구현 은 C 에서 해시 테이블 구현에 대해 설명합니다. 소스 코드는 온라인에서 사용할 수 있습니다 . (책의 사본이 작동 중이므로 더 구체적으로 말할 수 없습니다.)

---

Apache의 APR 라이브러리에는 자체 해시 구현이 있습니다. Apache가 실행되는 모든 것에 이미 포팅되어 있으며 Apache 라이센스 도 다소 자유 롭습니다.

---

samtools / bwa / seqtk / klib의 khash.h

컬 https://raw.github.com/attractivechaos/klib/master/khash.h

http://www.biostars.org/p/10353/을 통해

---

사용하지 않았지만 Google Sparsehash 가 작동 할 수 있습니다.

---

tcl을 다운로드 하고 검증 된 tcl 해시 함수를 사용하십시오. 그것은 간단합니다. TCL API는 잘 문서화되어 있습니다.

---

Gperf-완벽한 해시 함수 생성기

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

---

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

---

stl has map and hash_map (hash_map is only in some implementations) that are key to value if you are able to use C++.

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

참고URL : https://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c