我学hash_map(1)

时间:2022-09-23 23:03:43

本文来源:http://blog.chinaunix.net/uid-26548237-id-3800125.html 

map是什么?

map是键值对(key-value),复杂度是O(n).但是查找次数仍然会成为瓶颈。

hash_map是什么?

基本原理:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。哈希问题最重要的是两个方面“直接定址”和“解决冲突”。其过程为:

1-key

2-hash值

3-桶号(一般为求模)

4-key/value存入桶

取值过程是:

1-key

2-hash值

3-得到桶号

4-桶内元素是否和key相等。不等说明没找到。

5-相等,取出value

hash_map的使用

需要定义自己的hash函数,有以下几点要求。

1、使用struct,重载operator()

2、返回size_t

3、参数是你要hash的key类型

4、函数是const类型的

然后将hash函数写成如下形式的:

hash_map<string, string, str_hash> namemap;

下面再说比较函数:

hash_map中需要提供equal_to<key>

有两种方法,第一种重载==操作符。

struct mystruct{
int iID;
int len;
bool operator==(const mystruct & my) const{
return (iID==my.iID) && (len==my.len) ;
}
};

这样就可以直接用equal_to<mystruct>了。第二种是用一个“函数对象”。自定义一个比较函数体。

struct compare_str{
bool operator()(const char* p1, const char*p2) const{
return strcmp(p1,p2)==0;
}
};

然后就可以用下面这个东西了

typedef hash_map<const char*, string, hash<const char*>, compare_str> StrIntMap;
StrIntMap namemap;
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";

原文的例子好搞笑。我更加倾向于使用第一种方法。因为我感觉第二种好像很麻烦。

我学hash_map(1)的更多相关文章

  1. 我学hash&lowbar;map&lpar;2&rpar;

    啊,转眼之间就来到了我学hash_map(2)了.我们也从hash_map转移到了unordered_map上来了,今天这个文章的目的就是要来分享一下使用这个hash_map,哦不,unordered ...

  2. unordered&lowbar;map&lpar;hash&lowbar;map&rpar;和map的比较

    测试代码: #include <iostream> using namespace std; #include <string> #include <windows.h& ...

  3. 【Python五篇慢慢弹】快速上手学python

    快速上手学python 作者:白宁超 2016年10月4日19:59:39 摘要:python语言俨然不算新技术,七八年前甚至更早已有很多人研习,只是没有现在流行罢了.之所以当下如此盛行,我想肯定是多 ...

  4. 跟Unity3D学代码优化

    今天我们来聊聊如何跟Unity学代码优化,准确地说,是通过学习Unity的IL2CPP技术的优化策略,应用到我们的日常逻辑开发中. 做过Unity开发的同学想必对IL2CPP都很清楚,简单地说,IL2 ...

  5. 重学hadoop技术

    最近因为做了些和hadoop相关的项目(虽然主要是运维),但是这段经历让我对hadoop的实际运用有了更加深入的理解. 相比以前自学hadoop,因为没有实战场景以及良好的大数据学习氛围,现在回顾下的 ...

  6. 《学技术练英语》PPT分享

    之前做的一个PPT,分享给博客园的同学. 下载地址: 学技术练英语.pdf 技术是靠自己去学的,学技术不能仅仅是看书看博客,最好是有实践,不管是做实验去验证,还是写各种代码去玩各种特性,还是造*都是 ...

  7. 前端学HTTP之数据传输

    × 目录 [1]客户机处理 [2]集线器处理 [3]路由器1处理[4]路由器2处理[5]交换机处理[6]服务器处理[7]反向传输 前面的话 上一篇中,介绍了网络基础.本文将详细介绍客户机在浏览网页ab ...

  8. 前端学HTTP之网络基础

    × 目录 [1]网络 [2]OSI [3]TCP/IP 前面的话 HTTP协议对于前端工程师是非常重要的.我们在浏览网站时,访问的每一个WEB页面都需要使用HTTP协议实现.如果不了解HTTP协议,就 ...

  9. Mina、Netty、Twisted一起学(八):HTTP服务器

    HTTP协议应该是目前使用最多的应用层协议了,用浏览器打开一个网站就是使用HTTP协议进行数据传输. HTTP协议也是基于TCP协议,所以也有服务器和客户端.HTTP客户端一般是浏览器,当然还有可能是 ...

随机推荐

  1. Macosx 安装 ionic 成功教程

    一.首先介绍一下ionic ionic是一个用来开发混合手机应用的,开源的,免费的代码库.可以优化html.css和js的性能,构建高效的应用程序,而且还可以用于构建Sass和AngularJS的优化 ...

  2. AngularJs项目实践总结

    今年3月接触AngularJs,并且在6月的项目中开始应用,从踩坑到填坑花了不少时间,根据项目中的实际应用情况总结了一些经验,如下: 一.UI控件选择 Angularjs是不缺控件的,Github里现 ...

  3. WebKit的CSS扩展&lpar;WebKit是私有属性&rpar;

    http://www.css88.com/webkit/-webkit-touch-callout/ -webkit-tap-highlight-color 是一个 不规范的属性(unsupporte ...

  4. 百度SDK的使用第一天

    //获取自定义的经纬度上添加位置气泡,大头钉 BMKPointAnnotation* annotation = [[BMKPointAnnotation alloc]init]; CLLocation ...

  5. jquery&period;validate运用和扩展

    一.运用 默认校验规则 ().required:true 必输字段 ().remote:"remote-valid.jsp" 使用ajax方法调用remote-valid.jsp验 ...

  6. 【NOIP2008】双栈排序

    感觉看了题解还是挺简单的,不知道当年chty同学为什么被卡了呢么久--所以说我还是看题解了 原题: Tom最近在研究一个有趣的排序问题.如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将 ...

  7. qualcomm platform camera porting

    转载自http://www.cnblogs.com/thjfk/p/4086001.html camera基本代码架构 Camera原理:外部光线穿过lens后,经过color filter滤波后照射 ...

  8. &lbrack;置顶&rsqb; 使用U盘安装ubuntu系统

    使用U盘安装ubuntu系统 在网上找了很多教程,都不起效,提示:“从光盘上读取数据出错”. 总结出了几个关键点. 首先,版本,Ubuntu 12.04 Server,一般的U盘安装都会报:“从光盘上 ...

  9. 树莓派3B&plus; 安装系统

    安装概要步骤: 官网下载系统->刷入TF卡->设置开启显示器和SSH->通电->进入系统 1. 进入官方网站下载系统镜像 下载页面:https://www.raspberryp ...

  10. R t-test cor&period;test

    a = c(175, 168, 168, 190, 156, 181, 182, 175, 174, 179)b = c(185, 169, 173, 173, 188, 186, 175, 174, ...