Блог

Я пытаюсь сохранить некоторые данные, используя хэш-таблицы, и я решил использовать glib.

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

Итак, я пытался реализовать аналогичный алгоритм из g_str_hash, но чтобы, когда к ключу уже что-то прикреплено, оно переходило к следующему доступному пространству. Но у меня возникают трудности из-за некоторых вопросов, касающихся типов и того, как это сделать.

   guint hash(char * key, GHashTable *hasht ) {
    unsigned int hash = 5381;
    int c;

    while ((c = *(key  ))) {
      hash = ((hash << 5)   hash)   c;
    }

    //this is where i get lost on how to check if there is alreay something stored using the hash I generated before

    while (g_hash_table_contains(hasht, hash))
    {
      hash  ;
    }
    
    return hash;
  }
 

Су, я был бы очень признателен за помощь в том, как это сделать! Большое вам спасибо!

Если вы просто пытаетесь учиться, внедрение пользовательской хэш-таблицы для этого было бы хорошим опытом. Однако, если вы просто хотите получить какой-то рабочий код, вы чрезмерно усложняете это. Просто используйте a GHashTable из GPtrArray s. Что-то вроде (непроверенный, в основном из памяти, и я действительно не использовал GLib из C годами):

 /* create hash table */
GHashTable* ht = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, g_ptr_array_unref);

for (/* each record in CSV */) {
  GPtrArray* arr = g_hash_table_lookup(ht, record->id);
  if (arr == NULL) {
    /* We don't have an entry for that ID yet */
    arr = g_ptr_array_new_full(1, g_free);
    g_hash_table_insert(ht, g_strdup(record->id), arr);
  }
  g_ptr_array_add(arr, g_strdup(record->value));
}
 

Если вы не находитесь в очень критичном к производительности цикле, это должно быть нормально.

Хеш-таблица работает с использованием массива, где каждый элемент массива является «корзиной». Корзина (индекс массива) для определенного ключа или элемента в хеш-таблице вычисляется из значения хеш-функции для этого элемента. Каждая корзина содержит связанный список элементов, которые имеют одинаковое значение хэша (коллизии хэшей) или NULL, если корзина пуста.

Поэтому требуется, чтобы ваша хэш-функция всегда возвращала одно и то же значение для данного ключа / элемента. В противном случае вы никогда не сможете найти / просмотреть данный ключ. Обратите внимание, что ваша хеш-функция вызывается как при вставке в хеш-таблицу, так и при попытке поиска заданного ключа. С помощью этой хэш-функции вы можете вставить ключ «key1», а затем, когда вы позже попытаетесь выполнить поиск «key1», вы увеличите значение хэша, потому что оно уже присутствует в хэш-таблице, и оно не будет найдено. Вы не должны увеличивать значение хеш-функции на основе того, присутствует ли ключ уже в хеш-таблице.

Для хеш-таблицы также требуется способ определить, равны ли два ключа или нет. Это используется, например, для поиска конкретного элемента, который вы ищете в поиске. Короче говоря, поиск включает в себя поиск корзины для данного ключа с помощью хеш-функции, а затем с помощью функции ‘key_equal’ для поиска конкретного заданного ключа среди всех других ключей в этой корзине. Нечто подобное происходит при вставке, в зависимости от того, допускает ли хеш-таблица несколько одинаковых ключей или нет, и что она делает, когда в хеш-таблице уже существует равный ключ (например, сбой или замена существующего ключа).)

Я раньше не использовал GLib, но, глядя на документы, GLib.HashTable реализует хэш-карту пар ключ / значение. Ключи хэшируются, и каждый ключ имеет связанное значение. Он не допускает дублирования ключей. Вставка дубликата ключа приводит к замене старого.

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

 while (g_hash_table_contains(hasht, hash))
{
  hash  ;
}