六、GLib——GHashTable
1 基本概念
1.1 哈希表基本概念
-
哈希表（Hash Table）也叫散列表，哈希表本质上就是一个数组，只不过数组存放的是单一的数据，而哈希表中存放的是键值对，通过Key可以直接找到所映射的Value。
-
key通过哈希函数（hash function）得到数组的索引，进而存取索引位置的值。
-
不同的key通过哈希函数可能得到相同的索引值，此时，产生了哈希碰撞。
-
通过在数组中插入链表或者二叉树，可以解决哈希碰撞的问题。
1.2 哈希表实现原理
-
通过散列函数（映射函数），将key传入函数，计算出数组的下标值。比如以下time33哈希函数：
uint32_t time33(char const *str, int len) { unsigned long hash = 0; for (int i = 0; i < len; i++) { hash = hash *33 + (unsigned long) str[i]; } return (hash & 0x7FFFFFFF) % MAX_SIZE; }具体来说，函数接受一个指向字符串的指针和字符串的长度作为输入。然后，它遍历字符串中的每个字符，将当前哈希值乘以33，对当前所有字符进行如此操作，然后累加起来。最后，通过使用位掩码操作（& 0x7FFFFFFF）来确保返回的哈希值为正数（因为哈希值是无符号整数）。最后取余操作是防止值越界。
-
比如上图的情况，汉字拼音是key，对应具体的汉字，比如相同的拼音（字符串）计算出的值是相同的，就产生了哈希碰撞。为了解决碰撞，实现哈希表可以有以下两种方式：
-
数组 + 链表
-
数组 + 二叉树
以下以链表举例，使用C语言实现。产生哈希碰撞的时候，可以遍历该点的链表（每个数组元素都是链表的头节点），找到对应的key。
#ifndef MAX_SIZE #define MAX_SIZE (1024 ^ 2) // 定义哈系表的范围(也就是通过time_33哈系后的值在跟MAX_SIZE整除，从而限定了范围) // 一个捅，由key和value组成，同时next为链表所用[解决哈系冲突] typedef struct HashNode { char *key; char *value; struct HashNode *next; // 解决Hash冲突 } HashNode; // 一张哈希表，由一个指针组成，该指针起数组作用，内部存储捅的指针 typedef struct HashTable{ struct HashNode **HashNode; // 这是一个指针数组 } HashTable; HashTable *make_HashTable(); HashNode *make_HashNode(char *key, char *value); int login_node(HashTable *ht, HashNode *hn); HashNode *find_node(HashTable *ht, char *key); #endif -
2 GHashTable
-
GHashTable提供了键和值之间的关联，其优化使得在给定键的情况下，可以非常快速地找到关联的值。
-
请注意，插入GHashTable时，键和值都不会被复制，因此它们必须在GHashTable的生命周期内存在。这意味着使用静态字符串是可以的，但应在插入之前使用g_strdup()复制临时字符串（即在缓冲区中创建的字符串和由GTK+小部件返回的字符串）。
-
如果键或值是动态分配的，您必须小心确保在从GHashTable中删除它们时释放它们，并且在它们被新插入到GHashTable中覆盖时也要释放它们。在GHashTable中混合使用静态字符串和动态分配的字符串也不可取，因为这样就很难确定字符串是否应该被释放。
-
要创建一个GHashTable，使用g_hash_table_new()。
-
要将键和值插入到GHashTable中，使用g_hash_table_insert()。
-
要查找与给定键对应的值，使用g_hash_table_lookup()和g_hash_table_lookup_extended()。
-
要删除键和值，使用g_hash_table_remove()。
-
要为每个键和值对调用一个函数，使用g_hash_table_foreach()或使用迭代器迭代哈希表中的键/值对，请参阅GHashTableIter。
-
要销毁GHashTable，使用g_hash_table_destroy()。
总结：
-
GHashTable没有在类型系统注册，但是自定义结构体存在引用计数。所以有g_hash_table_ref和g_hash_table_unref。（除了创建和解引用，只有g_hash_table_destroy会修改引用计数） -
GHashTable多线程不安全。
struct _GHashTable
{
gsize size;
gint mod;
guint mask;
guint nnodes;
guint noccupied; /* nnodes + tombstones */
guint have_big_keys : 1;
guint have_big_values : 1;
gpointer keys;
guint *hashes;
gpointer values;
GHashFunc hash_func;
GEqualFunc key_equal_func;
gatomicrefcount ref_count;
#ifndef G_DISABLE_ASSERT
/*
* Tracks the structure of the hash table, not its contents: is only
* incremented when a node is added or removed (is not incremented
* when the key or data of a node is modified).
*/
int version;
#endif
GDestroyNotify key_destroy_func;
GDestroyNotify value_destroy_func;
};
引用计数：
/* 引用计数+1，此时 ref_count == 1 */
GHashTable* g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func);
/**
* 只要中间不调用 `g_hash_table_ref` ，引用计数就不会改变
*/
/* 除了ref函数，没有其他函数能修改引用计数，所以此时 ref_count == 1，调用unref即可释放GHashTable内存 */
g_hash_table_unref (hash_table);
2.1 创建与释放哈希表
/**
* @brief: 创建一个引用计数为1的新 #GHashTable。
* @hash_func: 这个函数是通过key创建哈希索引值的函数
* 由 @hash_func 返回的哈希索引值用于确定将键存储在 #GHashTable 数据结构中的位置。
* 对于一些常见类型的键，提供了 g_direct_hash()、g_int_hash()、g_int64_hash()、g_double_hash() 和 g_str_hash() 函数。
* 如果 @hash_func 为 %NULL，则使用 g_direct_hash()。
*
* @key_equal_func: 在查找 #GHashTable 中的键时使用。
* 对于最常见类型的键，提供了 g_direct_equal()、g_int_equal()、g_int64_equal()、g_double_equal() 和 g_str_equal() 函数。
* 如果 @key_equal_func 为 %NULL，则键会以类似于 g_direct_equal() 的方式直接比较，但没有函数调用的开销。
* @key_equal_func 被调用时，哈希表中的键作为其第一个参数，要检查的用户提供的键作为其第二个参数。
*
*
* @returns: a new #GHashTable
*
*/
GHashTable* g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func);
/* 解引用，释放内存，整个可调用GHshTable相关API中，除了创建和ref和g_hash_table_destroy函数，没有其他函数更改ref_count值 */
void
g_hash_table_unref (GHashTable *hash_table); /* g_hash_table_destroy也会调用g_hash_table_unref，所以直接使用该解引用函数即可*/
/**
* @brief: 销毁 #GHashTable 中的所有键和值，并将其引用计数减 1。如果键和/或值是动态分配的，
* 您应该先释放它们，或者使用带有销毁通知器的 g_hash_table_new_full() 创建 #GHashTable。
* 在后一种情况下，您提供的销毁函数将在销毁阶段对所有键和值进行调用。
*/
void
g_hash_table_destroy (GHashTable *hash_table)
{
g_return_if_fail (hash_table != NULL);
g_hash_table_remove_all (hash_table);
g_hash_table_unref (hash_table);
}
2.2 哈希表中插入key和value
/**
* @brief: 将新的键和值插入到 #GHashTable 中。
* @key: 要插入的键
* @value: 与键关联的值
* @note:
* 如果键已经存在于 #GHashTable 中，则其当前值将被替换为新值。
* 如果在创建 #GHashTable 时提供了 @value_destroy_func，则旧值将使用该函数释放。
* 如果在创建 #GHashTable 时提供了 @key_destroy_func，则传递的键将使用该函数释放。
*
* 会调用@hash_func函数
*
* 从 GLib 2.40 开始，此函数返回一个布尔值，表示新添加的值是否已经在哈希表中。
* @return：%TRUE 如果键尚不存在
*/
gboolean
g_hash_table_insert (GHashTable *hash_table,
gpointer key,
gpointer value)
2.3 哈希表中查找key对应的value
/**
* @brief: 在 #GHashTable 中查找一个 key 对应的 value
* @hash_table: a #GHashTable
* @key: 要查找的键
* @note: 在 #GHashTable 中查找一个键。请注意，此函数无法区分不存在的键和存在但其值为 %NULL 的键。
* @return: key关联的value，如果未找到键则为 %NULL。
*/
gpointer g_hash_table_lookup (GHashTable *hash_table,
gconstpointer key);