적절한 메모리 할당

Question

나는 다음과 같은 구성을 가지고 있습니다 :

typedef struct bucket {
    char *key;
    ENTRY *data;
    struct bucket *next;
} bucket;

typedef struct {
    size_t size;
    bucket **table;
} hash_table;

하지만 메모리를 할당하는 방법을 모르겠습니다.나는 시도했다:

hash_table* ht = malloc(sizeof(hash_table)*101);

101개 항목에 대한 해시 테이블을 생성하려고 했지만 작동하지 않습니다!누구든지 나를 도와줄 수 있나요?정말 감사하겠습니다!

Answer 1

좀 빠지는.이것이 C라고 가정하면 아마도 다음과 같은 함수를 만들고 싶을 것입니다.

 hash_table* init_table(size_t size) {
     size_t i;
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table));
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)malloc(sizeof(bucket*)*size);
     if (ht->table == NULL) {
         free(ht);
         return NULL;
     }
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

해당 구조체에 다른 필드가 필요할 수도 있습니다.

까다롭게 작업하고 버킷을 다시 할당하지 않으려면 다음을 수행할 수 있습니다.

 hash_table* init_table(size_t size) {
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table)+sizeof(bucket)*size);
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)(ht+1);
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

편집하다:내 버킷* 테이블을 버킷**으로 수정했습니다.

편집2:memset을 제거하고 malloc에 ​​대한 오류 검사를 추가했습니다.

Answer 2

101 (또는 많은) 버킷을 선불로 할당하는 것은 의미가 없으며, 테이블에 새 데이터를 삽입 할 때 일반적으로 한 번에 하나씩 할당 할 것입니다.

그것 하다 고정 된 크기를 갖는 해시 어레이를 사전 할당하는 것이 좋습니다. 버킷 포인터 배열, 버킷의 배열이 아니므로 답이 잘못되었습니다.

고정 크기의 버킷 어레이가있는 빈 해시 테이블을 만들기 위해 이와 같은 것이 있습니다.

hash_table * hash_table_new(size_t capacity)
{
  size_t i;

  hash_table *t = malloc(sizeof *t);
  t->size = capacity;
  t->bucket = malloc(t->size * sizeof *t->bucket);
  for(i = 0; i < t->size; i++)
    t->bucket[i] = NULL;
  return t;
}

이 코드 :

• 테이블을 고정하기 위해 해시 가능한 구조를 할당합니다
• 크기가 표시된 용량으로 초기화됩니다
• 적절한 길이의 버킷 포인터 배열을 할당합니다.
• 각 버킷 포인터가 NULL인지 확인하십시오 (Memset ()로 제대로 수행 할 수 없습니다. "All Bits Zero"가 Null이 메모리에서 보이는 방식이라고 가정하는 것이 안전하지 않기 때문에).
• 용도 sizeof 가능할 때마다 유형이 없으므로 괄호 안 함
• 반환 값을 시전하지 않습니다 malloc(), C에서는 결코 좋은 생각이 아닙니다.
• Malloc ()의 반환 값을 확인하지 않으므로 실제 코드로 수행해야합니다.

실제 해시 삽입물을 수행하려면 두 번째 함수가 필요합니다. 그러면 새 버킷을 할당하고 키에서 해시 값을 계산하고 해시 테이블 배열에서 올바른 위치를 선택하고 새 항목을 삽입해야합니다.

Answer 3

그만큼 hash_table 항상만있을 것입니다 sizeof(hash_table) 바이트가 큰. 그만큼 table 요소는 다양한 포이 인터 배열에 대한 포인터입니다. bucket 집단. 따라서 다음과 같은 것이 필요합니다.

hash_table* ht = malloc(sizeof(hash_table));
ht->size = 101;
ht->table = malloc(sizeof(bucket*)*ht->size);

그러나 나는 그와 함께 제공되는 초기화 방법이있을 수 있다고 생각하며 다음과 같은 일을 할 수 있습니다.

hash_table* ht = alloc_hash_table(101);

어쨌든, 나는 C에서 녹슬 었으므로 소금 한 알로 가져 가십시오.

Answer 4

Typedef와 함께 몇 가지가 있습니다. MSVC 사용을 가정합니다.

여기에있는 유형을 선언하는 쉬운 방법은 같은 것입니다.

이 typedef는 _type {} 유형, *ptype; 형식과 사용자 정의 유형에 대한 포인터를 동시에 선언하는 형식. Hash_table에서 아래로 표시되면 Pbucket *테이블을 사용할 수 있습니다.이 테이블은 코드에서 추가 ***를 제거하고 동적 할당을 수행 할 때 도움이 될 수 있습니다 (할당하는 것 등에 대해 머리를 똑바로 유지할 수 있도록 도와주십시오. ). 원래 typedef, typedef struct bucket {} bucket;을 보았을 때, typedef를 지정할 때 거기에있는 두 개의 "버킷"이름 중 하나를 최소한 수정해야합니다.

C ++ 빌드 설정을 사용하는 경우 캐스트해야합니다. 일반 C를 사용하는 경우 캐스트가 필요하지 않을 수 있으므로 Malloc 라인이 필요합니다 (다음 Typedef 변경 사항 포함).

hash_table* ht = (phash_table) malloc(sizeof(hash_table)*101);

어느 쪽이든,이 스 니펫은 당신에게 효과적입니다.

typedef struct _bucket {    
    char *key;    
    void *data;    
    _bucket *next;
} bucket, *pbucket;

typedef struct _hash_table {    
    size_t size;    
    pbucket *table;
}hash_table, *phash_table;