具有类似 STL 接口的通用开放寻址哈希表实现

Leandro T C Melo

4.97/5 (15投票s)

2008年1月21日

BSD

5分钟阅读

86324

721

一个通用的独立式、类似STL的哈希表实现，采用线性探测或双重散列作为冲突解决方法。

下载源代码 - 16.9 KB

引言

哈希表是非常常见的数据结构。它们提供高效的、基于键的操作，用于在容器中插入和搜索数据。像计算机科学中的许多其他事物一样，使用哈希表也伴随着权衡。当需要排序和选择操作时，它们不是好的选择。

关于基于哈希的容器的实现，有两个主要问题：哈希函数和冲突解决方法。哈希函数负责将特定键转换为特定表地址的算术运算。冲突解决方法负责处理哈希到相同地址的键。

尽管C++ STL（标准模板库）不支持基于哈希的容器，但大多数编译器（如GCC或Visual C++）都有自己的实现——值得注意的是，TR1（技术报告1）已经提供了无序映射和集合结构。另外，STLport [1] 是一个很好的替代方案，它提供了以下类模板：

hash_set
hash_map
hash_multiset
hash_multimap

不同编译器哈希表实现的接口可能各不相同。此外，并非所有编译器都支持TR1。将STLport集成到您的代码中可能并不容易（当然，除非您已经在使用它）。最后，这些基于哈希的容器大多使用分离链接作为冲突解决方法，这是一种直接的方法，但不是唯一的方法。

开放寻址是一种通过在哈希表中进行顺序探测来处理冲突的方法。当有足够的连续内存并且可以估算表中元素的数量时，它可能非常有用。两种广为人知的开放寻址策略是线性探测和双重散列，我将在下一节中简要讨论它们。

在本文中，我将介绍一个通用的、独立的、类似STL的哈希表实现，该实现使用线性探测或双重散列作为冲突解决方法。它作为上述四个类模板的底层实现，并且运用了STLport中的许多C++技术构建。代码非常接近STL和扩展的SGI概念。确切地说，只有一个操作未实现（原因稍后解释）。此外，该代码也作为对泛型编程的有趣介绍。这是一篇简短的文章，我既不提供关于哈希表的理论讨论，也不提供所有实现细节。我更感兴趣的是提供源代码，以便他人可以审查、提出建议，并从中受益。

哈希表参数化

以下类模板是hash_set、hash_map、hash_multiset和hash_multimap的底层实现。

template <
  class key_t, 
  class value_t, 
  class hash_fcn_t,
  class increment_t,
  class equal_key_t,
  class get_key_t,
  class alloc_t> 
class hash_table__
{
  //...
};

上面的模板参数大多具有有意义的名称和直接的作用。第一个参数key_t是哈希表的键类型。第二个参数value_t是值类型。（在set中，值就是实际的键；在map中，值是包含键和值的对。）第三个参数表示哈希函数。跳过第四个参数（我将在下一段中解释），第五个参数equal_key_t是一个二元谓词，用于确定两个键是否相等。参数get_key_t有一个有趣的职责：它是一个一元函数，用于获取存储在哈希表中的值的键。此参数必须根据值的类型进行设置。最后一个模板参数是分配器类型。

线性探测和双重散列之间只有一个显著的区别。对于线性探测，当检测到冲突时，算法会查找当前表地址的下一个位置，以检查它是否可用。它会一直这样做，直到找到一个空位（一旦到达表的末尾，它会重新开始）。自然，表未满非常重要。（此实现假定最大负载因子为5/10。）对于双重散列，第二个哈希函数被用作从当前表地址到算法查找的其他位置的增量。在这种特定情况下，还有一个额外的考虑是如何编写一个不会导致无限循环的第二个哈希函数。一个好的通用选择是选择一个与表大小互质的增量。我已经为（整数类型）提供了两个模板特化，用作increment_t参数的参数。

//For linear probing.
template <class key_t>
struct unit_increment
{
  std::size_t operator()(const key_t&){ return 1; }
};

//For double hashing.
template <class key_t>
struct hash_increment{};

//Specialization for integral types are just like this one.
template <> 
struct hash_increment<short>
{
  std::size_t operator()(short x){return (x % 97) + 1;}
};

线性探测和双重散列的行为非常相似。然而，双重散列更不容易形成簇，因为哈希到相同地址的键很可能会在表中分散开。另一方面，由于删除操作的问题，线性探测的实现可能稍微简单一些。更多细节请参阅[2]。

正如我之前提到的，hash_table__是映射和集合类模板的底层实现。这是通过组合实现的，如下面的hash_map示例代码所示。

template <
  class key_t, 
  class value_t, 
  class hash_fcn_t = hash<key_t>, 
  class increment_t = unit_increment<key_t>,
  class equal_key_t = std::equal_to<key_t>, 
  class alloc_t = std::allocator<std::pair<key_t, value_t> > >
class hash_multimap 
{
private:
  typedef std::pair<key_t, value_t> Map_pair;
  typedef hash_table__<
    key_t,
    Map_pair,
    hash_fcn_t,
    increment_t,
    equal_key_t,
    select1st<Map_pair>,
    alloc_t> HT; 
  HT underlying_;  
  //...
};

迭代器

在底层，哈希表是用std::vector实现的。因此，实现一个迭代器相对简单。基本上，需要有一个指向向量的指针、一个表示当前位置（或索引）的整数类型，以及一些用于迭代过程的逻辑。不过，有一个问题值得讨论。

当对iterator进行解引用时，会提供一个实例的引用。然而，当对const_iterator进行解引用时，会提供一个常量引用。由于这仅仅是类型差异，而不是编写两个迭代器实现，我们可以使用一个辅助traits类模板来完成这项工作。

迭代器实现的一个模板参数是哈希表类型。另一个是traits类型。对于iterator类型的定义，使用了non_const_traits类模板。对于const_iterator类型的定义，使用了const_traits类模板。下面的代码展示了这个想法

template <class value_t>
struct const_traits
{
  typedef const value_t* pointer;
  typedef const value_t& reference;
};

template <class value_t>
struct non_const_traits
{
  typedef value_t* pointer;
  typedef value_t& reference;
};

//Iterator implementation.
template <
  class hash_container_t,
  class constness_traits_t>  
struct hash_table_iterator__
{  
  //...
  typedef typename constness_traits_t::pointer pointer;
  typedef typename constness_traits_t::reference reference;
  reference operator*()const {return (*this->container_)[this->current_].value_;}
  pointer operator->()const {return &(operator*());}
};

最后一个问题是iterator和const_iterator之间的转换应该得到妥善处理。请参阅源代码以获取示例。

Using the Code

代码的使用就像任何STL容器一样。这里有一个例子

#include "hash_map.h"
#include <iostream>

int main()
{
  using namespace hashcol;
  
  typedef hash_map<int,double> Map;
  typedef Map::value_type value_type;
  typedef Map::iterator iterator;

  Map map;  
  map.insert(value_type(8, 8.888));
  map.insert(value_type(1, 1.111));
  map.insert(value_type(12, 12.12));
  map.insert(value_type(3, 3.3));
  map.insert(value_type(122, 122.122));
  
  std::cout << "\nSize is: " << map.size();
  std::cout << "\nElements are:";
  for (iterator it = map.begin(); it != map.end(); ++it)
  {
    std::cout << "\n\tKey = " << it->first 
              << "   Value = " << it->second;
  }
  
  return 0;
}

参考文献

[1] STLport - http://www.stlport.org/
[2] Sedgewick R. Algorithms in C++ - Fundamentals, Data Structures, Sorting and Searching (3^rd edn). Addison-Wesley, 1998