XPCOM 哈希表技术细节

注意

本文深入探讨了支持 XPCOM 哈希表的底层机制。其中一些信息非常旧，可能已过时。如果您正在寻找如何使用 XPCOM 哈希表，您应该考虑阅读 XPCOM 哈希表指南。

Mozilla 的哈希表实现

Mozilla 有几种哈希表实现，这些实现经过测试和调整，隐藏了哈希表实现的内部复杂性。

  • PLHashTable - 低级 C API；条目类指针是常量；对于大型条目结构更有效；通常会浪费内存，进行许多小的堆分配。

  • nsTHashtable - 围绕 PLDHash 的低级 C++ 包装器；生成回调函数并自动处理大多数转换。客户端编写自己的条目类，其中可以包含复杂的键和数据类型。

  • nsTHashMap/nsInterfaceHashtable/nsClassHashtable - 简化了将简单键类型映射到简单数据类型的常用模式；客户端不需要声明或管理条目类；nsTHashMap 数据类型是标量，例如 uint64_t；nsInterfaceHashtable 数据类型是 XPCOM 接口；nsClassHashtable 数据类型是由哈希表拥有的类指针。

PLHashTable

PLHashTable 是 NSPR 的一部分。头文件可以在 plhash.h 中找到。

在以下两种情况下，PLHashTable 可能更可取

  • 您需要条目指针保持不变。

  • 存储在表中的条目非常大（大于 12 个字）。

nsTHashtable

要使用 nsTHashtable，您必须声明一个条目类。此条目类包含您要进行哈希处理的键和数据。它还声明了操作键的函数。在大多数情况下，此条目类的函数可以完全内联。有关条目类的示例，请参阅 nsHashKeys.h 中的声明。

模板参数是条目类。构造完成后，使用函数 PutEntry/GetEntry/RemoveEntry 来修改哈希表。Iterator 类将执行迭代，但请注意，迭代将以看似随机的顺序发生（没有排序）。

  • nsTHashtable 可以分配在栈上、作为类成员或在堆上。

  • 当向哈希表添加或从中删除项目时，条目指针可以并且确实会发生变化。不要长时间保存对条目的指针。

  • 因此，nsTHashtable 本身不是线程安全的。如果您在多线程环境中使用哈希表，则必须根据需要提供锁定。

在使用 nsTHashtable 之前，请查看 nsBaseHashtable 及其相关类是否适合您。它们更容易使用，因为您不必声明条目类。如果您将简单键类型哈希到简单数据类型，它们通常是更好的选择。

nsBaseHashtable 及其相关类：nsTHashMap、nsInterfaceHashtable 和 nsClassHashtable

这些 C++ 模板提供了用于使用哈希表的高级接口，隐藏了底层实现的大部分复杂性。它们提供了以下功能

  • 无需使用条目类即可完成哈希表操作，使代码更易于阅读

  • 可选的线程安全：哈希表可以在表周围管理读写锁

  • 预定义的键类提供字符串/接口的自动清理

  • nsInterfaceHashtable 和 nsClassHashtable 自动释放/删除对象以避免泄漏。

nsBaseHashtable 不直接使用；根据您要存储的数据类型选择三个派生类之一。KeyClass 来自 nsHashKeys.h，并且对于所有三个类都是相同的

  • nsTHashMap<KeyClass, DataType> - DataType 是简单类型，例如 uint32_t 或 bool。

  • nsInterfaceHashtable<KeyClass, Interface> - Interface 是 XPCOM 接口，例如 nsISupports 或 nsIDocShell

  • nsClassHashtable<KeyClass, T> - T 是任何 C++ 类。哈希表存储指向对象的指针，并在删除条目时删除该对象。

要阅读的重要文件是 nsBaseHashtable.h 和 nsHashKeys.h。这些类可以在栈上、作为类成员或在堆上使用。

将 nsTHashtable 用作哈希集

哈希集仅跟踪键的存在：它不将数据与键关联。这可以使用 nsTHashtable<nsSomeHashKey> 完成。合适的条目是 GetEntry 和 PutEntry。