OpenFOAM中哈希表的实现也采用了类模板技术，使得其可以实现多种不同类别哈希表的构造。
其类头声明如下：
                 template <class T, class Key, class Hash> class HashTable {};
其中三个模板参数T为实际存储对象的类型，Key为标示该对象的关键字，Hash类为表中采用的哈希函数对象类。
哈希表的实现采用的是多串链表的形式，在类内部定义了节点的结构：
                  struct hashedEntry {Key key_; hashedEntry* next_; T obj_;};
这里的三个成员变量key_, next_, obj_分别为节点标示关键字，next_为指向该串下一个节点的指针，obj_为实际保存的对象。

这里所谓的“多串链表”可以如下表示：
fst-->hashedEntry1--next_-->hashedEntry2--next_-->hashedEntry3--next_-->null;
snd-->hashedEntry1--next_-->hashedEntry2--next_-->hashedEntry3--next_-->null;
thrd-->hashedEntry1--next_-->null;
……
……
end-->hashedEntry1--next_-->hashedEntry2--……-->null;
每串链表的首地址之间在内存中是连续的，其相对位置通过模板参数Hash定义的哈希函数计算得到。

实现该多串链表，是通过定义hashedEntry** table_;得到的，各串首地址是通过构造函数里的语句：table_=new hashedEntry*[tableSize_]得到的，因而在内存中是连续的空间。

另外该类还有两个私有成员变量tableSize_,表示串的个数，nElmts_表示表中保存的节点的个数。构造函数提供的默认串个数为100，并将每个串初始化为0；另外由于在构造函数中使用了new []，所以在析构函数中采用delete[]释放内存空间，释放之前还要调用clear()清除每个链表的内容。

insert(const Key& key, const T& newEntry)函数是实现向表中插入元素的成员函数接口，用户可以通过这一函数进行表元素的添加。其具体的运行机制为首先根据key值计算哈希值，并将其作为该元素所在的串号，通过hashedEntry的构造函数将其加到该串的第一个位置。

同样查找函数find(const Key& key)也是通过哈希函数及key值计算得到该key对应的元素所在串号，遍历该串在其中查找key，若找到则返回指向该元素的迭代子iterator或const_iterator。found(const Key& key)函数功能与此相似，只是找到了则返回true，否则返回false。由此可见哈希函数的作用是非常重要的，它是编址和寻址的工具。

erase(const iterator& cit)和erase(const Key& key)的实现主要定义在前者的函数体中，主要是找到cit对应的元素后，将其前面元素的next_指向其next_，并将其delete掉。如果是串的首元素则将该元素的next_设为首元素，而delete该元素。

resize(const label newSize)用于对哈希表进行扩容，当执行insert时其实现要求当nElmts / tableSize >0.8时，调用resize(2*tableSize_)将串的个数增倍。

clear()将遍历所有的串，并delete掉串中所有的元素，最后设置nElmts=0;

toc()返回表中所有元素关键词的列表;

transfer(HashTable<T,Key,Hash>& ht)将ht的内容转移给当前的HashTable对象，具体在实现时首先clear()清除链表串，然后删除table_指针指向的空间；而后设定tableSize_ =  ht.tableSize_; ht.tableSize_ = 0; table_=ht.table_; ht.table_=null; nElmts_=ht.nElmts_; ht.nElmts=0; 这样就实现了将ht所管理的内存空间(table及链表空间)转移给当前HashTable对象了。

评论