C++ 的HashTable

最近因為作業的關係會用到hashtable

但是c++內建並沒有hashtable

有幾個己決方法


#include <ext/hash_map>
#include <ext/hashtable.h>
#include <map>
using namespace __gnu_cxx;


可以用map取代他，可以得到相同的效果

而hashtable雖然目前不是c++的標準類別

但是Linux下大概都已經有實作他

再ext的資料夾下應該都可以找的到

不過還是希望以後會有C++真正的標準hashtable

這邊要注意的是他們都是再__gnu_cxx這個namespace之下

上面3個 map，hashˍmap，hashtable

都可以拿來作類似的工作，但是他們底層實作的方法不一樣

詳細可以去看reference

C++可以把這類資料結構看成陣列來使用

接下來我都用hash_map舉例

...
hash_map<string,string> maps;
maps["左邊"]="老王";
maps["右邊"]="老李";
//他會很像
hash_map<int,string> maps2;
maps2[0]="老王";
maps2[1]="老李";
...


他用法跟一般陣列一樣，只是註標(key)可以是自訂型態

像是maps是用string當index的string陣列


string [] maps;

不過c++的這類型態只支援一些原生型態像是int,char之類的

如果想用自訂class當key或value就必須提供一些指定函式

以hash_map為例


template<class _Key, class _Tp, class _HashFn = hash<_Key>,
class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp>>

第一個參數是用來當index的Data Type

第二個參數是用來當容器內容的DataType

他總共有3個可擴充用參數 第三個跟第四個都是給key用的 第五個是給value用的


簡單來說

maps[key]=value;

想要再中括號[]放入自訂型態 就一定要寫HashFun跟EqualFun

這裡做個小訂正，EqualFun並不是非寫不可 2009/05/06
參考資料：http://www.stlchina.org/twiki/bin/view.pl/Main/STLDetailHashMap

然後想用=指定值 就要寫allocator

不過第五個參數通常沒人寫

因為可以用指標來折衷 指標是原生型態 c++自己可以處理

以下簡單一個例子


class Word: public Token {
public:
string lexeme;
Word(string s,int tag);
virtual ~Word();
string getData()const;
static const Word AND;
static const Word OR;
static const Word EQ;
static const Word NE;
static const Word LE;
static const Word GE;
static const Word MINUS;
static const Word TRUE;
static const Word FALSE;
static const Word TEMP;
};
struct hash_word{
size_t operator()(const string& w)const{
return __stl_hash_string(w.c_str());
}
};

struct eq_word{
bool operator()(const string& w1,const string& w2)const{
return true;
}

};
......
hash_map<string,const Word*,hash_word,eq_word> words;
words["Hello"]=new Word("s",254);


string c++有提供處理hash的方法__stl_hash_string

而通常都是習慣用struct去寫hash_map需要的函式

我們必須作()的運算子多載讓類別可以當function的角色

以hash_word為例，我們覆寫了operator()(const string& w)之後

就可以把hash_word當成function來使用

hash_word hashFun;
size_t hashkey=hashFun("Hello");



而再我宣告了如上的hash_map之後 就隨即產生了const* Word的陣列

就像是

const* Word[] words;

所以他可以接new 傳回來的值(new 會回傳一個指標)

為何有const呢 因為必須存static const Word這些常數Type code

如果直接用Word的話 他就像一般陣列一樣會產生實體必須實作default constructor

所以用指標是比較好的選擇