65.9K
CodeProject 正在变化。 阅读更多。
Home

AHash： 一组简单的 C++ 哈希模板

AngusEm
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.31/5 (9投票s)

2008年2月4日

CPOL

9分钟阅读

viewsIcon

55725

downloadIcon

727

一组易于理解和实现的轻量级哈希表模板。

引言

我曾在一个项目中处理大约1000条记录。最终，这些记录的数量增加到数千条。在某些情况下，处理这些数据的例程的时间复杂度为O(n2)。使用数组随机访问这些记录不再可行。是时候回顾我的计算机科学课程笔记，处理一个更令人兴奋的数据结构了。你可能也正处于同样的情况。（我现在已经不在那种情况了。现在我需要处理几十万条记录了！）

在我寻找可以借鉴的已有工作成果时，我发现唯一认真的C++哈希模板类是SGI在STL扩展中的。就像STL的许多部分一样，我觉得它很难理解。与STL不同的是，我觉得它也很难使用。如果你有一个轻量级的任务要执行，你必须经历一个相对繁琐的过程来定义这个，实现那个，等等。我想要一些可以快速定义和实例化的东西——我必须自己写。

我的哈希表为什么比SGI的好

  1. 你可以轻松实现它们，而无需太多麻烦：最常用的模板的实现只需派生一个类并实现3个纯虚方法，平均每个方法大约只有3行简短的代码。我编写的实现，每个方法只需要1行代码。
  2. 你可以快速熟悉它们：更容易理解你的代码部分在做什么，以及你如何编写它们所产生的后果。
  3. 如果你想变得有冒险精神，你可以在优化和哈希函数上获得更多控制权。

SGI的哈希表为什么比我的好

  1. SGI的功能更丰富：例如，SGI吹嘘其哈希表的桶数组是自适应的。这对于我的哈希表所扮演的角色来说是不必要的。你必须自己设置数组大小，一旦设置好，就不能再改变了。（测试版不再有这个限制。）
  2. 我的哈希表性能可能不是最优的：我只是一名中高级程序员，我相信SGI的人知道他们在做什么。虽然我对优化、编译器等方面有深刻的理解，但仍有可能我遗漏了什么。

限制

有些其他哈希表可以做到的事情，而这个做不到

  • 键必须是唯一的：我相信SGI的hash_multiset没有这个限制。如果你尝试添加一个键已经存在于表中的元素，那么在随机访问查找中只会引用第一个键。
  • 桶数组大小只能设置一次：如上所述，我的哈希表的使用方式不需要调整数组。在某些情况下，具有固定桶数组大小的哈希表是不可接受的。（在测试版中不再是限制。）

背景

本文假设您知道哈希表是如何工作的。如果您不知道，那么您应该熟悉它，并考虑哈希表甚至不是一个合适的解决方案的可能性。由于您还必须提供哈希函数，所以您必须了解它们的原理。您不必自己编写。网上有很多可用的，但您需要将它们整合进来，理解它们的原理，并判断它们是否适合您的数据。

平台、环境和要求

我编写这些模板是为了兼容所有编译器、环境和C++的各种版本。然而，我只在GNU C++和Visual C++中实际测试过代码。唯一的环境要求是它们必须能够访问STL vector模板类。还有一个#include <assert.h>，这是ANSI标准的一部分。如果出于任何原因，这会导致编译器错误，您可以轻松地注释掉该行并定义自己的assert宏来让编译器满意。

Using the Code

您可以使用3个哈希表模板。Doxygen生成的文档已包含在源代码中。但是，让我们先从一个“Hello world”开始，您可以用它作为哈希表应用的框架。

入门：教程

首先，您将需要定义您的类，您需要对其进行快速随机访问，在模板代码中称为T（或“数据类”）。此类声明可能如下所示

class Student {

public:
    Student();

    string m_sName;//this will be the unique key to the hash table entry

    int m_nGrade;
    int m_nID;
};

接下来，我们将声明您的哈希类

#include <ahashp.h>

class StudentHash : public _HashP<Student> {

public:
    StudentHash();

private:
    virtual bool COMPAREREFERENCESPREATTRIBUTES CompareReferences(
        const Student &ref1, const char *ref2) const COMPAREREFERENCESPOSTATTRIBUTES;
    virtual bucket_array_unit HASHREFERENCEPREATTRIBUTES GetHashReference(
        const char *ref) const HASHREFERENCEPOSTATTRIBUTES;
    virtual bucket_array_unit HASHREFERENCEPREATTRIBUTES GetHashReference(
        const Student &ref) const HASHREFERENCEPOSTATTRIBUTES;
};

请注意，如果您预计永远不会使用*ATTRIBUTES宏，则可以省略它们。但是，如果您使用它们，您可能会忘记您需要更新旧代码，并且忘记了这个类。因此，如果您非常注重正确性，请务必保留它们。

另请注意，实际上有两个模板参数传递给了_HashP。第二个默认值为const char *。您还会注意到，这些模板参数是传递给虚方法的参数类型。这并非巧合。模板参数决定了传递给虚方法的参数类型。最后，定义您的类。

CompareReferences()的使用是为了当_HashP需要将一个键与哈希表中的特定元素进行匹配时，它能够做到。STL的做法可能要求Student有一个比较运算符。这样，您就不需要修改数据类，而只需在哈希类中实现一个纯虚方法。

bool StudentHash::CompareReferences(const Student &ref1, const char *ref2) const {
    return ref1.m_sName == ref2;
}

现在是哈希函数。这些函数返回桶数组的索引。请注意，通常需要对GetBucketSize()进行取模运算

StudentHash::bucket_array_unit StudentHash::GetHashReference(const char *ref) const {
    sdbm(ref)%GetBucketSize();
}

StudentHash::bucket_array_unit StudentHash::GetHashReference(const Student &ref) const {
    return GetHashReference(ref.m_sName.c_str());
    //just call GetHashReference(const char *)
}

选择哪个哈希函数取决于您。Sdbm()对于string类型的键来说是一个有吸引力的选择，性能好且随机性好，所以我推荐它。就这样，您的哈希类就实现了！您需要做的就是使用它，为此您应该阅读关于Add()、Get()和SetBucketSize()方法的内容。

关注点

优化

我使用了4个名称形式为*ATTRIBUTES的宏。您可以将它们定义为特定于编译器的属性，这可能会使纯虚方法的调用效率略有提高。一种可能的实现方式是GNU属性__attribute__((fastcall))或Visual C++的__fastcall。使用属性在GNU中可能非常危险，在Visual C++中可能稍好一些，所以在使用它们时您应该非常小心，确保您知道自己在做什么。到目前为止，我一直在愉快地使用__attribute__((fastcall))而没有遇到问题，因此尽职调查应该可以确保安全使用。

Characteristics

这个哈希表属于**链式**类型。链由链表维护。这种结构非常适合那些哈希表的查找次数与插入和删除次数的比例不太大的场景。

如果您认为自己做得更好...

如果您想改进我的代码，我将给您一些关于理解它的技巧。

符号

匈牙利命名法是我的最爱之一，但我更喜欢一个我称之为加拿大命名法的改进。

噪音/混乱

我试图清理代码。然而，我仍然保留了一些我舍不得删掉的调试代码，因为我曾经或现在都用得上它们。与其他方法不同，这些代码的文档记录并不好，而且在某些情况下，使用起来可能不太直观。所以，请记住，您可以忽略它们，而不会丢失理解代码的关键点。

STL哲学

人们可以通过“哈希迭代器”来遍历哈希表，这些迭代器借鉴了STL迭代器的概念。我最初发现迭代器这个概念很难理解，但如果需要的话，这可能是高效地顺序遍历这种随机访问数据结构的最佳方式。

私有纯虚方法哲学

C++文化似乎只倾向于使用public的纯虚方法。这可能是为什么，如果您启用了此类警告，GNU C++将**始终**向您发出关于具有虚方法的类没有虚析构函数的警告，即使虚方法不是public的，或者析构函数不是public的。到目前为止，我还没有发现任何理由说明纯虚方法不应该是private的，这样abstract类就可以调用它们，而不是由所有者通过可能指向实例的指针来调用它们。这种哲学使纯虚方法更像回调函数，并且仍然充分利用了abstract类的优势。

杂项

有人可能会注意到我使用了STL的数组模板vector，但没有使用链表。我当时觉得链表很令人沮丧，而且收到了很多关于不当使用迭代器的调试错误。所以，我直接放弃了它，自己创建了链表。此外，我不太确定STL链表的效率，但我对自己编写的链表很有信心。

版本差异

代码的测试版已经过测试，但未经广泛测试。然而，V1.0在使用某些方法时会产生编译器错误。在一些不太重要的代码中也存在一些明显的低效率。因此，测试版具有以下特点：

  • 自适应桶数组：您不再需要担心桶数组的大小。当数组认为表变得太大时，它会自动增加。您还可以控制这些调整何时发生以及它们的大小。
  • 它仍在测试阶段.
  • 更高效的代码：某些代码块更快，但不太可能是关键的Get()方法。
  • 名称更改：我之前使用的命名约定与常规不符，所以我不得不更改一些类名。

历史

  • 2008年2月4日 -- 发布原始版本
  • 2008年2月8日 -- 文章内容更新
  • 2008年3月18日 -- 文章更新 - 部分代码修复
  • 2011年8月22日 -- 文章更新 - 引入测试版
  • 2015年7月2日 -- 发现了最新GNU的一些怪异之处，因此不得不进行一些奇怪的调整。可能还会有更多。
© . All rights reserved.