专栏首页程序员互动联盟【专业技术】STL hash_map使用(一)

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。

hash_map类在头文件hash_map中,和所有其它的C++标准库一样,头文件没有扩展名。如下声明:

class hash_map<class _Tkey, class _Tval>

{

private:

typedef pair<_Tkey, _Tval> hash_pair;

typedef list<hash_pair> hash_list;

typedef vector<hash_list> hash_table;

};

hash_map是一个聚合类,它继承自_Hash类,包括一个vector,一个list和一个pair,其中vector用于保存桶,list用于进行冲突处理,pair用于保存key->value结构,简要地伪码如下:

class hash_map<class _Tkey, class _Tval>

{

private:

typedef pair<_Tkey, _Tval> hash_pair;

typedef list<hash_pair> hash_list;

typedef vector<hash_list> hash_table;

};

当然,这只是一个简单模型,C++标准库的泛型模版一向以嵌套复杂而闻名,初学时看类库,无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类,hash_compare类里又聚合了less仿函数类,乱七八糟的。

下面说说使用方法:

一、简单变量作为索引:整形、实性、指针型 其实指针型也就是整形,算法一样。但是hash_map会对char*, const char*, wchar_t*, const wchar_t*做特殊处理。 这种情况最简单,下面代码是整形示例:

hash_map<int, int> IntHash;

IntHash[1] = 123;

IntHash[2] = 456;

int val = IntHash[1];

int val = IntHash[2];

实型和指针型用法和整形一样,原理如下: 1、使用简单类型作索引声明hash_map的时候,不需要声明模版的后两个参数(最后一个参数指名hash_map节点的存储方式,默认为pair,我觉得这就挺好,没必要修改),使用默认值就好。 2、对于除过字符串的其它简单类型,hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值,计算方法是经典的掩码异或法,自动溢出得到索引hash值。微软的工程师也许开了一个玩笑,这个掩码被定义为0xdeadbeef(死牛肉,抑或是某个程序员的外号)。 3、对于字符串指针作索引的时候,使用定类型函数inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)计算hash值,计算方法是取出每一个字符求和,自动溢出得到hash值。对于字符串型的hash索引,要注意需要自定义less仿函数。 因为我们有理由认为,人们使用hash表进行快速查找的预期成本要比在hash表中插入的预期成本低得多,所以插入可以比查找昂贵些;基于这个假设,hash_map在有冲突时,插入链表是进行排序插入的,这样在进行查询冲突解决的时候就能够更快捷的找到需要的索引。 但是,基于泛型编程的原则,hash_map也有理由认为每一种类型都支持使用"<"来判别两个类型值的大小,这种设计恰好让字符串类型无所适从,众所周知,两个字符串指针的大小并不代表字符串值的大小。见如下代码:

hash_map<const char*, int> CharHash;

CharHash["a"] = 123;

CharHash["b"] = 456;

char szInput[64] = "";

scanf("%s", szInput);

int val = CharHash[szInput];

最终的结果就是无论输入任何字符串,都无法找到对应的整数值。因为输入的字符串指针是szInput指针,和"a"或"b"字符串常量指针的大小是绝对不会相同。解决方法如下: 首先写一个仿函数CharLess,继承自仿函数基类binary_function(当然也可以不继承,这样写只是符合标准,而且写起来比较方便,不用被类似于指针的指针和指针的引用搞晕。

struct CharLess : public binary_function<const char*, const char*, bool>

{

public:

result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const

{

return(stricmp(_Left, _Right) < 0 ? true : false);

}

};

很好,有了这个仿函数,就可以正确的使用字符串指针型hash_map了。如下:

hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;

CharHash["a"] = 123;

CharHash["b"] = 456;

char szInput[64] = "";

scanf("%s", szInput);

int val = CharHash[szInput];

现在就可以正常工作了。至此,简单类型的使用方法介绍完毕。

未完待续

转自:http://blog.csdn.net/sdhongjun/article/details/4517325

本文分享自微信公众号 - 程序员互动联盟(coder_online)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-02-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【答疑释惑第十四讲】如何学习数据结构?

    疑惑一 为什么学习编程前,先要掌握计算机组成原理? 很多的学习编程的小伙伴,特别是上来就学习java的小伙伴,很多对底层语言的实现存在一种莫名的畏惧感,老是觉得...

    程序员互动联盟
  • 【专业技术】hash_map使用(二)

    上次说完了简单类型的hash_map使用,现在说说用户自定义类型:比如对象类型,结构体的hash_map使用。 这种情况比价复杂,我们先...

    程序员互动联盟
  • 【答疑释惑第三十四讲】Web js 常见用法

    疑惑一 一、js中怎么实现hashcode值? 在java中有一种方法,就是可以获取字符串的对应的hashcode值,返回对应的整数值; 这个方法对于一些写在数...

    程序员互动联盟
  • 面试题,如何在千万级的数据中判断一个值是否存在?

    当你看到这个标题的时候,你也许会想我可以使用hashmap之类的来存储值,然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

    ImportSource
  • hash散列 introduction

    hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

    CoffeeLand
  • djb2 hash算法

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就...

    李小白是一只喵
  • 纸上谈兵: 哈希表 (hash table)

    HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

    Vamei
  • 如果世界上只有一种数据结构,那么我选择哈希!

    来源:blog.csdn.net/liweisnake/article/details/104779497

    芋道源码
  • Hash冲突和一致性

    在数据量很大的时候,就会出现hash之后的数值,指向相同的位置,也就是所谓的hash冲突。这个取决于hash算法的好坏,以及数据量的大小,hash算法越差,数据...

    灰子学技术
  • php hash算法类

    它可以将一个长度不固定的数据,通过算法,获取其特征值生成一个固定的,较短的数据,压缩其文件标识.

    仙士可

扫码关注云+社区

领取腾讯云代金券