linux_hash.txt

Linux实现hash算法！ 效率比较高。。。。。

曾经发过一贴关于标准STL中Map的使用简介。
Map虽好用，但其内部使用线性查询，成员一多就会降低查询效率。
现在介绍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算法的函数，
_EqualKey 是比较函数，用于定位相应的成员。

下面建一个Hash函数

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