Правильное распределение памяти

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

Нет смысла выделять все 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;
}

Этот код:

• Распределяет структуру hash_table для хранения таблицы
• Инициализирует его размер с указанной емкостью
• Выделяет массив указателей сегмента правильной длины
• Гарантирует, что каждый указатель сегмента равен NULL (что не может быть правильно сделано с помощью memset (), так как небезопасно предполагать, что "все биты ноль" - это то, как NULL выглядит в памяти)
• Использует sizeof везде, где это возможно, но не для типов, поэтому без скобок
• Не приводит к возвращаемому значению malloc(), так как это никогда не было хорошей идеей в C
• Не проверяет возвращаемое значение malloc (), конечно, вы должны сделать это в реальном коде

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

Answer 2

Есть несколько вещей, которые мешают твоему typedef. Предполагая, что вы используете MSVC.

Простой способ объявить типы, которые у вас есть, был бы что-то вроде:

Этот typedef включает тип _type {}, * ptype; формат, который объявляет тип и указатель на ваш пользовательский тип одновременно. Если вы видите внизу в hash_table, вы можете использовать таблицу pbucket *, которая устраняет лишние символы *** в вашем коде и может помочь при выполнении динамического выделения (помогите настолько, что вы будете уверены в том, что выделяете и т. ). Ваш оригинальный typedef, если вы смотрели, имел typedef struct bucket {} 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;

Answer 3

Не совсем. Предполагая, что это 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;
 }

РЕДАКТИРОВАТЬ: я установил свое ведро * стол на ведро **

EDIT2: я избавился от memsets и добавил проверку ошибок для malloc.

Answer 4

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);

В любом случае, я немного ржавый в Си, так что возьми это с крошкой соли.