曾經(jīng)發(fā)過一貼關于標準STL中Map的使用簡介。
Map雖好用，但其內(nèi)部使用線性查詢，成員一多就會降低查詢效率。
現(xiàn)在介紹Hash Map，對_Key進行Hash，查詢時就可以將輸入的_Key進行Hash以直接定位相應的成員。

Hash Map的聲明如下：

template <class _Key, class _Tp,
          class _HashFcn  = hash<_Key>,
          class _EqualKey = equal_to<_Key>,
          class _Alloc =  allocator<_Tp> >
class hash_map;


_HashFcn 是運行Hash算法的函數(shù)，
_EqualKey 是比較函數(shù)，用于定位相應的成員。

下面建一個Hash函數(shù)

struct MyHasher : public unary_function<int, size_t>
{
	size_t operator () (const int& nKey) const
	{
		return static_cast<size_t>(nKey + 10);
	}
};


就將_Key + 10

同時_EqualKey使用缺省的即可，或者自定義也行：

typedef equal_to<int> MyEqual;


程序如下：（Compile under Redhat 8.0 box）

#include <ext/hash_map>
#include <string>
#include <iostream>
#include <functional>
 
using namespace std;
using namespace __gnu_cxx;	// hash map is int __gnu_cxx namespace
 
struct MyHasher : public unary_function<int, size_t>
{
  size_t operator () (const int& nKey) const
  {
    return static_cast<size_t>(nKey + 10);
  }
};
 
typedef equal_to<int> MyEqual;
 
typedef hash_map<int, string, MyHasher, MyEqual> HM_TYPE;
typedef HM_TYPE::iterator HM_IT;
typedef HM_TYPE::const_iterator HM_CIT;
 
int main()
{
	HM_TYPE aHmap;
	
	aHmap[2] = "No.2";
	aHmap[1] = "No.1";
	aHmap[4] = "No.4";
	aHmap[3] = "No.3";
	HM_IT it_stop = aHmap.find(3);
	
	cout << it_stop->second << endl;
	it_stop->second = "No.3 After modification";
	cout << it_stop->second << endl;
	
	cout << "Map contents : " << endl;
	for(HM_CIT it = aHmap.begin(); it != aHmap.end(); it++)
	{
		cout << it->second << endl;
	}
	return 0;
}


程序輸出：
No.3
No.3 After modification
Map contents :
No.1
No.2
No.3 After modification
No.4