XPCOM 哈希表指南¶

注意

要深入了解为我们的哈希表提供支持的基础机制，请查看 XPCOM 哈希表技术细节文档。

什么是哈希表？¶

哈希表是一种数据结构，用于存储一组 **项目**。每个项目都有一个 **键** 来标识该项目。通过使用键可以查找、添加和删除哈希表中的项目。哈希表可能看起来像数组，但它们之间存在重要区别

	数组	哈希表
键	整数：数组始终以整数为键，并且必须连续。	任何类型：几乎任何数据类型都可以用作键，包括字符串、整数、XPCOM 接口指针、IIDs 和几乎任何其他东西。键可以是不连续的（例如，您可以存储键为 1、5 和 3000 的条目）。
查找时间	O(1)：查找时间是一个简单的常数	O(1)：查找时间大多是常数，但常数时间可能大于数组查找
排序	已排序：存储已排序；以已排序的方式迭代。	未排序：存储未排序；不能以已排序的方式迭代。
插入/删除	O(n)：从大型数组中添加和删除项目可能很耗时	O(1)：从哈希表中添加和删除项目是一个快速操作
浪费的空间	无：数组是打包结构，因此没有浪费的空间。	一些：哈希表不是打包结构；根据实现，可能会浪费大量的内存。

在它们的实现中，哈希表获取键并应用数学 **哈希函数** 来 **随机化** 键，然后使用哈希来查找哈希表中的位置。好的哈希表实现将自动调整内存中哈希表的大小，如果需要额外的空间，或者如果分配了太多空间。

哈希表对于以下情况很有用

不应在以下情况下使用哈希表

在这些情况下，数组、链接列表或各种树数据结构效率更高。

如果没有 **键** 类型，则应使用 nsTHashSet。

如果有键类型，则应使用 nsTHashMap。

nsTHashMap 是一个具有两个参数的模板。第一个是哈希键，第二个是要存储为映射中值的的数据。大多数情况下，只要 nsTHashMap.h 支持，您可以简单地将原始键类型作为第一个参数传递。如果需要，也可以指定自定义键。有关示例，请参阅 nsHashKeys.h。

nsHashKeys.h 中还有许多更深奥的哈希键类，如果这些类都不满足您的需求，您可以随时自己创建（但请确保您没有重复现有的哈希键类！）。

确定了所需的哈希表和哈希键类后，就可以将它们组合在一起。以下是一些示例

一个将 UTF-8 来源名称映射到 DOM 窗口的哈希表 - nsTHashMap<nsCString, nsCOMPtr<nsIDOMWindow>>
一个将 32 位整数映射到浮点数的哈希表 - nsTHashMap<uint32_t, float>
一个将 nsISupports 指针映射到引用计数的 CacheEntry 的哈希表 - nsTHashMap<nsCOMPtr<nsISupports>, RefPtr<CacheEntry>>
一个将 JSContext 指针映射到 ContextInfo 结构的哈希表 - nsTHashMap<JSContext*, UniquePtr<ContextInfo>>
一个字符串的哈希集 - nsTHashSet<nsString>

所有哈希表类都公开了相同的基本 API。有三个关键方法，Get、InsertOrUpdate 和 Remove，它们分别从哈希表中检索条目、将条目写入哈希表以及从哈希表中删除条目。有关更多详细信息，请参阅 nsBaseHashtable.h。

保存对指针引用的哈希表（nsRefPtrHashtable 和 nsInterfaceHashtable）还具有 GetWeak 方法，该方法返回未添加引用的指针。

请注意，nsRefPtrHashtable、nsInterfaceHashtable 和 nsClassHashtable 是旧版哈希表类型，它们有一些额外的方法，并且没有自动的键类型处理。

所有这些哈希表类都可以通过 Iterator 类进行迭代，使用正常的 C++11 迭代器或使用 Keys() / Values() 范围，并且所有都可以通过 Clear 方法清除。