Могу ли я использовать один указатель для моей хэш-таблицы в C?

Question

Я хочу реализовать хеш-таблицу следующим образом:

struct list
{ 
 char *string;
 struct list *next; 
};

struct hash_table
{
 int size;     /* the size of the table */
 struct list **table; /* the table elements */
}; 

Вместо struct hash_table, как указано выше, я могу использовать:

struct hash_table
{
 int size;              /* the size of the table */
 struct list   *table; /* the table elements */
}; 

То есть я могу просто использовать один указатель вместо двойного указателя для элементов хеш-таблицы? Если да, пожалуйста, объясните разницу в способе хранения элементов в таблице?

Answer 1

Ну, это зависит. Если вы посмотрите на таблицу [i], как вы узнаете, пуста она или нет? Если вы используете list **, тогда table [i] будет type list *, и поэтому вы можете легко определить, является ли он пустым, если он нулевой. Если вы используете тип list *, то таблица [i] является списком, и поэтому, если вы не используете нулевое, пустое или какое-либо другое значение для ключа в качестве значения стража, указывающего, что список пуст, он не будет работать. Так что, да, вы можете использовать список *, но тогда вам нужно добавить дополнительное условие стража, которое также может ограничивать типы ключей, которые вы разрешаете. В качестве альтернативы, вы можете просто проигнорировать первый элемент списка [i], однако это будет расточительно. Я также должен отметить, что использование list * вместо list ** затрудняет вставку элемента в начало таблицы [i]; если вы используете тип списка **, то вам просто нужно установить следующий указатель новой записи на текущее значение таблицы [i], а затем присвоить таблице [i] адрес новой выделенной записи. Если вы используете тип list *, вам нужно вставить элемент между таблицей [i] и таблицей [i] -> next, что делает логику для вставки излишне сложной.

Кроме того, я должен добавить, что определение вашей хеш-таблицы неверно. Хеш-таблица должна отображать один набор элементов в другой. Ваша структура списка имеет одно значение. Ему нужен и ключ, и значение. Лучшим объявлением для хеш-таблицы будет следующее:

typedef struct HashTableEntry
{
    char* key;
    void* value;
    struct HashTableEntry* next;
} HashTableEntry;

typedef struct HashTable
{
     HashTableEntry** entries;
     int capacity; // size of entries
     int length; // number of key/value pairs currently in map
} HashTable;

Answer 2

Используя двойной указатель, **table, после выделения памяти вы можете ссылаться на массив элементов, например: table[2]. Затем вы можете получить доступ к элементу хеш-таблицы напрямую, без необходимости просматривать связанный список.

В качестве альтернативы, если вы используете только один указатель, *table, вы сможете ссылаться только на один элемент. Таким образом, в основном вам нужно будет использовать структуру данных, такую ​​как связанный список (ick), для хранения элементов вашей хеш-таблицы - так же, как вы настроили list структуру данных.

Я не рекомендую использовать один указатель, так как вам придется выполнять обход линейного списка для выполнения каких-либо операций с вашей хеш-таблицей. Другими словами, чтобы добавить элемент, вам придется пройти по связанному списку, чтобы найти элемент n, а не просто получить к нему прямой доступ. Поскольку ожидается, что операции с хеш-таблицей будут выполняться быстро (O), эта реализация исключает преимущество использования хеш-таблицы. Вы можете также использовать связанный список в этой точке.