Linux之父Linus Torvalds谈软件开发管理经验

导读:没有人比Linus Torvalds更了解软件开发项目管理中的酸甜苦辣了。作为Linux的创建者,Torvalds在过去二十年指导了数以千计的开发者共同改进开源操作系统内核。此前,CSDN研发频道发表过一篇文章《Linus Torvalds的软件开发管理经验》,文中提到了Torvalds在软件管理方面的宝贵经验。现对此文进行全文翻译及整理,供开发者学习与参考。

 

文章内容如下:

Linus Torvalds说,有两件事,世界上大都数人,无论是独立开发者还是公司级别的开发团队,都有普遍的错误认知。

其一:“大都数人认为可以把事情丢给其他人,让他们帮忙。在你公开你的想法后,你得假设自己一个人要干完全部的活,然后你在网上征求人们的意见,你 应该询问自己该干什么,而不是他们该干什么。或许开始他们会偶尔帮助你解决一些实际问题,但是,必须从一开始就告诉自己这份工作只有你一个人负责,并且做 好完成它的准备。”

 

如果你一开始就认为全世界的人们都会联合起来为你的项目工作,一起创造一个更美好的世界,那么你可能不会走得很远。

其二:“人们往往认为自己写的代码是最重要的东西,而事实不是这样。即使你编写了100%的代码;即使你是世界上最好的程序员并且从来不需要任何帮助。然而最重要的东西也不是你写的代码,而是代码的用户。代码本身不重要;只有当用户真正用到它的时候项目才是有用的。之所以提到这一点是因为它不只是一个程序员的问题,我见过一些公司把追求完美的程序当做事情的全部。”

Torvalds就第二个问题上继续展开言论,他说:“这就是为什么Linux内核团队无法容忍这种‘脱离本质’的东西。比如,为了“修复”某个问 题而打破原来的用户体验绝对是错误的观点;千万不要这么干。如果你破坏了用户体验,或许你觉得是在修复问题,但你就犯了刚才说到的第二个错误——你以为代 码质量比用户重要,大错特错。”

Torvalds最后总结道:“有太多的项目将代码质量置于用户之上,结果两边都不讨好,而且还不肯承认错误,因为他们觉得是在“修复”问题,并且一点都没错。”

 

关于开发工具的重要性

关于SCM(Software Configuration Management软件配置管理系统 )工具,比如,以Git版本控制系统的问题为例,他回答说:“我不认为工具是最重要的。”

“现在重要的是你的项目是否有一个好的工作流程,工具当然能够启到帮助的作用,”他说,“但是,大多数的项目其实并不是必须要使用这些工具。许多项 目其实并没有那么多改动,多到必须要在他们整个工作流程中使用这些工具;如果你在每个release中只有几百个补丁,你可以随便怎么维护他们,完全手动 也不是问题。”

当然,Linux就绝对不是同一个层次的了,“对于内核,我们每个release都有成千上万个补丁,而且基本上每三个月就有一个release, 所以对我们来说SCM工具就尤其重要了。”他说,“但我仍然不认为这所有大的错误是因为最初几年开发的目标球和补丁,这是一个小得多的项目,而且直到很多 年后是因为缺乏管理工具才显现出来。”

他还说,“一些工具积极鼓励工作流程,我认为CVS(Concurrent Versions System并发版本控制系统)”例如已经影响了很多项目,使他们有了一个概念“承诺团体”,

Torvalds继续说,“我个人认为tar-balls和补丁相比他来说要好得多,因为他们使开发者都是“平等”的。而且你不会遇到这种情况:一 些开发者有委员权限而其他的人都是二级权限。有时全部人都只有二等权限要比有人有特权要好得多。”(注:Torvalds很熟悉CVS很而且非常讨厌有很 多年时间了。就如他在Google Talk 2007所说的,“我讨厌带着许可证的CVS”。)Torvalds还说:“比工具更重要的是人,是维护者和他们的思想。”

 

如何把大家都保持在正轨上

现在的人们是怎么一起工作的呢?我向Torvalds提问了关于正在实施中的LKML(Linux Kernel Mailing List ,用来将讨论话题转发给各位开发者。)他回答说:“我认为过去在LKML上发生的讨论比现在的多。LKML中的signal-to-noise和纯信息量 表明大多数开发者没有时间仔细地去读LKML——最多他们会扫一下标题栏。所以,现在我主张大多数开发者都在独自完成工作,然后他们会在一个大的开发者范 围中发送email告之对方是如何完成的”。

“并不是说LKML不重要,而是说LKML已经成为了独立开发者的公共纽带。所以事情最后会变成这样:你其实只有4-5个人一同参与一个讨论,但是LKML会转发并且让其他人有机会能够参加进来,而不是让他成为一个封闭的讨论。”

接下来说说它怎么工作的,“大多数人其实不阅读LKML,他们经常让它自动存档,只对某几个关键词或关键人物参与的话题感兴趣。”它其实有点类似于 某种存档机制。人们可以在日后查阅它,而且很多Bug可以通过Google找到LKML中以前报道的记录。如果某人提出了一个问题,它可能只是个别硬件问 题,但如果Google后发现在LKML中已经被提交过几次了,那这个问题原因会有点不确定,但必然不是个案。”

“所以我认为LKML非常重要,但我们不是通过它来保持人们走在正轨上的。所有的开发者都非常主动积极,而且他们都有非常好的意见和想法(核心成员 之所以是核心成员因为他们的自我定位)。LKML很重要,因为这是公开讨论的,即使实际中参与某些特定问题的只有特定的一小组人。在开源项目中事情就是和 其他不一样。”Torvalds总结道。

 

关于信任,托付和保持清醒

曾经Linux是一个个人项目。现在他有成千上万的提交者和贡献者。接下来我问道:“现在有多少工作你是交付给其他人做的?对于如何分配才能保持人们思路清晰和遵循工作流程你有什么想法?”

“如果我从中学到了什么的话,那就是你必须学会放手,不要试图控制别人和他们的代码。如果你不信任别人,而一定要监视着他们的话,还是早点放弃这个负责人位置吧。”

他说:“是的,我经常会跟别人纠结一些细节,但不是因为我不信任别人或不愿分配给他们权限。而是因为一些小错误最后会闹到我头上。要么是个 Bug(而且都是一些平时忽视的小错误),要么是一些把我弄烦了的工作流程问题(就像今天早些时候我向一个分负责人抱怨开发者的名字显示不正常)。”

Torvalds还说,“你只能偶尔关注一下细节,而不是老是站在开发者后面监视他、检查他写的每一句代码。我相信分负责人做的事99%都是没问题的,然后偶尔我会大声抱怨一些东西。”比如说GNOME桌面系统正在怎么改进,或者根本没有改进。

以上就是全部内容了。这就是Torvalds怎么做的,如果你觉得你比他好,先问问自己:有创造过一个在大多数超级计算机、股票交易和类似于 Google这样的网站上运行的世界级的操作系统吗?如果你的答案是没有,如果我是你,我会重新读一遍他的答案并且好好想想自己是怎么维护项目的。

文章来源:Linus Torvalds’s Lessons on Software Development Management

Web代码审计工具大大全

Php Code Audits的方向

下面是一个Source Code Auditing tools的一个list[转于网络]

Name - [ language/s supported ] - web link:
.TEST - [ C#, VB.NET, MC++ ] - http://www.parasoft.com/jsp/products.jsp
ASTRéE - [ C ] - http://www.astree.ens.fr
Bandera - [ Java ] - http://bandera.projects.cis.ksu.edu/
BLAST - [ C ] - http://mtc.epfl.ch/software-tools/blast/
BOON - [ C ] - http://www.cs.berkeley.edu/~daw/boon/
C Code Analyzer (CCA) - [ C ] - http://www.drugphish.ch/~jonny/cca.html
C++test - [ C++ ] - http://www.parasoft.com/jsp/products.jsp
CCMetrics - [ C#, VB.NET ] - http://www.serviceframework.com/jwss/utility,ccmetrics,utility.aspx
Checkstyle - [ Java ] - http://checkstyle.sourceforge.net/
CodeCenter - [ C ] - http://www.ics.com/products/centerline/codecenter/features.html
CodeScan - [ .ASP, PHP ] - http://www.codescan.com/
CodeSecure - [ PHP, Java ] - http://www.armorize.com/corpweb/en/products/codesecure
CodeSonar - [ C, C++ ] - http://www.grammatech.com/products/codesonar/overview.html
CQual - [ C ] - http://www.cs.umd.edu/~jfoster/cqual
Csur - [ C ] - http://www.lsv.ens-cachan.fr/csur/
Dehydra - [ C++ ] - http://wiki.mozilla.org/Dehydra_GCC
DevInspect - [ C#, Visual Basic, JavaScript, VB Script] - http://www.spidynamics.com/products/devinspect/
DevPartner SecurityChecker - [ C#, Visual Basic ] - http://www.compuware.com/products/devpartner/securitychecker.htm
DoubleCheck - [ C, C++ ] - http://www.ghs.com/products/doublecheck.html
FindBugs - [ Java ] - http://findbugs.sourceforge.net/
FlawFinder - [ C, C++ ] - http://www.dwheeler.com/flawfinder/
Fluid - [ Java ] - http://www.fluid.cs.cmu.edu/
Frama-C - [ C ] - http://frama-c.cea.fr/
ftnchek - [ FORTRAN ] - http://www.dsm.fordham.edu/~ftnchek/
FxCop - [ .NET ] - http://code.msdn.microsoft.com/codeanalysis
g95-xml - [ FORTRAN ] - http://g95-xml.sourceforge.net/
ITS4 - [ C, C++ ] - http://www.cigital.com/its4/
Jlint - [ Java ] - http://artho.com/jlint/
JsLint - [ JavaScript ] - http://www.jslint.com/
Jtest - [ Java ] - http://www.parasoft.com/jsp/products.jsp
KlocWork / K7 - [ C, C++, Java ] - http://www.klocwork.com/products/k7_security.asp
LAPSE - [ Java ] - http://www.owasp.org/index.php/Category:OWASP_LAPSE_Project
MOPS - [ C ] - http://www.cs.berkeley.edu/~daw/mops/
MSSCASI - [ ASP ] - http://www.microsoft.com/downloads/details.aspx?FamilyId=58A7C46E-A599-4FCB-9AB4-A4334146B6BA&displaylang=en
MZTools - [ VB6, VBA ] - http://www.mztools.com/index.aspx/
Oink - [ C++ ] - http://www.cubewano.org/oink
Ounce - [ C, C++, Java, JSP, ASP.NET, VB.NET, C# ] - http://www.ouncelabs.com/accurate-complete-results.html
Perl-Critic - [ Perl ] - http://search.cpan.org/dist/Perl-Critic/
PLSQLScanner 2008 - [ PLSQL ] - http://www.red-database-security.com/software/plsqlscanner.html
PHP-Sat - [ PHP ] - http://www.program-transformation.org/PHP/PhpSat
Pixy - [ PHP ] - http://pixybox.seclab.tuwien.ac.at/pixy/index.php
PMD - [ Java ] - http://pmd.sourceforge.net/
PolySpace - [ Ada, C, C++ ] - http://www.polyspace.com/products.htm
PREfix & PREfast - [ C, C++ ] - http://support.microsoft.com/vst
Prevent - [ C, C++ ] - http://www.coverity.com/html/coverity-software-quality-products.html
PyChecker - [ Python ] - http://pychecker.sourceforge.net/
pylint - [ Python ] - http://www.logilab.org/project/pylint
QA-C, QA-C++, QA-J - [ C, C++, Java, FORTRAN ] - http://www.programmingresearch.com/PRODUCTS.html
QualityChecker - [ Visual Basic 6 ] - http://d.cr.free.fr/
RATS - [ C, C++, Perl, PHP, Python ] - http://www.fortify.com/security-resources/rats.jsp
RSM - [ C, C++, C#, Java ] - http://msquaredtechnologies.com/m2rsm/
Smatch - [ C ] - http://smatch.sourceforge.net/
SCA - [ ASP.NET, C, C++, C#, Java, JSP, PL/SQL, T-SQL, VB.NET, XML ] - http://www.fortifysoftware.com/products/sca/
Skavenger - [ PHP ] - http://code.google.com/p/skavenger/
smarty-lint - [ PHP ] - http://code.google.com/p/smarty-lint/
soot - [ Java ] - http://www.sable.mcgill.ca/soot/
Source Monitor - [ C#, VB.NET ] - http://www.campwoodsw.com/sm20.html
SPARK - [ Ada ] - http://www.praxis-his.com/sparkada/spark.asp
Spike PHP Security Audit Tool - [ PHP ] - http://developer.spikesource.com/projects/phpsecaudit/
Splint - [ C ] - http://www.splint.org/
SWAAT - [ PHP, ASP.NET, JSP, Java ] - http://www.owasp.org/index.php/Category:OWASP_SWAAT_Project
UNO - [ C ] - http://spinroot.com/uno/">
vil - [ C#, VB.NET ] - http://www.1bot.com/
Viva64 - [ C++ ] - http://www.viva64.com/
xg++ - [ C ] - http://www.stanford.edu/~engler/mc-osdi.pdf

 

支持php的有:

CodeScan - [ .ASP, PHP ] - http://www.codescan.com/
CodeSecure - [ PHP, Java ] - http://www.armorize.com/corpweb/en/products/codesecure
PHP-Sat - [ PHP ] - http://www.program-transformation.org/PHP/PhpSat
Pixy - [ PHP ] - http://pixybox.seclab.tuwien.ac.at/pixy/index.php
RATS - [ C, C++, Perl, PHP, Python ] - http://www.fortify.com/security-resources/rats.jsp
Skavenger - [ PHP ] - http://code.google.com/p/skavenger/
smarty-lint - [ PHP ] - http://code.google.com/p/smarty-lint/
Spike PHP Security Audit Tool - [ PHP ] - http://developer.spikesource.com/projects/phpsecaudit/
SWAAT - [ PHP, ASP.NET, JSP, Java ] - http://www.owasp.org/index.php/Category:OWASP_SWAAT_Project

另外还有一个Fortify - http://www.fortifysoftware.com [如果还有,请帮忙补充]

目 前就php的Source Code Auditing tool基本都是静态分析的,而Source Code Auditing一直围绕着2个元素:变量和函数.也就是说这些tools不管是php开发的还是java开发的,也不管是不是基于php原代码的,他本 身都对一些危险的函数和变量都对应的一个'字典'[特征字符串],这些tools都是通过查找这些字典,然后跟踪变量来分析代码.

但是随着程序员安全意识的提高,很多的程序员也知道了这些'字典'了,都有对应的过滤,所以那些传统的问题,很找在大型程序里出现了.所以只有通过扩大我们的字典才有更多的机会去找到应用程序的漏洞.我们的途径有:

* 分析和学习别人发现的漏洞或者exp,如大牛Stefan Esser发现的那些问题,rgod等以前发的那些exp
* 通过学习php手册或者官方文档了解php 一些函数的'特性'
* fuzz php的函数,找到新的有问题的函数[不一定非要溢出的]
* 分析php源代码,发现新的漏洞函数'特性'或者漏洞
* 有条件或者机会和开发者学习,找到他们实现某些常用功能的代码的缺陷或者容易忽视的问题
* 你有什么要补充的吗? 🙂
from:http://hi.baidu.com/hi_heige/blog/item/2ac6ab003fea1105738da5a3.html

PHP代码审计

目录

1. 概述 3

2. 输入验证和输出显示 3

2.1 命令注入 4
2.2 跨站脚本 4
2.3 文件包含 5
2.4 代码注入 5
2.5 SQL注入 6
2.6 XPath注入 6
2.7 HTTP响应拆分 6

2.8 文件管理 6
2.9 文件上传 7
2.10 变量覆盖 7
2.11 动态函数 7

3. 会话安全 8

3.1 HTTPOnly设置 8
3.2 domain设置 8
3.3 path设置 8
3.4 cookies持续时间 8
3.5 secure设置 8
3.6 session固定 9
3.7 CSRF 9

4. 加密 9

4.1 明文存储密码 9
4.2 密码弱加密 9
4.3 密码存储在攻击者能访问到的文件 9

5. 认证和授权 10

5.1 用户认证 10
5.2 函数或文件的未认证调用 10
5.3 密码硬编码 10

6. 随机函数 10

6.1 rand() 10
6.2 mt_srand()和mt_rand() 11

7. 特殊字符和多字节编码 11

7.1 多字节编码 11

8. PHP危险函数 11

8.1 缓冲区溢出 11
8.2 session_destroy()删除文件漏洞 12
8.3 unset()-zend_hash_del_key_or_index漏洞 12

9. 信息泄露 13

9.1 phpinfo 13

10. PHP环境 13

10.1 open_basedir设置 13
10.2 allow_url_fopen设置 13
10.3 allow_url_include设置 13
10.4 safe_mode_exec_dir设置 14
10.5 magic_quote_gpc设置 14
10.6 register_globals设置 14
10.7 safe_mode设置 14
10.8 session_use_trans_sid设置 14
10.9 display_errors设置 14
10.10 expose_php设置 14

1.概述

代码审核,是对应用程序源代码进行系统性检查的工作。它的目的是为了找到并且修复应用程序在开发阶段存在的一些漏洞或者程序逻辑错误,避免程序漏洞被非法利用给企业带来不必要的风险。

代码审核不是简单的检查代码,审核代码的原因是确保代码能安全的做到对信息和资源进行足够的保护,所以熟悉整个应用程序的业务流程对于控制潜在的风险是非常重要的。审核人员可以使用类似下面的问题对开发者进行访谈,来收集应用程序信息。

应用程序中包含什么类型的敏感信息,应用程序怎么保护这些信息的?

应用程序是对内提供服务,还是对外?哪些人会使用,他们都是可信用户么?

应用程序部署在哪里?

应用程序对于企业的重要性?

最好的方式是做一个checklist,让开发人员填写。Checklist能比较直观的反映应用程序的信息和开发人员所做的编码安全,它应该涵盖可能存在严重漏洞的模块,例如:数据验证、身份认证、会话管理、授权、加密、错误处理、日志、安全配置、网络架构。

2.输入验证和输出显示

大多数漏洞的形成原因主要都是未对输入数据进行安全验证或对输出数据未经过安全处理,比较严格的数据验证方式为:

1.对数据进行精确匹配
2.接受白名单的数据
3.拒绝黑名单的数据
4.对匹配黑名单的数据进行编码

在PHP中可由用户输入的变量列表如下:

$_SERVER

$_GET

$_POST

$_COOKIE

$_REQUEST

$_FILES

$_ENV

$_HTTP_COOKIE_VARS

$_HTTP_ENV_VARS

$_HTTP_GET_VARS

$_HTTP_POST_FILES

$_HTTP_POST_VARS

$_HTTP_SERVER_VARS

我们应该对这些输入变量进行检查


1.命令注入

PHP执行系统命令可以使用以下几个函数:system、exec、passthru、“、shell_exec、popen、proc_open、pcntl_exec
我们通过在全部程序文件中搜索这些函数,确定函数的参数是否会因为外部提交而改变,检查这些参数是否有经过安全处理。

防范方法:

1.使用自定义函数或函数库来替代外部命令的功能

2.使用escapeshellarg函数来处理命令参数

3.使用safe_mode_exec_dir指定可执行文件的路径

2.跨站脚本

反 射型跨站常常出现在用户提交的变量接受以后经过处理,直接输出显示给客户端;存储型跨站常常出现在用户提交的变量接受过经过处理后,存储在数据库里,然后 又从数据库中读取到此信息输出到客户端。输出函数经常使用:echo、print、printf、vprintf、< %=$test%>

对于反射型跨站,因为是立即输出显示给客户端,所以应该在当前的php页面检查变量被客户提交之后有无立即显示,在这个过程中变量是否有经过安全检查。

对于存储型跨站,检查变量在输入后入库,又输出显示的这个过程中,变量是否有经过安全检查。

防范方法:

1.如果输入数据只包含字母和数字,那么任何特殊字符都应当阻止

2.对输入的数据经行严格匹配,比如邮件格式,用户名只包含英文或者中文、下划线、连字符

3.对输出进行HTML编码,编码规范

< < > >

( (

) )

# #

& &

” “

‘ ‘

` %60

3.文件包含

PHP可能出现文件包含的函数:include、include_once、require、require_once、show_source、highlight_file、readfile、file_get_contents、fopen、file

防范方法:

1.对输入数据进行精确匹配,比如根据变量的值确定语言en.php、cn.php,那么这两个文件放在同一个目录下’language/’.$_POST[‘lang’].’.php’,那么检查提交的数据是否是en或者cn是最严格的,检查是否只包含字母也不错

2.通过过滤参数中的/、..等字符

4.代码注入

PHP可能出现代码注入的函数:eval、preg_replace+/e、assert、call_user_func、call_user_func_array、create_function

查找程序中程序中使用这些函数的地方,检查提交变量是否用户可控,有无做输入验证

防范方法:

1.输入数据精确匹配

2.白名单方式过滤可执行的函数

5.SQL注入

SQL注入因为要操作数据库,所以一般会查找SQL语句关键字:insert、delete、update、select,查看传递的变量参数是否用户可控制,有无做过安全处理

防范方法:

使用参数化查询

6.XPath注入

Xpath用于操作xml,我们通过搜索xpath来分析,提交给xpath函数的参数是否有经过安全处理

防范方法:

对于数据进行精确匹配

7.HTTP响应拆分

PHP中可导致HTTP响应拆分的情况为:使用header函数和使用$_SERVER变量。注意PHP的高版本会禁止HTTP表头中出现换行字符,这类可以直接跳过本测试。

防范方法:

1.精确匹配输入数据

2.检测输入输入中如果有\r或\n,直接拒绝

8.文件管理

PHP 的用于文件管理的函数,如果输入变量可由用户提交,程序中也没有做数据验证,可能成为高危漏洞。我们应该在程序中搜索如下函数:copy、rmdir、 unlink、delete、fwrite、chmod、fgetc、fgetcsv、fgets、fgetss、file、 file_get_contents、fread、readfile、ftruncate、file_put_contents、fputcsv、 fputs,但通常PHP中每一个文件操作函数都可能是危险的。

http://ir.php.net/manual/en/ref.filesystem.php

防范方法:

1.对提交数据进行严格匹配

2.限定文件可操作的目录

9.文件上传

PHP文件上传通常会使用move_uploaded_file,也可以找到文件上传的程序进行具体分析

防范方式:

1.使用白名单方式检测文件后缀

2.上传之后按时间能算法生成文件名称

3.上传目录脚本文件不可执行

4.注意%00截断

10.变量覆盖

PHP变量覆盖会出现在下面几种情况:

1.遍历初始化变量

例:

foreach($_GET as $key => $value)

$$key = $value;

2.函数覆盖变量:parse_str、mb_parse_str、import_request_variables

3.Register_globals=ON时,GET方式提交变量会直接覆盖

防范方法:

1.设置Register_globals=OFF

2.不要使用这些函数来获取变量

11.动态函数

当使用动态函数时,如果用户对变量可控,则可导致攻击者执行任意函数。

例:

< ?php $myfunc = $_GET['myfunc']; $myfunc(); ?>

防御方法:

不要这样使用函数

3.会话安全

1.HTTPOnly设置

session.cookie_httponly = ON时,客户端脚本(JavaScript等)无法访问该cookie,打开该指令可以有效预防通过XSS攻击劫持会话ID

2.domain设置

检查session.cookie_domain是否只包含本域,如果是父域,则其他子域能够获取本域的cookies

3.path设置

检查session.cookie_path,如果网站本身应用在/app,则path必须设置为/app/,才能保证安全

4.cookies持续时间

检查session.cookie_lifetime,如果时间设置过程过长,即使用户关闭浏览器,攻击者也会危害到帐户安全

5.secure设置

如果使用HTTPS,那么应该设置session.cookie_secure=ON,确保使用HTTPS来传输cookies

6.session固定

如果当权限级别改变时(例如核实用户名和密码后,普通用户提升到管理员),我们就应该修改即将重新生成的会话ID,否则程序会面临会话固定攻击的风险。

7.CSRF

跨站请求伪造攻击,是攻击者伪造一个恶意请求链接,通过各种方式让正常用户访问后,会以用户的身份执行这些恶意的请求。我们应该对比较重要的程序模块,比如修改用户密码,添加用户的功能进行审查,检查有无使用一次性令牌防御csrf攻击。

4.加密

1.明文存储密码

采用明文的形式存储密码会严重威胁到用户、应用程序、系统安全。

2.密码弱加密

使用容易破解的加密算法,MD5加密已经部分可以利用md5破解网站来破解

3.密码存储在攻击者能访问到的文件

例如:保存密码在txt、ini、conf、inc、xml等文件中,或者直接写在HTML注释中

5.认证和授权

1.用户认证

检查代码进行用户认证的位置,是否能够绕过认证,例如:登录代码可能存在表单注入。

检查登录代码有无使用验证码等,防止暴力破解的手段

2.函数或文件的未认证调用

一些管理页面是禁止普通用户访问的,有时开发者会忘记对这些文件进行权限验证,导致漏洞发生

某些页面使用参数调用功能,没有经过权限验证,比如index.php?action=upload

3.密码硬编码

有的程序会把数据库链接账号和密码,直接写到数据库链接函数中。

6.随机函数

1.rand()

rand()最大随机数是32767,当使用rand处理session时,攻击者很容易破解出session,建议使用mt_rand()

2.mt_srand()和mt_rand()

PHP4和PHP5<5.2.6,这两个函数处理数据是不安全的。在web应用中很多使用mt_rand来处理随机的session,比如密码找回功能等,这样的后果就是被攻击者恶意利用直接修改密码。

7.特殊字符和多字节编码

1.多字节编码

8.PHP危险函数

1.缓冲区溢出

confirm_phpdoc_compiled

影响版本:

phpDocumentor phpDocumentor 1.3.1

phpDocumentor phpDocumentor 1.3 RC4

phpDocumentor phpDocumentor 1.3 RC3

phpDocumentor phpDocumentor 1.2.3

phpDocumentor phpDocumentor 1.2.2

phpDocumentor phpDocumentor 1.2.1

phpDocumentor phpDocumentor 1.2

mssql_pconnect/mssql_connect

影响版本:PHP < = 4.4.6

crack_opendict

影响版本:PHP = 4.4.6

snmpget

影响版本:PHP <= 5.2.3

ibase_connect

影响版本:PHP = 4.4.6

unserialize

影 响版本:PHP 5.0.2、PHP 5.0.1、PHP 5.0.0、PHP 4.3.9、PHP 4.3.8、PHP 4.3.7、PHP 4.3.6、PHP 4.3.3、PHP 4.3.2、PHP 4.3.1、PHP 4.3.0、PHP 4.2.3、PHP 4.2.2、PHP 4.2.1、PHP 4.2.0、PHP 4.2-dev、PHP 4.1.2、PHP 4.1.1、PHP 4.1.0、PHP 4.1、PHP 4.0.7、PHP 4.0.6、PHP 4.0.5、PHP 4.0.4、PHP 4.0.3pl1、PHP 4.0.3、PHP 4.0.2、PHP 4.0.1pl2、PHP 4.0.1pl1、PHP 4.0.1

2.session_destroy()删除文件漏洞

影响版本:不祥,需要具体测试

测试代码如下:

view sourceprint?01 <?php  

02 session_save_path(‘./’);  

03 session_start();  

04 if($_GET[‘del’]) {  

05 session_unset();  

06 session_destroy();  

07 }else{  

08 $_SESSION[‘do’]=1;  

09 echo(session_id());  

10 print_r($_SESSION);  

11 }  

12 ?> 

当我们提交cookie:PHPSESSIONID=/../1.php,相当于删除了此文件

3.unset()-zend_hash_del_key_or_index漏洞

zend_hash_del_key_or_index PHP4小于4.4.3和PHP5小于5.1.3,可能会导致zend_hash_del删除了错误的元素。当PHP的unset()函数被调用时,它会阻止变量被unset。

9.信息泄露

1.phpinfo

如果攻击者可以浏览到程序中调用phpinfo显示的环境信息,会为进一步攻击提供便利

10.PHP环境

1.open_basedir设置

open_basedir能限制应用程序能访问的目录,检查有没有对open_basedir进行设置,当然有的通过web服务器来设置,例如:apache的php_admin_value,nginx+fcgi通过conf来控制php设置

2.allow_url_fopen设置

如果allow_url_fopen=ON,那么php可以读取远程文件进行操作,这个容易被攻击者利用

3.allow_url_include设置

如果allow_url_include=ON,那么php可以包含远程文件,会导致严重漏洞

4.safe_mode_exec_dir设置

这个选项能控制php可调用的外部命令的目录,如果PHP程序中有调用外部命令,那么指定外部命令的目录,能控制程序的风险

5.magic_quote_gpc设置

这个选项能转义提交给参数中的特殊字符,建议设置magic_quote_gpc=ON

6.register_globals设置

开启这个选项,将导致php对所有外部提交的变量注册为全局变量,后果相当严重

7.safe_mode设置

safe_mode是PHP的重要安全特性,建议开启

8.session_use_trans_sid设置

如果启用 session.use_trans_sid,会导致 PHP 通过 URL 传递会话 ID,这样一来,攻击者就更容易劫持当前会话,或者欺骗用户使用已被攻击者控制的现有会话。

9.display_errors设置

如果启用此选项,PHP将输出所有的错误或警告信息,攻击者能利用这些信息获取web根路径等敏感信息

10.expose_php设置

如果启用 expose_php 选项,那么由 PHP 解释器生成的每个响应都会包含主机系统上所安装的 PHP 版本。了解到远程服务器上运行的 PHP 版本后,攻击者就能针对系统枚举已知的盗取手段,从而大大增加成功发动攻击的机会。

参考文档:

https://www.fortify.com/vulncat/zh_CN/vulncat/index.html

http://secinn.appspot.com/pstzine/read?issue=3&articleid=6

http://riusksk.blogbus.com/logs/51538334.html

http://www.owasp.org/index.php/Category:OWASP_Code_Review_Project

C与C++在Linux下的混合编译问题

最近遇到一个挺挠头的技术问题,我们波士顿那边客户公司的代码是既有C++又有C,我们作为外包公司,需要把我们的C++代码与他们的集成起 来,原先的集成方案是我们的C++与他们的C++揉在一起,这样不Touch任何C集成的冬冬,我当时在波士顿已经搞定了此问题,但出差回来前客户提出要 优化系统效率,其意思就是想让我们更多地重用他们的C代码,这样集成C与C++的任务逐渐提上日程。
 

网上有很多讨论这方面的中英文文章,但感觉不是很全面,等我使用这些方法搞不定时,没有提供一个全面系统的分析解决问题的思路,我摘选了其中一篇:http://www.pconline.com.cn/pcedu/empolder/gj/c/0508/693175_3.html,文章有四个部分,

前三个部分属于科普,可以不看,最后一个部分讲述了C++调用C和C调用C++的两个范例,甚是有用,我总结一下:
 

(1)C++调用C的问题:
在C++的File中,加入C的头文件,一般情况下需要加extern "C", 但这点不是铁律,后面我会专门讲这个问题,认定这点有时会死得比较惨。建议原文范例中增加__cplusplus宏比较好一些,例如:
#if defined(__cplusplus)
extern "C"
{
#endif
#include "cExample.h" //头文件声明
#if defined(__cplusplus)
}

#endif
 

加extern "C"的原因是因为C++在编译函数名时加入了很多其他怪异字符,这点是C++语言为了支持重载overload的特性以及其它特性所不得不加的冬冬,但 C是朴素型,编译出来的符号表就是代码里的函数名。加了extern C后,编译器就会按照C的命名方式将C++引用C代码的地方使用C方式的函数名,避免引用和定义出现命名的不一致。但有一个问题是这一点取决于特定的编译 器,而不是绝对的,我在.NET的VC7下拿我们的工程做了个试验没有问题,但在Linux的g++下就歇了,原因是什么?Window下的nmake在 编译时使用的原则是:C代码按照C的命名方式编译引用点和函数定义,可是g++就是另外一回事了,它对C的代码采取的是C++的命名方式,怎么印证这个问 题呢,下面我来介绍一下Linux下的两个工具nm和objdump, 命令如下:
objdump -x (Obj文件名) , nm (Obj文件名)
下面给出更详尽的测试依据,例如C代码中的PP__sctp函数在g++编译后的符号表就变了,
nm mylib.a |grep PP__sctp
结果是:
               U _Z8PP__sctpPKcmm
000000c0 B V__PP__sctp
00000040 T _Z8PP__sctpPKcmm
看到了吧!U是引用点的函数符号,T的定义点的函数符号,如果你在调用时加了extern "C",编译后,肯定会有一条错误说:undefined reference "PP__sctp".

这就是我要讲的第一个问题,C,C++集成编译时需要看具体的编译环境和工具,充分利用你手头的工具帮你来分析和定位问题。

(2) C调C++的问题,具体可以参看前面说的文章,非常有用,要点是:C调用C++,通过extern 变量或函数的外部声明,而不用include头文件方式。但前面提到的第一个问题依然会在不同的编译器下重演,你需要定位分析,看是否需要加extern "C",只要耐心一些,就会快速定位和解决问题。

我这里提到的第二个问题是在复杂工程下会出现的问题,我 们的工程巨大,六千多个文件,和我们相关的就有7,8百个,最后在链接时,出了问题是几个静态库互相引用,打成了死结,因为g++ 通过-l选项加入库的顺序也是有讲究的,先引用的库可以使用后引用库的函数和变量,但反过来则不行。
这里介绍一个办法,利用拓扑分析,把几个库的引用关系用圈和箭头表示出来,就像分析最短路径那样,如果发现是个环状拓扑,只管把它们加入到一个库中即可,当然这是在Linux下,Windows下我不Sure是否会出现类似问题。

Long Long、__int64使用总结

前言:
在16位环境下,int/unsigned int 占16位,long/unsigned long占32位
在32位环境下,int占32位,unsigned int占16位,long/unsigned long占32位
何时需要使用
long 和 int 范围是[-2^31,2^31),即-2147483648~2147483647,而unsigned范围是[0,2^32),即0~4294967295,所以常规的32位整数只能够处理40亿左右,
遇到比40亿大的多的数就要用到64位
64位使用范围:
不 同的编译器对64位整数的扩展有所不同,VC使用__int64/unsigned __int64,范围是[-2^63, 2^63)和[0,2^64),即-9223372036854775808~9223372036854775807与 0~18446744073709551615(约1800亿亿)。

注意点:
1、编译器不同导致使用64位的申明方式不同;
2、long long / unsigned long long 一般是Linux下申明方式、如:G++
3、__int64 /unsigned __int64一般是Windows下使用64位的申明方式,如:VS
4、在赋值时需要注意加上ll进行显式赋值;
5、当进行64位与 32位的混合运算时,32位整数会被隐式转换成64位整数。
6、输出printf("");,long long使用%lld输出,__int64使用%I64d,无符号使用u替代d即可。
7、测试下来编译器一般都支持2种操作,不必太过纠结,怎么使用看个人喜欢。

//=================================华丽的分隔线========================================
#include <stdio.h>
#include <stdlib.h>
intmain(){
    unsigned long longa= 412432424000ll;
    unsigned __int64b= 9223372036854775808ll;
    printf("%I64u\n",a);                 //使用%lld时无法正常输出,why? 解答在附
    printf("%I64u",b);
    system("pause");
    return 0;
}
附网友测试结果:
   刚实验了下,在VC6、DEV、CodeBlocks中C语言都可以使用__int64,格式化输出标识为%I64d。不过在VC6中数字后加2个L是 会报错,可以只加1个或不加。查了下资料,__int64是windows专用的,被vc、gcc等编译器支持,但在在UNIX、Linux中需用 long long配合%lld。后者是标准C的规定!
  我试了下long long配合%I64d,可以正确输出,而不管是long long还是__int64配合%lld都不能正确输出。所以我得出的结论是在windows下需要用longlong或,__int64配合%64d。而在UNIX、Linux中必须使用标准C规定的long long配合%lld。
记。

海量数据处理:十道面试题与十个海量数据处理方法总结

第一部分、十道海量数据处理面试题

1、海量日志数据,提取出某日访问百度次数最多的那个IP。

      首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法, 比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大 的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

或者如下阐述(雪域之鹰):
算法思想:分而治之+Hash
1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理; 
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址; 
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;

Continue reading "海量数据处理:十道面试题与十个海量数据处理方法总结"

nocreate is not a member of std::ios

ios::nocreate是在C++标准制定之前在 <fstream.h> 中有定义的。

但是因为它跟系统平台相关密切,所以在C++标准中去掉了对它的支持。

如果想实现它的功能,可以这样编写一段程序:
// void main()
int main()
{
string str;
cin > > str;
// you should check if <str> is a valid file name here
// ifstream fin;
// fin.open(str.c_str(),ios::nocreate);
fstream fs(str.c_str(), ios_base::in); // open file for reading
if (!fs) // file not exist
{
// do nothing
}
else // file exists. close and re-open for writing
{
fs.close();
fs.open(str.c_str(), ios_base::out); // reopen for writing
}

C++ 中标准库 map 和 hash_map 的使用方法

1。目录

  1. map简介
  2. map的功能
  3. 使用map
  4. 在map中插入元素
  5. 查找并获取map中的元素
  6. 从map中删除元素

2。map简介

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小,除了那个操作节点,对其他的节点都没有什么影响。对于迭代器来说,可以修改实值,而不能修改key。

 

3。map的功能

  1. 自动建立Key - value的对应。key 和 value可以是任意你需要的类型。
  2. 根据key值快速查找记录,查找的复杂度基本是Log(N),如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次。
  3. 快速插入Key - Value 记录。
  4. 快速删除记录
  5. 根据Key 修改value记录。
  6. 遍历所有记录。

4。使用map

使用map得包含map类所在的头文件
#include <map> //注意,STL头文件没有扩展名.h

map对象是模板类,需要关键字和存储对象两个模板参数:
std:map<int, string> personnel;
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.

为了使用方便,可以对模板类进行一下类型定义,

typedef map<int, CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;

 

5。在map中插入元素

改变map中的条目非常简单,因为map类已经对[]操作符进行了重载

enumMap[1] = "One";
enumMap[2] = "Two";
.....

这样非常直观,但存在一个性能的问题。插入2时,先在enumMap中查找主键为2的项,没发现,然后将一个新的对象插入enumMap,键是2,值是一个空字符串,插入完成后,将字符串赋为"Two"; 该方法会将每个值都赋为缺省值,然后再赋为显示的值,如果元素是类对象,则开销比较大。我们可以用以下方法来避免开销:

enumMap.insert(map<int, CString> :: value_type(2, "Two"))

 

6。查找并获取map中的元素

下标操作符给出了获得一个值的最简单方法:

CString tmp = enumMap[2];

但是,只有当map中有这个键的实例时才对,否则会自动插入一个实例,值为初始化值

我们可以使用Find()和Count()方法来发现一个键是否存在。

查找map中是否包含某个关键字条目用find()方法,传入的参数是要查找的key,在这里需要提到的是begin()和end()两个成员,分别代表map对象中第一个条目和最后一个条目,这两个数据的类型是iterator.

int nFindKey = 2;            //要查找的Key
//定义一个条目变量(实际是指针)
UDT_MAP_INT_CSTRING::iterator it= enumMap.find(nFindKey); 
if(it == enumMap.end()) {
    //没找到
}
else {
    //找到
}

通过map对象的方法获取的iterator数据类型是一个std::pair对象,包括两个数据 iterator->first 和 iterator->second 分别代表关键字和存储的数据

 

7。从map中删除元素

移除某个map中某个条目用erase()

该成员方法的定义如下

  1. iterator erase(iterator it); //通过一个条目对象删除
  2. iterator erase(iterator first, iterator last);        //删除一个范围
  3. size_type erase(const Key& key); //通过关键字删除

clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());

 

 

 

STL hash_map简介

         hash_map的用法和map是一样的,提供了 insert,size,count等操作,并且里面的元素也是以pair类型来存贮的。虽然对外部提供的函数和数据类型是一致的,但是其底层实现是完全不同的,map底层的数据结构是rb_tree而,hansh_map却是哈希表来实现的。

void main()
{//简单的一个列子,其使用方法和map是一样的。
hash_map<int,string> hmap;//定义一个实例
hmap.insert(pair<int,string>(10,"sfsfd"));//插入一个pair对象,

hmap.insert(hash_map<int,string>::value_type(34,"sddsf"));//value_type就是pair类型的

hmap[23] = "23";
hmap[33] = "33";
hmap[-1] = "-1";
hash_map<int,string>::iterator it = hmap.begin();
while(it!=hmap.end())//遍历
   cout<<it->first<<"\t"<<it++->second<<endl;
it = hmap.find(23);//查找
if(it!=hmap.end())
   PRINT(it);
cout<<hmap.size()<<endl;
cout<<hmap.count(58)<<endl;
cout<<hmap.empty()<<endl;
hash_map<int,string>::const_reverse_iterator cit = hmap.rend();
PRINT(cit);
}

从上面的列子可以看到,使用起来是没什么困难的,很方便。但是我们什么时候要用map,什么时候用hash_map呢?

map与hash_map

     总 体来说,hash_map 查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。hash还有hash函数的耗时。当有100w条记录的时候,map也只需要20次的比较,200w也只需要21次的比较!所以并不一定常数就比log(n) 小!

    hash_map对空间的要求要比map高很多,所以是以空间换时间的方法,而且,hash_map如果hash函数和hash因子选择不好的话,也许不会达到你要的效果,所以至于用map,还是hash_map,从3个方面来权衡: 查找速度, 数据量, 内存使用,还有一个就是你的经验!没有特别的标准

另外可以通过重写 hash_compair仿函数,更改里面关于桶数量的定义,如果取值合适,也可以得到更优的性能。而且如果你的数据是自定义的类型,必须要重写这个仿函数。可以模仿原来的写法,所有的成员函数,成员变量一个不能少!

C++ hash_map 详细介绍

为什么需要hash_map
用过map吧?map提供一个很常用的功能,那就是提供key-value的存储和查找功能。例如,我要记录一个人名和相应的存储,而且随时增加,要快速查找和修改:

岳不群-华山派掌门人,人称君子剑
张三丰-武当掌门人,太极拳创始人
东方不败-第一高手,葵花宝典
...

这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找"张三丰"的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。如 果要速度快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同时需要保持记录有序,因此需要插入排序。考虑到效率,这就需要 用到二叉树。讲下去会没完没了,如果你使用STL 的map容器,你可以非常方便的实现这个功能,而不用关心其细节。关于map的数据结构细节,感兴趣的朋友可以参看学习STL map, STL set之数据结构基础。看看map的实现:

#include <map>
#include <string>
using namespace std;
...
map<string, string> namemap;
//增加。。。
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";
...
//查找。。
if(namemap.find("岳不群") != namemap.end()){
...
}


不觉得用起来很easy吗?而且效率很高,100万条记录,最多也只要20次的string.compare的比较,就能找到你要找的记录;200万条记录事,也只要用21次的比较。

速度永远都满足不了现实的需求。如果有100万条记录,我需要频繁进行搜索时,20次比较也会成为瓶颈,要是能降到一次或者两次比较是否有可能?而且当记录数到200万的时候也是一次或者两次的比较,是否有可能?而且还需要和map一样的方便使用。

答案是肯定的。这时你需要has_map. 虽然hash_map目前并没有纳入C++ 标准模板库中,但几乎每个版本的STL都提供了相应的实现。而且应用十分广泛。在正式使用hash_map之前,先看看hash_map的原理。
1 数据结构:hash_map原理
这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。

hash_map基于hash table(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当 前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

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

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

   1. 得到key
   2. 通过hash函数得到hash值
   3. 得到桶号(一般都为hash值对桶数求模)
   4. 存放key和value在桶内。

其取值过程是:

   1. 得到key
   2. 通过hash函数得到hash值
   3. 得到桶号(一般都为hash值对桶数求模)
   4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。
   5. 取出相等的记录的value。

hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).

由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。
2 hash_map 使用
2.1 一个简单实例
不要着急如何把"岳不群"用hash_map表示,我们先看一个简单的例子:随机给你一个ID号和ID号相应的信息,ID号的范围是1~2的31次方。如何快速保存查找。

#include <hash_map>
#include <string>
using namespace std;
int main(){
hash_map<int, string> mymap;
mymap[9527]="唐伯虎点秋香";
mymap[1000000]="百万富翁的生活";
mymap[10000]="白领的工资底线";
...
if(mymap.find(10000) != mymap.end()){
...
}

够简单,和map使用方法一样。这时你或许会问?hash函数和比较函数呢?不是要指定么?你说对了,但是在你没有指定hash函数和比较函数的时候,你会有一个缺省的函数,看看hash_map的声明,你会更加明白。下面是SGI STL的声明:

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<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;

Alloc我们就不要取关注太多了(希望深入了解Allocator的朋友可以参看标准库 STL :Allocator能做什么)
2.2 hash_map 的hash函数
hash< int>到底是什么样子?看看源码:

struct hash<int> {
size_t operator()(int __x) const { return __x; }
};

原来是个函数对象。在SGI STL中,提供了以下hash函数:

struct hash<char*>
struct hash<const char*>
struct hash<char>
struct hash<unsigned char>
struct hash<signed char>
struct hash<short>
struct hash<unsigned short>
struct hash<int>
struct hash<unsigned int>
struct hash<long>
struct hash<unsigned long>

也就是说,如果你的key使用的是以上类型中的一种,你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量,你只能如此,例如对于string,就必须自定义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);
}
};
//如果你希望利用系统定义的字符串hash函数,你可以这样写:
struct str_hash{
size_t operator()(const string& str) const
{
return return __stl_hash_string(str.c_str());
}
};

在声明自己的哈希函数时要注意以下几点:

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

如果这些比较难记,最简单的方法就是照猫画虎,找一个函数改改就是了。

现在可以对开头的"岳不群"进行哈希化了 smile . 直接替换成下面的声明即可:

map<string, string> namemap;
//改为:
hash_map<string, string, str_hash> namemap;

其他用法都不用边。当然不要忘了吧str_hash的声明以及头文件改为hash_map。

你或许会问:比较函数呢?别着急,这里就开始介绍hash_map中的比较函数。
2.3 hash_map 的比较函数
在map中的比 较函数,需要提供less函数。如果没有提供,缺省的也是less< Key> 。在hash_map中,要比较桶内的数据和key是否相等,因此需要的是是否等于的函数:equal_to< Key> 。先看看equal_to的源码:

//本代码可以从SGI STL
//先看看binary_function 函数声明,其实只是定义一些类型而已。
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//看看equal_to的定义:
template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

如果你使用一个自定义的数据类型,如struct mystruct, 或者const char* 的字符串,如何使用比较函数?使用比较函数,有两种方法. 第一种是:重载==操作符,利用equal_to;看看下面的例子:

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;
}
};

有了compare_str,就可以使用hash_map了。

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

2.4 hash_map 函数
hash_map的函数和map的函数差不多。具体函数的参数和解释,请参看:STL 编程手册:Hash_map,这里主要介绍几个常用函数。

   1. hash_map(size_type n) 如果讲究效率,这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多,hash函数发生冲突的概率就越小,重新申请内存的概率就越小。n越大,效率越高,但是内存消耗也越大。
   2. const_iterator find(const key_type& k) const. 用查找,输入为键值,返回为迭代器。
   3. data_type& operator[](const key_type& k) . 这是我最常用的一个函数。因为其特别方便,可像使用数组一样使用。不过需要注意的是,当你使用[key ]操作符时,如果容器中没有key元素,这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时,你可以使用find。如果你 希望插入该元素时,你可以直接使用[]操作符。
   4. insert 函数。在容器中不包含key值时,insert函数和[]操作符的功能差不多。但是当容器中元素越来越多,每个桶中的元素会增加,为了保证效 率,hash_map会自动申请更大的内存,以生成更多的桶。因此在insert以后,以前的iterator有可能是不可用的。
   5. erase 函数。在insert的过程中,当每个桶的元素太多时,hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后,其他元素的iterator还是可用的。

3 相关hash容器
hash 容器除了hash_map之外,还有hash_set, hash_multimap, has_multiset, 这些容器使用起来和set, multimap, multiset的区别与hash_map和map的区别一样,我想不需要我一一细说了吧。
4 其他
这里列几个常见问题,应该对你理解和使用hash_map比较有帮助。
4.1 hash_map和map的区别在哪里?

    * 构造函数。hash_map需要hash函数,等于函数;map只需要比较函数(小于函数).
    * 存储结构。hash_map采用hash表存储,map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。

4.2 什么时候需要用hash_map,什么时候需要用map?
总体来说,hash_map 查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。

现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

这里还有个关于hash_map和map的小故事,看看:http://dev.csdn.net/Develop/article/14/14019.shtm

4.3 如何在hash_map中加入自己定义的类型?
你只要做两件事, 定义hash函数,定义等于比较函数。下面的代码是一个例子:

-bash-2.05b$ cat my.cpp
#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;
}
-bash-2.05b$ make my
c++  -O -pipe -march=pentiumpro  my.cpp  -o my
-bash-2.05b$ ./my
I am 12
I am 198877

typedef map<Key, Value> KeyMap;

当你希望使用hash_map来替换的时候,只需要修改:

typedef hash_map<Key, Value> KeyMap;

其他的基本不变。当然,你需要注意是否有Key类型的hash函数和比较函数。
4.5为什么hash_map不是标准的?
具体为什么不是标准的,我也不清楚,有个解释说在STL加入标准C++之时,hash_map系列当时还没有完全实现,以后应该会成为标准。如果 谁知道更合理的解释,也希望告诉我。但我想表达的是,正是因为hash_map不是标准的,所以许多平台上安装了g++编译器,不一定有hash_map 的实现。我就遇到了这样的例子。因此在使用这些非标准库的时候,一定要事先测试。另外,如果考虑到平台移植,还是少用为佳。
4.6 有学习使用hash_map的建议吗?
hash中文是哈希,也成为散列,听见别人说散列容器不要埋怨自己孤陋寡闻。了解hash系列,你还可以看看这篇文章:effective STL 25: 熟悉非标准散列容器, 另外建议查看源代码。如果还有问题,那么你可以在STL论坛上提问,会有高手回答你的。

C++ STL map的使用

1、map简介

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小,除了那个操

作节点,对其他的节点都没有什么影响。对于迭代器来说,可以修改实值,而不能修改key。

 

2、map的功能

自 动建立Key - value的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录,查找的复杂度基本是Log(N),如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次。 快速插入Key - Value 记录。 快速删除记录 根据Key 修改value记录。 遍历所有记录。
 

3、使用map

使用map得包含map类所在的头文件

#include <map> //注意,STL头文件没有扩展名.h

map对象是模板类,需要关键字和存储对象两个模板参数:

std:map<int, string> personnel;

这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.

为了使用方便,可以对模板类进行一下类型定义,

typedef map<int, CString> UDT_MAP_INT_CSTRING;

UDT_MAP_INT_CSTRING enumMap;

 

4、在map中插入元素

改变map中的条目非常简单,因为map类已经对[]操作符进行了重载

enumMap[1] = "One";

enumMap[2] = "Two";

.....

这样非常直观,但存在一个性能的问题。插入2时,先在enumMap中查找主键为2的项,没

发现,然后将一个新的对象插入enumMap,键是2,值是一个空字符串,插入完成后,

将字符串赋为"Two"; 该方法会将每个值都赋为缺省值,然后再赋为显示的值,如果元素

是类对象,则开销比较大。我们可以用以下方法来避免开销:

enumMap.insert(map<int, CString> :: value_type(2, "Two"))

 

5、查找并获取map中的元素

下标操作符给出了获得一个值的最简单方法:

CString tmp = enumMap[2];

但是,只有当map中有这个键的实例时才对,否则会自动插入一个实例,值为初始化值。

我们可以使用Find()和Count()方法来发现一个键是否存在。

查找map中是否包含某个关键字条目用find()方法,传入的参数是要查找的key,在这里

需要提到的是begin()和end()两个成员,分别代表map对象中第一个条目和最后一个条

目,这两个数据的类型是iterator.

int nFindKey = 2; //要查找的Key

//定义一个条目变量(实际是指针)

UDT_MAP_INT_CSTRING::iterator it= enumMap.find(nFindKey);

if(it == enumMap.end()) {

//没找到

}

else {

//找到

}

通过map对象的方法获取的iterator数据类型是一个std::pair对象,包括两个数据

 iterator->first

 和 iterator->second 分别代表关键字和存储的数据

 

6、从map中删除元素

移除某个map中某个条目用erase()

该成员方法的定义如下

iterator erase(iterator it); //通过一个条目对象删除 iterator erase(iterator first, iterator last); //删除一个范围 size_type erase(const Key& key); //通过关键字删除

clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());

C++ STL map的使用

以下是对C++中STL map的插入,查找,遍历及删除的例子:

#include <map>
#include <string>
#include <iostream>
using namespace std;

void map_insert(map < string, string > *mapStudent, string index, string x)
{
mapStudent->insert(map < string, string >::value_type(index, x));
}

int main(int argc, char **argv)
{
char tmp[32] = "";
map < string, string > mapS;

//insert element
map_insert(&mapS, "192.168.0.128", "xiong");
map_insert(&mapS, "192.168.200.3", "feng");
map_insert(&mapS, "192.168.200.33", "xiongfeng");

map < string, string >::iterator iter;

cout << "We Have Third Element:" << endl;
cout << "-----------------------------" << endl;

//find element
iter = mapS.find("192.168.0.33");
if (iter != mapS.end()) {
cout << "find the elememt" << endl;
cout << "It is:" << iter->second << endl;
} else {
cout << "not find the element" << endl;
}

//see element
for (iter = mapS.begin(); iter != mapS.end(); iter ) {

cout << "| " << iter->first << " | " << iter->
second << " |" << endl;

}
cout << "-----------------------------" << endl;

map_insert(&mapS, "192.168.30.23", "xf");

cout << "After We Insert One Element:" << endl;
cout << "-----------------------------" << endl;
for (iter = mapS.begin(); iter != mapS.end(); iter ) {

cout << "| " << iter->first << " | " << iter->
second << " |" << endl;

}

cout << "-----------------------------" << endl;

//delete element
iter = mapS.find("192.168.200.33");
if (iter != mapS.end()) {
cout << "find the element:" << iter->first << endl;
cout << "delete element:" << iter->first << endl;
cout << "=================================" << endl;
mapS.erase(iter);
} else {
cout << "not find the element" << endl;
}
for (iter = mapS.begin(); iter != mapS.end(); iter ) {

cout << "| " << iter->first << " | " << iter->
second << " |" << endl;

}
cout << "=================================" << endl;

return 0;
}

 

map和hash_map性能测试(2009-01-21 10:04:52)

大家都知道在C++的STL中map是使用树来做查找算法,而hash_map使用hash表来排列配对,是使用关键字来计算表位置。那使用起来他们的差 别主要是什么呢?对于性能差别是什么,适合什么情况下应用呢?于是我对它们进行了一些测试,并记录了测试数据供大家分享。
    测试的内容主要是map和hash_map的添加、删除、查找和遍历操作,首先进行了几组测试,分别是10万次、30万次,时间单位均为毫秒,具体的性能对照如下:
  hash_map(10万) map(10万) hash_map(20万) map(20万) hash_map(30万) map(30万)
添加 93   47  156   94  203   172
遍历 16   15  16   16  16   15
查找 0   0  32   31  31   32
删除 8422   32  33765   63  76016   78
    通过上面的数据比较,我们很容易发现hash_map的添加和删除操作比map要慢,尤其是删除操作hash_map比map可能慢1000倍;从而得到 结论是删除和插入操作较多的情况下,map比hash_map的性能更好,添加和删除的数据量越大越明显。但我们使用map、hash_map一般都用于 查找和遍历较多,而且上述测试数据也不能反映出这两方面的性能差距,于是继续对查找和遍历进行了性能测试,得到具体数据如下,时间单位仍为毫秒:
 hash_map(100万) map(100万) hash_map(200万) map(200万) hash_map(300万) map(300万)
遍历 94   31  203   32  297   47
查找 94   234  188   531  281   875
    通过上面的测试数据可以得出结论是map的遍历性能高于hash_map,而查找性能则相反,hash_map比map要好,数据量越大查找次数越多,表现就越好。
    两大组测试完毕,整体结论也可以得出:一般应用情况下,我们保存的数据不超过100万份,查找的频繁程度不高情况下使用map性能比较好;而保存的数据较多时(超过100万),查找频繁时使用hash_map的性能就高于map了。

测试环境具体如下:
操作系统:Windows XP Professional (5.1, Build 2600) Service Pack 3 (2600.xpsp_sp3_gdr.080814-1236)
编译环境:Microsoft Visual C++ 2005 

  55603-007-4000003-41525
处理器:Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz (2 CPUs)
内存:2044MB RAM,
     另外,整个测试仅使用物理内存,而没有虚拟内存,使用Release版本直接在控制台中运行,而没有在IDE中运行,避免影响性能;且对于较短时间计时,少于20毫秒以下可能不准确。

 

几句话道出map和hash_map的区别

1. STL map is an associative array where keys are stored in sorted order using balanced trees. While hash_map is a hashed associated container, where keys are not stored in an ordered way. Key, value pair is stored using a hashed function.
2. Insertion and lookup takes Ologn time in map, Also performance would degrade as the key size increases. Mainly balance operations on large key ranges would kill performance. while lookup is very efficient O(1) in hash_map.
3. Map is useful where you want to store keys in sorted order, hash_map is used where keys order is not important and lookup is very efficient.
4. One more difference is map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators.
Performance would mostly be o(lgn) due to the implementation of a balanced tree.
For Map custom objects you would need at the minimum the following operators to store data in a map "<" ">" "==" and of course the other stuff for deep copy.

原文地址:http://stlchina.huhoo.net/twiki/bin/view.pl/Main/STLDetailHashMap

0 为什么需要hash_map 1 数据结构:hash_map原理2 hash_map 使用 2.1 一个简单实例2.2 hash_map 的hash函数2.3 hash_map 的比较函数2.4 hash_map 函数3 相关hash容器4 其他 4.1 hash_map和map的区别在哪里?4.2 什么时候需要用hash_map,什么时候需要用map?4.3 如何在hash_map中加入自己定义的类型?4.4 如何用hash_map替换程序中已有的map容器?4.5 为什么hash_map不是标准的?4.6 有学习使用hash_map的建议吗?5 参考文章:

条条大路通罗马,为什么你不随便选一条?

0 为什么需要hash_map 用过map吧?map提供一个很常用的功能,那就是提供key-value的存储和查找功能。例如,我要记录一个人名和相应的存储,而且随时增加,要快速 查找和修改: 岳不群-华山派掌门人,人称君子剑
张三丰-武当掌门人,太极拳创始人
东方不败-第一高手,葵花宝典
...

这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找"张三丰"的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。 如果要速度快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同时需要保持记录有序,因此需要插入排序。考虑到效率,这就需 要用到二叉树。讲下去会没完没了,如果你使用STL 的map容器,你可以非常方便的实现这个功能,而不用关心其细节。关于map的数据结构细节,感兴趣的朋友可以参看学习STL map, STL set之数据结构基础。 看看map的实现:

#include <map>
#include <string>
using namespace std;
...
map<string, string> namemap;

//增加。。。
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";
...

//查找。。
if(namemap.find("岳不群") != namemap.end()){
...
}

不觉得用起来很easy吗?而且效率很高,100万条记录,最多也只要20次的string.compare的比较,就能找到你要找的记录;200万条记 录事,也只要用21次的比较。

速度永远都满足不了现实的需求。如果有100万条记录,我需要频繁进行搜索时,20次比较也会成为瓶颈,要是能降到一次或者两次比较是否有可能?而且当记 录数到200万的时候也是一次或者两次的比较,是否有可能?而且还需要和map一样的方便使用。

答案是肯定的。这时你需要has_map. 虽然hash_map目前并没有纳入C++ 标准模板库中,但几乎每个版本的STL都提供了相应的实现。而且应用十分广泛。在正式使用hash_map之前,先看看hash_map的原理。

1 数据结构:hash_map原理 这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。

hash_map基于hash table(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当 前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

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

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就 是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

得到key 通过hash函数得到hash值 得到桶号(一般都为hash值对桶数求模) 存放key和value在桶内。 其取值过程是: 得到key 通过hash函数得到hash值 得到桶号(一般都为hash值对桶数求模) 比较桶的内部元素是否与key相等,若都不相等,则没有找到。 取出相等的记录的value。 hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当 许多桶内没有值时,许多查询就会更快了(指查不到的时候).

由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

2 hash_map 使用 2.1 一个简单实例 不要着急如何把"岳不群"用hash_map表示,我们先看一个简单的例子:随机给你一个ID号和ID号相应的信息,ID号的范围是1~2的31次方。如 何快速保存查找。 #include <hash_map>
#include <string>
using namespace std;
int main(){
hash_map<int, string> mymap;
mymap[9527]="唐伯虎点秋香";
mymap[1000000]="百万富翁的生活";
mymap[10000]="白领的工资底线";
...
if(mymap.find(10000) != mymap.end()){
...
}

够简单,和map使用方法一样。这时你或许会问?hash函数和比较函数呢?不是要指定么?你说对了,但是在你没有指定hash函数和比较函数的时候,你 会有一个缺省的函数,看看hash_map的声明,你会更加明白。下面是SGI STL的声明:

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<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;

Alloc我们就不要取关注太多了(希望深入了解Allocator的朋友可以参看标准库 STL :Allocator能做什么)

2.2 hash_map 的hash函数 hash< int>到底是什么样子?看看源码: struct hash<int> {
size_t operator()(int __x) const { return __x; }
};

原来是个函数对象。在SGI STL中,提供了以下hash函数:

struct hash<char*>
struct hash<const char*>
struct hash<char>
struct hash<unsigned char>
struct hash<signed char>
struct hash<short>
struct hash<unsigned short>
struct hash<int>
struct hash<unsigned int>
struct hash<long>
struct hash<unsigned long>

也就是说,如果你的key使用的是以上类型中的一种,你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量,你只能 如此,例如对于string,就必须自定义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);
}
};
//如果你希望利用系统定义的字符串hash函数,你可以这样写:
struct str_hash{
size_t operator()(const string& str) const
{
return __stl_hash_string(str.c_str());
}
};

在声明自己的哈希函数时要注意以下几点:

使用struct,然后重载operator(). 返回是size_t 参数是你要hash的key的类型。 函数是const类型的。 如果这些比较难记,最简单的方法就是照猫画虎,找一个函数改改就是了。

现在可以对开头的"岳不群"进行哈希化了 . 直接替换成下面的声明即可:

map<string, string> namemap;
//改为:
hash_map<string, string, str_hash> namemap;

其他用法都不用边。当然不要忘了吧str_hash的声明以及头文件改为hash_map。

你或许会问:比较函数呢?别着急,这里就开始介绍hash_map中的比较函数。

2.3 hash_map 的比较函数 在map中的比较函数,需要提供less函数。如果没有提供,缺省的也是less< Key> 。在hash_map中,要比较桶内的数据和key是否相等,因此需要的是是否等于的函数:equal_to< Key> 。先看看equal_to的源码: //本代码可以从SGI STL
//先看看binary_function 函数声明,其实只是定义一些类型而已。
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//看看equal_to的定义:
template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

如果你使用一个自定义的数据类型,如struct mystruct, 或者const char* 的字符串,如何使用比较函数?使用比较函数,有两种方法. 第一种是:重载==操作符,利用equal_to;看看下面的例子:

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;
}
};

有了compare_str,就可以使用hash_map了。

typedef hash_map<const char*, string, hash<const char*>, compare_str> StrIntMap;
StrIntMap namemap;
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";2.4 hash_map 函数 hash_map的函数和map的函数差不多。具体函数的参数和解释,请参看:STL 编程手册:Hash_map, 这里主要介绍几个常用函数。 hash_map(size_type n) 如果讲究效率,这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多,hash函数发生冲突的概率就越小,重新申请内存的概率就越小。n越大,效率越高,但是内存消耗也越大。 const_iterator find(const key_type& k) const. 用查找,输入为键值,返回为迭代器。 data_type& operator[](const key_type& k) . 这是我最常用的一个函数。因为其特别方便,可像使用数组一样使用。不过需要注意的是,当你使用[key ]操作符时,如果容器中没有key元素,这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时,你可以使用find。如果你 希望插入该元素时,你可以直接使用[]操作符。 insert 函数。在容器中不包含key值时,insert函数和[]操作符的功能差不多。但是当容器中元素越来越多,每个桶中的元素会增加,为了保证效 率,hash_map会自动申请更大的内存,以生成更多的桶。因此在insert以后,以前的iterator有可能是不可用的。 erase 函数。在insert的过程中,当每个桶的元素太多时,hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后,其他元素的iterator还是可用的。 3 相关hash容器 hash 容器除了hash_map之外,还有hash_set, hash_multimap, has_multiset, 这些容器使用起来和set, multimap, multiset的区别与hash_map和map的区别一样,我想不需要我一一细说了吧。 4 其他 这里列几个常见问题,应该对你理解和使用hash_map比较有帮助。 4.1 hash_map和map的区别在哪里? 构造函数。hash_map需要hash函数,等于函数;map只需要比较函数(小于函数). 存储结构。hash_map采用hash表存储,map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。 4.2 什么时候需要用hash_map,什么时候需要用map? 总体来说,hash_map 查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。

现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

这里还有个关于hash_map和map的小故事,看看:http://dev.csdn.net/Develop/article/14/14019.shtm

4.3 如何在hash_map中加入自己定义的类型? 你只要做两件事, 定义hash函数,定义等于比较函数。下面的代码是一个例子: -bash-2.05b$ cat my.cpp
#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;
}
-bash-2.05b$ make my
c++ -O -pipe -march=pentiumpro my.cpp -o my
-bash-2.05b$ ./my
I am 12
I am 1988774.4如何用hash_map替换程序中已有的map容器? 这个很容易,但需要你有良好的编程风格。建议你尽量使用typedef来定义你的类型: typedef map<Key, Value> KeyMap;

当你希望使用hash_map来替换的时候,只需要修改:

typedef hash_map<Key, Value> KeyMap;

其他的基本不变。当然,你需要注意是否有Key类型的hash函数和比较函数。

4.5为什么hash_map不是标准的? 具体为什么不是标准的,我也不清楚,有个解释说在STL加入标准C++之时,hash_map系列当时还没有完全实现,以后应该会成为标准。如果谁知道更 合理的解释,也希望告诉我。但我想表达的是,正是因为hash_map不是标准的,所以许多平台上安装了g++编译器,不一定有hash_map的实现。 我就遇到了这样的例子。因此在使用这些非标准库的时候,一定要事先测试。另外,如果考虑到平台移植,还是少用为佳。 4.6 有学习使用hash_map的建议吗? hash中文是哈希,也成为散列,听见别人说散列容器不要埋怨自己孤陋寡闻。了解hash系列,你还可以看看这篇文章:effective STL 25: 熟悉非标准散列容器, 另外建议查看源代码。如果还有问题,那么你可以在STL论坛上提问,会有高手回答你的。