C99의 HashTable 및 Vector와 같은 데이터 구조

C99의 독립 벡터 데이터 구조에 의존하는 해시 테이블을 만들고 싶습니다. OO의 도움으로 C++에서이 작업을 수행 할 수 있지만 구조체와 공용체를 사용하여이 방법에 접근하는 방법을 확신 할 수 없습니다.C99의 HashTable 및 Vector와 같은 데이터 구조

링크 된 예제에는 매우 복잡한 해싱 함수가있는 해시 테이블 구현이 포함되지 않는 것이 좋습니다. 특히 충돌이나 저장 효율성에 대해 신경 쓰지 않습니다. 나는 단지 진행 방법에 대한 조언이나 각각의 데이터 구조의 기능보다는 형태를 보여주는 간단한 예제를 원한다.

출처

2011-10-28 SirensOfTitan

완전히 일반적인 방법으로 증가하는 해시 테이블을 구현할 것이라는 것을 정확하게 추론하면 void 포인터가 많이 필요합니다.

typedef struct { 
    size_t capacity, nelems; 
    void **contents; 
} Vector; 

enum { INITIAL_CAPACITY = 256 }; 

Vector *make_vector() 
{ 
    Vector *v = malloc(sizeof(Vector)); 
    if (v == NULL) 
     return NULL; 
    v->capacity = INITIAL_CAPACITY; 
    v->contents = malloc(sizeof(void *) * v->capacity); 
    if (v->contents == NULL) { 
     free(v); 
     return NULL; 
    } 
    v->nelems = 0; 
    return v; 
} 

// exercise for the reader 
int vector_append(Vector *, void *); 
void *vector_at(Vector const *);

는 일반적인 해시 기능을 사용하면 크기에 전달해야 즉, 프로토 타입 size_t hash(void const *, size_t)을 가질 것을 유의 사항 : 벡터는 그냥 입력이 많이 걸립니다, 너무 열심히하지 않습니다.

(사이드 노트 : 놓치지 않을 C++의 OOP 기능은 템플릿, 구매하는 유형 안전성, 연산자 오버로딩과 같은 구문 설탕입니다. 자세한 예제는 OpenBSD의 ohash 라이브러리를보십시오.)

출처

2011-10-28 19:22:10