条款25：熟悉非标准散列容器

优质

小牛编辑

140浏览

2023-12-01

条款25：熟悉非标准散列容器

STL程序员一般用不了多久就开始惊讶，“vector、list、map，很好，但是散列（hash）表在哪里"？唉，在标准C++库里没有任何散列表。每个人都同意这是个不幸，但是标准委员会觉得需要加给他们的工作可能会过渡地推迟标准的完成。可以肯定标准的下一个版本将包含散列表，但是目前，STL没有散列的东西。

但是如果你喜欢散列表，那么振作起来。你不需要放弃或自己做一个。兼容STL的散列关联容器可以从多个来源获得，而且它们甚至有事实上的标准名字：hash_set、hash_multiset、hash_map和hash_multimap。（译注：在C++标准委员会的议案中，散列容器的名字是unordered_set、unordered_multiset、unordered_map和unordered_multimap。恰好是为了避开现存的hash_*名字。）

在这些公用的名字后面，有不同的实现，呃，不同。它们在接口、能力、内在数据结构和支持操作的相关效率方面不同。写出使用散列表的适度可移植的代码仍然是可能的，但不像如果散列容器被标准化一样容易。（现在你知道为什么标准很重要了吧。）

对于几个可得到的散列容器的实现，最常见的两个来自SGI（参见条款50）和Dinkumware（参见附录B），所以在下文里，我把自己限制在来自这些厂商的散列容器的设计。STLport（再次参见条款50）也提供散列容器，但是STLport的散列容器是基于来自SGI的。为了本条款的目的，假设我写的任何关于SGI散列容器的东西也适用于STLport散列容器。

散列容器是关联容器，因此你不该惊讶，正如所有关联容器，它们需要知道储存在容器中的对象类型，用于这些对象的比较函数，以及用于这些对象的分配器。另外，散列容器需要散列函数的说明。下面是散列容器声明：

template<typename T,
		typename HashFunction,
		typename CompareFunction,
		typename Allocator = allocator<T> >
class hash_container;

这非常接近于散列容器的SGI声明，主要差别是SGI为HashFunction和CompareFunction提供了默认类型。hash_set的SGI声明看起来基本上像这样（我为了演示的目的已经稍微调整了一下）：

template<typename T,
		typename HashFunction = hash<T>,
		typename CompareFunction = equa_to<T>,
		typename Allocator = allocator<T> >
class hash_set;

SGI设计的一个值得注意的方面是使用equal_to作为默认比较函数。这违背标准关联容器的约定——默认比较函数是less。这个设计结果不仅仅表示简单地改变默认比较函数。SGI的散列容器确定在一个散列容器中的两个对象是否有相同的值是通过相等测试，而不是等价（参见条款19）。对于散列容器来说，这不是一个不合理的决定，因为散列关联容器，不像它们在标准中的（通常基于树）兄弟，不需要保持有序。

Dinkumware设计的散列容器采取一些不同的策略。它仍然允许你指定对象类型、散列函数类型、比较函数类型和分配器类型，但是它把默认的散列和比较函数移进一个单独的类似特性的叫做hash_compare的类，而且它把hash_compare作为容器模板的HashingInfo实参的默认值。（如果你不熟悉“特性”类的概念，打开一本好的STL参考，比如Josuttis的《C++ Standard Library》[3]并学习char_traits和iterator_traits模板的动机和实现。）

例如，这是Dinkumware的hash_set声明（再次为演示而调整过）：

template<typename T, typename CompareFunction>
class hash_compare;

template<typename T,
		typename HashingInfo = hash_compare<T, less<T> >
		typename Allocator = allocator<T> >
class hash_set;

这种接口设计有趣的地方是HashingInfo的使用。容器的散列和比较函数储存在那里，但HashingInfo类型也容纳了控制表中桶（bucket）最小数量，以及容器元素对桶的最大允许比率的枚举。当这比率被超过时，表中桶的数量就增加，而表中的一些元素需要重新散列。（SGI提供具有类似控制表中桶和表中元素对桶比率的成员函数。）（译注：如果你不知道桶和散列表的原理，那么看看数据结构的书中关于散列表的部分。）

做了一些为了演示的调整之后，hash_compare（HashingInfo的默认值）看起来或多或少像这样：

template<typename T, typename CompareFunction = less<T> >
class hash_compare {
public:
	enum {
		bucket_size = 4,			// 元素对桶的最大比率
		min_buckets = 8			// 桶的最小数量
	};

size_t operator()(const T&) const;			// 散列函数
bool operator()(const T&,				// 比较函数
			const T&) const;

...						// 忽略一些东西，包括
						// CompareFunction的使用
}

重载operator()（在这里是实现散列和比较函数）是比你可以想象的更经常出现的一个策略。对于这一想法的另一个应用，参见条款23。

Dinkumware设计允许你写你自己的类似hash_compare的类（也许通过从hash_compare本身派生而来），而且只要你的类定义了bucket_size、min_buckets、两个operator()函数（一个带有一个实参，一个带有两个），加上我已经省去的一些东西，你就能使用它来控制Dinkumware的hash_set或hash_multiset的配置和行为。hash_map和hash_multimap的配置控制也相似。

注意不管是SGI还是Dinkumware的设计，你都能把全部决策留给实现，并仅仅写像这样的东西：

hash_set<int> intTable;		// 建立一个int的散列表

要让这个可以编译，散列表必须容纳一个整数类型（例如int），因为默认散列函数一般局限于整数类型。（SGI的默认散列函数稍微灵活一些。条款50将告诉你在哪里可以找到全部细节。）

在后端，SGI和Dinkumware的实现方法非常不同。SGI利用常用的一个元素的单链表的指针数组（桶）组成的开放散列法。Dinkumware也利用了开放散列法，但是它的设计是基于一种新颖的数据结构——由迭代器（本质是桶）的数组组成的元素双向链表，迭代器的相邻对表示在每个桶里元素的范围。（细节可以参考Plauger相关主题的专栏，《Hash Tables》[16]。）

作为这些实现的用户，你可能会对SGI实现在单链表中储存表的元素，而Dinkumware实现使用一个双向链表的事实感兴趣。差别是值得注意的，因为它影响了用于两个实现的迭代器种类。SGI的散列容器提供了前向迭代器，因此你得放弃进行反向迭代的能力：在SGI的散列容器中没有rbegin或者rend成员函数。用于Dinkumware散列容器的迭代器是双向的，所以它们可以提供前向和反向遍历。在内存使用量方面，SGI的设计比Dinkumware的节俭一点点。

哪个设计最有利于你和你的程序？我不可能知道。只有你能确定，而且本条款并不试图给你足以得出一个合理结论的信息。取而代之的是，本条款的目标是让你知道虽然STL本身缺乏散列容器，兼容STL的散列容器（有不同的接口、能力和行为权衡）不难得到。就SGI和STLport的实现而言，你甚至可以免费得到它们，因为它们可以自由下载。