哈希表

概念

到目前为止，本教程只介绍了有序容器，在其中插入的条目会保持特定次序不变。哈希表 是另一类容器，也称为“映射”、“联合数组（associative array）” 或者“目录（dictionary）”。

正如语文辞典使用一个定义来关联一个词，哈希表使用一个 键（key） 来唯一标识一个 值（value）。哈希表可以根据键非常快速地执行插入、查找和删除操作；实际上，如果使用得当，这些可以都是常数时间 —— 也就是 O(1) —— 操作。这比从一个有序列表中查找或删除条目快得多，那是 O(n) 操作。

哈希表之所以能快速执行操作，是因为它们使用 散列函数 来定位键。散列函数获得一个键并为其计算一个唯一的值，称为 散列值（hash）。例如，一个散列函数可以接受一个词并将那个词中的字母数作为散列值返回。那是个不好的散列函数，因为 “fiddle”和“faddle”将会散列为相同的值。

当散列函数为不同的键返回相同的散列值时，取决于哈希表的实现会发生各种不同的事情。哈希表可以使用第二个值覆盖第一个值，也可以将值放入一个列表，或者或以简单地抛出一个错误。

注意，哈希表不是必然比列表更快。如果拥有的条目较少 —— 少于一打左右 —— 那么使用有序的集合会获得更好的性能。那是因为，尽管在哈希表中存储和获取数据需要常数时间，那个常数时间值可能会很大，因为计算条目的散列值相对于反引用一两个指针会是一个较慢的过程。对于较小的值，简单地遍历有序列表会比进行散列计算更快。

无论何时，重要的是在选择容器时要考虑自己应用程序的具体数据存储需要。如果应用程序很明显需要某种容器，那么没有理由不去使用它。




一些简单的哈希表操作

这里是一些示例，可以生动地展示以上的理论：


//ex-ghashtable-1.c
#include <glib.h>
int main(int argc, char** argv) {
 GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
 g_hash_table_insert(hash, "Virginia", "Richmond");
 g_hash_table_insert(hash, "Texas", "Austin");
 g_hash_table_insert(hash, "Ohio", "Columbus");
 g_printf("There are %d keys in the hash/n", g_hash_table_size(hash));
 g_printf("The capital of Texas is %s/n", g_hash_table_lookup(hash, "Texas"));
 gboolean found = g_hash_table_remove(hash, "Virginia");
 g_printf("The value 'Virginia' was %sfound and removed/n", found ? "" : "not ");
 g_hash_table_destroy(hash);
 return 0;
}

***** Output *****

There are 3 keys in the hash
The capital of Texas is Austin
The value 'Virginia' was found and removed


有很多新东西，所以给出一些注解：

    * 对 g_hash_table_new 的调用指定了这个哈希表将使用字符串作为键。函数 g_str_hash 和 g_str_equal 是 GLib 的内置函数，因为这很常用。其他内置 散列/等同（equality） 函数包括 g_int_hash /g_int_equal（使用整数作为键）以及 g_direct_hash/g_direct_equal（使用指针作为键）。
    * GLists 和 GSLists 拥有一个 g_[container]_free 函数来清除它们；可以使用 g_hash_table_destroy 来清空 GHashTable。
    * 当尝试使用 g_hash_table_remove 删除 键/值 对时，会获得一个 gboolean 返回值，表明键是否找到并删除。gboolean 是 真/假 值的一个简单的跨平台 GLib 实现。
    * g_hash_table_size 返回哈希表中键的数目。





插入和替换值

当使用 g_hash_table_insert 插入键时，GHashTable 首先检查那个键是否已经存在。如果已经存在，那么那个值会被替换，而键不会被替换。如果希望同时替换键和值，那么需要使用 g_hash_table_replace。它稍有不同，因此在下面同时展示了二者：


//ex-ghashtable-2.c
#include <glib.h>
static char* texas_1, *texas_2;
void key_destroyed(gpointer data)
{
 g_printf("Got a key destroy call for %s/n", data == texas_1 ? "texas_1" : "texas_2");
}
int main(int argc, char** argv)
{

 GHashTable* hash = g_hash_table_new_full(g_str_hash, g_str_equal,  (GDestroyNotify)key_destroyed, NULL);
 
 texas_1 = g_strdup("Texas");
 texas_2 = g_strdup("Texas");
 g_hash_table_insert(hash, texas_1, "Austin");
 g_printf("Calling insert with the texas_2 key/n");
 g_hash_table_insert(hash, texas_2, "Houston");
 g_printf("Calling replace with the texas_2 key/n");
 g_hash_table_replace(hash, texas_2, "Houston");
 g_printf("Destroying hash, so goodbye texas_2/n");
 g_hash_table_destroy(hash);
 g_free(texas_1);
 g_free(texas_2);
 return 0;
}

***** Output *****

Calling insert with the texas_2 key
Got a key destroy call for texas_2
Calling replace with the texas_2 key
Got a key destroy call for texas_1
Destroying hash, so goodbye texas_2
Got a key destroy call for texas_2


从输出可以看到，当 g_hash_table_insert 尝试插入与现有键相同的字符串（Texas）时， GHashTable 只是简单的释放传递进来的键（texas_2），并令当前键（texas_1）保持不变。但是当 g_hash_table_replace 做同样的事情时，texas_1 键被销毁，并在使用它的地方使用 texas_2 键。更多注解：

    * 当创建新的 GHashTable 时，可以使用 g_hash_table_full 来提供一个 GDestroyNotify 实现，在键被销毁时调用它。这让您能够为那个键进行完全的资源清除，或者（在本例中）去查看在键变化时实际发生的事情。
    * 在前面的 GSList 部分已经出现过 g_strdup；在这里使用它来分配字符串 Texas 的两个拷贝。可以发现，GHashTable 函数 g_str_hash 和 g_str_equal 正确地检测到，尽管指针指向不同的内存位置，但实际上字符串是相同的。为了避免内存泄漏，在函数的末尾必须释放 texas_1 和 texas_2 当然，在本例中这并不重要，因为程序会退出，但是无论如何能够清除是最好的。





遍历 键/值 对

有时需要遍历所有的 键/值 对。这里是如何使用 g_hash_table_foreach 来完成那项任务：


//ex-ghashtable-3.c
#include <glib.h>
void iterator(gpointer key, gpointer value ,gpointer user_data)
{
 g_printf(user_data, *(gint*)key, value);
}



int main(int argc, char** argv)
{
 GHashTable* hash = g_hash_table_new(g_int_hash, g_int_equal);
 
gint* k_one = g_new(gint, 1), *k_two = g_new(gint, 1), *k_three = g_new(gint, 1);
*  k_one = 1, *k_two=2, *k_three = 3;

 g_hash_table_insert(hash, k_one, "one");
 g_hash_table_insert(hash, k_two, "four");
 g_hash_table_insert(hash, k_three, "nine");
 
 g_hash_table_foreach(hash, (GHFunc)iterator, "The square of %d is %s  /n");
 g_hash_table_destroy(hash);
 return 0;
}


***** Output *****

The square of 1 is one
The square of 2 is four
The square of 3 is nine


在这个示例中有一些细微的不同之处：

    * 可以发现，使用 GLib 提供的散列函数 g_int_hash 和 g_int_equal 让您能够使用指向整数的指针作为键。本示例使用的是整数的 GLib 跨平台抽象： gint。
    * g_hash_table_foreach 与您已经了解的 g_slist_foreach 和 g_list_foreach 函数非常类似。唯一的区别是，传递到 g_hash_table_foreach 的 GHFunc 要接受三个参数，而不是两个。在本例中，传递进入一个用来格式化键和字符串的打印的字符串作为第三个参数。另外，尽管在本示例时键恰巧是以它们插入的顺序打印出来，但绝对不保证那个键插入的顺序会被保留。





查找条目      //(//(((((((((((((((((((未完全理解))))))))))))))))))))))))))))))))

使用 g_hash_table_find 函数来查找某个特定的值。这个函数支持查看每一个 键/值 对，直到定位到期望的值。这里是一个示例：


//ex-ghashtable-4.c
#include <glib.h>
void value_destroyed(gpointer data)
{
 g_printf("Got a value destroy call for %d/n", GPOINTER_TO_INT(data));
}

gboolean finder(gpointer key, gpointer value, gpointer user_data)
{
 return (GPOINTER_TO_INT(key) + GPOINTER_TO_INT(value)) == 42;
}


int main(int argc, char** argv)
{
 GHashTable* hash = g_hash_table_new_full(g_direct_hash, g_direct_equal,  NULL,  (GDestroyNotify)value_destroyed);
 
 g_hash_table_insert(hash, GINT_TO_POINTER(6), GINT_TO_POINTER(36));
 g_hash_table_insert(hash, GINT_TO_POINTER(10), GINT_TO_POINTER(12));
 g_hash_table_insert(hash, GINT_TO_POINTER(20), GINT_TO_POINTER(22));
 
 gpointer item_ptr = g_hash_table_find(hash, (GHRFunc)finder, NULL);
 gint item = GPOINTER_TO_INT(item_ptr);
 g_printf("%d + %d == 42/n", item, 42-item);
 
 g_hash_table_destroy(hash);
 return 0;
}

***** Output *****

36 + 6 == 42
Got a value destroy call for 36
Got a value destroy call for 22
Got a value destroy call for 12


照例，本示例介绍了 g_hash_table_find 以及其他一些内容：

    * GHRFunc 返回 TRUE 时，g_hash_table_find 返回第一个值。如果 GHRFunc 作用于任意条目都都不返回 TRUE（这表明没有找到合适的条目），则它返回 NULL。
    * 本示例介绍了另一组内置的 GLib 散列函数：g_direct_hash 和 g_direct_equal。这组函数支持使用指针作为键，但却没有尝试去解释指针背后的数据。由于要将指针放入 GHashTable，所以需要使用一些便利的 GLib 宏（GINT_TO_POINTER 和 GPOINTER_TO_INT）来在整数与指针之间进行转换。
    * 最后，本示例创建了 GHashTable，并给予它一个 GDestroyNotify 回调函数，以使得您可以查看条目是何时被销毁的。大部分情况下您会希望在一个与此类似的函数中释放某些内存，不过出于示例的目的，这个实现只是打印出一条消息。





难处理的情形：从表中删除

偶尔可能需要从一个 GHashTable 中删除某个条目，但却没有获得 GHashTable 所提供的任意 GDestroyNotify 函数的回调。要完成此任务，或者可以根据具体的键使用 g_hash_table_steal，或者根据所有匹配某个条件的键使用 g_hash_table_foreach_steal。


//ex-ghashtable-5.c
#include <glib.h>
gboolean wide_open(gpointer key, gpointer value, gpointer user_data)
{
 return TRUE;
}

void key_destroyed(gpointer data)
{
 g_printf("Got a GDestroyNotify callback/n");
}

int main(int argc, char** argv)
{
 GHashTable* hash = g_hash_table_new_full(g_str_hash, g_str_equal, (GDestroyNotify)key_destroyed,(GDestroyNotify)key_destroyed);
 
 g_hash_table_insert(hash, "Texas", "Austin");
 g_hash_table_insert(hash, "Virginia", "Richmond");
 g_hash_table_insert(hash, "Ohio", "Columbus");
 g_hash_table_insert(hash, "Oregon", "Salem");
 g_hash_table_insert(hash, "New York", "Albany");
 
 g_printf("Removing New York, you should see two callbacks/n");
 g_hash_table_remove(hash, "New York");
 if (g_hash_table_steal(hash, "Texas"))
 {
  g_printf("Texas has been stolen, %d items remaining/n", g_hash_table_size(hash));
 }
 g_printf("Stealing remaining items/n");
 g_hash_table_foreach_steal(hash, (GHRFunc)wide_open, NULL);
 g_printf("Destroying the GHashTable, but it's empty, so no callbacks/n");
 g_hash_table_destroy(hash);
 return 0;
}

***** Output *****

Removing New York, you should see two callbacks
Got a GDestroyNotify callback
Got a GDestroyNotify callback
Texas has been stolen, 3 items remaining
Stealing remaining items
Destroying the GHashTable, but it's empty, so no callbacks






高级查找：找到键和值

针对需要从表中同时获得键和值的情况，GHashTable 提供了一个 g_hash_table_lookup_extended 函数。它与 g_hash_table_lookup 非常类似，但要接受更多两个参数。这些都是“out”参数；也就是说，它们是双重间接指针，当数据被定位时将指向它。这里是它的工作方式：


//ex-ghashtable-6.c
#include <glib.h>
int main(int argc, char** argv)
{
 GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
 
 g_hash_table_insert(hash, "Texas", "Austin");
 g_hash_table_insert(hash, "Virginia", "Richmond");
 g_hash_table_insert(hash, "Ohio", "Columbus");
 
 char* state = NULL;
 char* capital = NULL;
 char** key_ptr = &state;
 char** value_ptr = &capital;
 
 gboolean result = g_hash_table_lookup_extended(hash, "Ohio", (gpointer*)key_ptr, (gpointer*)value_ptr);
 if (result)
  {
  g_printf("Found that the capital of %s is %s/n", capital, state);
 }
 if (!g_hash_table_lookup_extended(hash, "Vermont", (gpointer*)key_ptr, (gpointer*)value_ptr))
 {
  g_printf("Couldn't find Vermont in the hash table/n");
 }
 
 g_hash_table_destroy(hash);
 return 0;
}

***** Output *****

Found that the capital of Columbus is Ohio
Couldn't find Vermont in the hash table


初始化能够接收 键/值 数据的变量有些复杂，但考虑到它是从函数返回多于一个值的途径，这可以理解。注意，如果您为后两个参数之一传递了 NULL，则 g_hash_table_lookup_extended 仍会工作，只是不是填充 NULL 参数。




每个键多个值

到目前为止已经介绍了每个键只拥有一个值的散列。不过有时您需要让一个键持有多个值。当出现这种需求时，使用 GSList 作为值并及 GSList 添加新的值通常是一个好的解决方案。不过，这需要稍多一些工作，如本例中所示：


//ex-ghashtable-7.c
#include <glib.h>
void print(gpointer key, gpointer value, gpointer data)
{
 g_printf("Here are some cities in %s: ", key);
 g_slist_foreach((GSList*)value, (GFunc)g_printf, NULL);
 g_printf("/n");
}

void destroy(gpointer key, gpointer value, gpointer data)
 {
 g_printf("Freeing a GSList, first item is %s/n", ((GSList*)value)->data);
 g_slist_free(value);
}

int main(int argc, char** argv)
 {
 GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
 
 g_hash_table_insert(hash, "Texas",  g_slist_append(g_hash_table_lookup(hash, "Texas"), "Austin "));
 
 g_hash_table_insert(hash, "Texas",  g_slist_append(g_hash_table_lookup(hash, "Texas"), "Houston "));
 
 g_hash_table_insert(hash, "Virginia",  g_slist_append(g_hash_table_lookup(hash, "Virginia"), "Richmond "));
 
 g_hash_table_insert(hash, "Virginia",  g_slist_append(g_hash_table_lookup(hash, "Virginia"), "Keysville "));
 
 g_hash_table_foreach(hash, print, NULL);
 g_hash_table_foreach(hash, destroy, NULL);
 g_hash_table_destroy(hash);
 return 0;
}
***** Output *****

Here are some cities in Texas: Austin Houston
Here are some cities in Virginia: Richmond Keysville
Freeing a GSList, first item is Austin
Freeing a GSList, first item is Richmond


g_slist_append 接受 NULL 作为 GSList 的合法参数，示例中的“insert a new city”代码利用了这一事实；它不需要检查这是不是添加到给定州的列表的第一个城市。

当销毁 GHashTable 时，必须记住在释放哈希表本身之前先释放那些 GSList。注意，如果没有在那些列表中使用静态字符串，这会更为复杂；在那种情况下需要在释放列表本身之前先释放每个 GSList 之中的每个条目。这个示例所展示的内容之一是各种 foreach 函数多么实用 —— 它们可以节省很多输入。




现实应用

这里是如何使用 GHashTables 的样例。

在 Gaim 中：

    * gaim-1.2.1/src/buddyicon.c 使用 GHashTable 来保持对“好友图标（buddy icons）”的追踪。键是好友的用户名，值是指向 GaimBuddyIcon 结构体的指针。
    * gaim-1.2.1/src/protocols/yahoo/yahoo.c 是这三个应用程序中唯一使用 g_hash_table_steal 的地方。它使用 g_hash_table_steal 作为构建帐号名到好友列表的映射的代码片断的组成部分。

在 Evolution 中：

    * evolution-2.0.2/smime/gui/certificate-manager.c 使用 GHashTable 来追踪 S/MIME 证书的根源；键是组织名，值是指向 GtkTreeIter 的指针。
    * evolution-data-server-1.0.2/calendar/libecal/e-cal.c 使用 GHashTable 来追踪时区；键是时区 ID 字符串，值是某个 icaltimezone 结构体的字符串描述。

在 GIMP 中：

    * gimp-2.2.4/libgimp/gimp.c 使用 GHashTable 追踪临时的过程。在整个代码基（codebase）中唯一使用 g_hash_table_lookup_extended 的地方，它使用 g_hash_table_lookup_extended 调用来找到某个过程，以使得在删除那个过程之前能首先释放散列键的内存。
    * gimp-2.2.4/app/core/gimp.c 使用 GHashTable 来保存图像；键是图像的 ID（一个整数），值是指向 GimpImage 结构体的指针。