나는 그 객체를 링크리스트가 아닌 (2 차원) 배열로 저장하는 C에서의 해시 테이블 구현을 찾고있다. 즉, 충돌이 발생하면 충돌을 일으키는 개체가 연결 목록의 헤드 및 첫 번째 요소로 푸시되기보다는 다음 사용 가능한 행 인덱스에 저장됩니다.배열 (대 링크 된 목록) C에서 해시 테이블 구현을 찾고
더하기, 개체 자체는 포인터로 참조되기보다는 해시 테이블에 복사해야합니다. (객체는 프로그램의 전체 수명 동안 생기지 않지만 표는 수행합니다).
이러한 구현에는 심각한 효율성 문제가있을 수 있으며 "해싱의 표준 방식"이 아니라는 것을 알고 있습니다. 그러나 저는 매우 특별한 시스템 구조에서 작업 할 때 이러한 특성이 필요합니다.
감사합니다.
슈퍼 간단한 구현 :
char hashtable[MAX_KEY][MAX_MEMORY];
int counts[MAX_KEY] = {0};
/* Inserting something into the table */
SomeStruct* some_struct;
int hashcode = compute_code(some_struct);
int size = sizeof(SomeStruct);
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size);
++counts[hashcode];
MAX_MEMORY에 대해 확인하는 것을 잊지 마십시오.
와우, 단순한 (그리고 꽤 :) 접근 방식을 생각해 본적이 없다. 만약 내가 그것에 약간의 기능을 추가한다면, 정말로 효과가있을 수있다. 고마워요! – kingusiu
내 시스템에서는 동적 메모리 할당이 허용되지 않습니다. 따라서 데이터 (합계 개체 수와 최대 예상 충돌 수)에 합당한 전면 배열 범위와 개체에 대한 사용자 지정 해시 함수를 정의하여 자신의 해시 테이블을 구현하는 것이 가장 좋습니다.
C가 아니지만 C++이지만 Google Sparse Hash을 살펴보세요. 몇 가지 아이디어가 있습니다. 중요한 요구 사항은 저장되는 객체가 null 일 수있는 방법이 있다는 것입니다.
구현을위한 비정상적이고 구체적인 요구 사항이 있으므로 최선을 다해 직접 구현을 작성하는 것이 좋습니다. 그럼에도 불구하고 흥미로운 질문 인 –
+1. –