Map和hash_map

2022-11-06 07:48:28

map和hash_map

今天在写拼流的程序时碰到一个问题，要根据流的四元组的结构信息映射到该流的数据。也就是我在网络数据包拼接的过程中，要根据包的地址和端口信息，对应到其对应的一个流的数据上去，把端口和地址信息相同的包的数据段中的数据组装起来。自然想到用map，不过map要求其关键码类型提供一个小于操作，而我的这种四元组信息没有大小的关系，于是自然就想到用hash_map。
hash_map基于哈希表，它对数据的存储和查找所需的时间大大降低，几乎可以看成是常数时间（理想情况下是O(1)）。其代价是消耗比较多的内存，不过在某些情况下用空间换时间的做法是值得的。
hash_map的声明大致是这样的：

template <class _Key, class _Tp, class _HashFcn = hash<_Key>,class _EqualKey = equal_to<_Key>,class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >class hash_map{        ...}

hash_map的基本原理是使用一个下标范围比较大的数组来存储元素。需要提供一个散列函数（hash函数），使得每个关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素。除了定义一个hash函数外，还需提供一个比较其关键码是否相等的函数。对于STL的内部类型的关键码，hash函数和equal_to函数可以省略，STL会提供缺省的函数。不过对于自定义结构的关键码，就必须自己提供hash函数和比较函数。
在声明自己的哈希函数时要注意以下几点：

使用struct，然后重载operator().
返回是size_t
参数是你要hash的key的类型。
函数是const类型的。

例如：

//如果要自己定义字符串hash函数，你可以这样写：
struct str_hash{

        size_t operator()(const string& str) const        {
										unsigned
										long __h = 0;
										for (size_t i = 0 ; i < str.size() ; i ++)                __h = 5*__h + str[i];
										return size_t(__h);        }};

对于比较函数，应该就比较简单了。
map和hash_map性能分析：
    选择map容器，是为了更快的从关键字查找到相关的对象。与使用list这样的线性表容器相比，一可以简化查找的算法，二可以使任意的关键字做索引，并与目标对象配对，优化查找算法。在C++的STL中map是使用树来做查找算法，这种算法差不多相当与list线性容器的折半查找的效率一样，都是O (log2N)，而list就没有map这样易定制和操作了。
相比hash_map，hash_map使用hash表来排列配对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。
    总体来说，hash_map 查找速度会比map快，其查找速度基本和数据量大小无关，属于常数级别；而map的查找速度是log(n)级别。hash_map的缺点是性能不稳定，且占用较多内存。这就需要权衡了。
    树查找，在总查找效率上比不上hash表，但是它很稳定，它的算法复杂度不会出现波动。在一次查找中，你可以断定它最坏的情况下其复杂度不会超过O (log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。假若你在开发一个供外部调用的接口，其内部有关键字的查找，但是这个接口调用并不频繁，你是会希望其调用速度快、但不稳定呢，还是希望其调用时间平均、且稳定？反之假若你的程序需要查找一个关键字，这个操作非常频繁，你希望这些操作在总体上的时间较短，那么hash表查询在总时间上会比其他要短，平均操作时间也会短。
总结一下，选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。如果是少数次的操作，使用hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map，考虑整体稳定性应该要高于整体效率，因为前提在操作次数较少。如果在一次流程中，使用hash_map的少数操作产生一个最坏情况O(N)，那么hash_map的优势也因此丧尽了。
    下面摘录使用hash_map的一个例子，我的程序就是参考的这个例子：（对于自定义的结构，为它定义一个好的hash函数是最重要的，这个例子中的hash函数定义很简单。。。）
#include <hash_map>
#include <string>
#include <iostream>
using
namespace std;
//define the class
class ClassA{
public:
ClassA(int a):c_a(a){}
int getvalue()const { return c_a;}
void setvalue(int a){c_a;}
private:
int c_a;
};
//1 define the hash function
struct hash_A{
size_t operator()(const
class ClassA & A)const{
// return hash<int>(classA.getvalue());
return A.getvalue();
}
};
//2 define the equal function
struct equal_A{
bool
operator()(const
class ClassA & a1, const
class ClassA & a2)const{
return a1.getvalue() == a2.getvalue();
}
};

int main()
{
hash_map<ClassA, string, hash_A, equal_A> hmap;
ClassA a1(12);
hmap[a1]="I am 12";
ClassA a2(198877);
hmap[a2]="I am 198877";

cout<<hmap[a1]<<endl;
cout<<hmap[a2]<<endl;
return 0;
}

后来弄了半天，发现VC6下竟没有hash_map头文件，ft....。ms当年VC6出来的时候hash_map还没有成为STL标准吧。转而奔到.net2003下，还是编译不过，再ft....现在正下.net 2005中，希望能支持hash_map，不然就只能单独下一个STL库安装上了。

支持(0)反对(0)

码农公寓

相关文章