📄 hashfunction.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Author" CONTENT="Zafir Anjum">
<TITLE>MFC Programmer's SourceBook : STL Programmer's Guide</TITLE>
<META name="description"
content="A freely available implementation
of the C++ Standard Template Library, including
hypertext documentation.">
<META name="keywords"
content="generic programming, STL, standard template library">
</HEAD>
<SCRIPT LANGUAGE="JavaScript"><!--
var adcategory = "cpp";
// -->
</SCRIPT>
<body background="../../fancyhome/back.gif" bgcolor="#FFFFFF" >
<SCRIPT LANGUAGE="JavaScript"><!--
var nfrm = location.href.indexOf("_nfrm_");
var validframes = (top.frames.length > 0 && top.frames['ad'] && top.frames['logo'] );
var random = Math.random();
if( !validframes && nfrm == -1 )
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
document.write('<nolayer><center>');
document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
+ random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
+ 'frameborder=0 scrolling=no bordercolor="#000000">');
document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
+ random + '">');
document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
+ random + '" height=60 width=468>' + '</a>');
document.write('</iframe>');
document.write('</center></nolayer>');
document.write('<layer src="http://ad.doubleclick.net/adl/' + dclkPage +
';ord=' + random + '"></layer>');
document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}
// top.location = "/show.cgi?" + adcategory + "=" + location.pathname;
// -->
</SCRIPT>
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=NupaIdFCY34AAHYpGVs">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaIdFCY34AAHYpGVs"></a>
</p>
</noscript>
<BR Clear>
<H1>Hash Function</H1>
<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "containers.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
<TD Align=right><Img src = "concept.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left><Img src = "functors.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
<TD Align=right></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Categories</b>: containers, functors</TD>
<TD Align=right VAlign=top><b>Component type</b>: concept</TD>
</TR>
</Table>
<h3>Description</h3>
A Hash Function is a <A href="UnaryFunction.html">Unary Function</A> that is used by
<A href="HashedAssociativeContainer.html">Hashed Associative Containers</A>: it maps its argument to a
result of type <tt>size_t</tt>. A Hash Function must be deterministic
and stateless. That is, the return value must depend only
on the argument, and equal arguments must yield equal results.
<P>
The performance of a <A href="HashedAssociativeContainer.html">Hashed Associative Container</A> depends
crucially on its hash function. It is important for a Hash Function
to minimize collisions, where a collision is defined as two different
arguments that hash to the same value. It is also important that the
distribution of hash values be uniform; that is, the probability that
a Hash Function returns any particular value of type <tt>size_t</tt> should
be roughly the same as the probability that it returns any other
value. <A href="#1">[1]</A>
<h3>Refinement of</h3>
<A href="UnaryFunction.html">Unary Function</A>
<h3>Associated types</h3>
<Table border>
<TR>
<TD VAlign=top>
Result type
</TD>
<TD VAlign=top>
The type returned when the Hash Function is called. The result
type must be <tt>size_t</tt>.
</TD>
</tr>
</table>
<h3>Notation</h3>
<h3>Definitions</h3>
<h3>Valid expressions</h3>
None, except for those described in the <A href="UnaryFunction.html">Unary Function</A>
requirements.
<h3>Expression semantics</h3>
<h3>Complexity guarantees</h3>
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign=top>
Deterministic function
</TD>
<TD VAlign=top>
The return value depends only on the argument, as opposed to
the past history of the Hash Function object. The return value
is always the same whenever the argument is the same.
</TD>
</tr>
</table>
<h3>Models</h3>
<UL>
<LI>
<tt><A href="hash.html">hash</A></tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that both of these requirements make sense only in the
context of some specific distribution of input values. To take a
simple example, suppose that the values being hashed are the six
strings "aardvark", "trombone", "history", "diamond", "forthright",
and "solitude". In this case, one reasonable (and efficient) hash
function would simply be the first character of each string. On the
other hand, suppose that the values being hashed are "aaa0001",
"aaa0010", "aaa0011", "aaa0100", "aaa0101", and "aaa0110". In that
case, a different hash function would be more appropriate. This is
why <A href="HashedAssociativeContainer.html">Hashed Associative Containers</A> are parameterized by the hash
function: no one hash function is best for all applications.
<h3>See also</h3>
<A href="HashedAssociativeContainer.html">Hashed Associative Container</A>, <tt><A href="hash.html" tppabs="http://www.sgi.com/Technology/STL/hash.shtml">hash</A></tt>
<HR SIZE="6"> <FONT SIZE="-2"> Copyright © 1996 Silicon Graphics, Inc.
<HR>
<TABLE BORDER=0 WIDTH="100%" >
<TR>
<TD WIDTH="33%"><FONT SIZE=-1><A HREF="index.html" >
STL</A></FONT></TD>
<TD WIDTH="33%">
<CENTER><FONT SIZE=-2>© Copyright 1997-1998 CodeGuru</FONT> </CENTER>
</TD>
<TD WIDTH="34%">
<DIV ALIGN=right><FONT SIZE=-1>Contact : <A HREF="mailto:webmaster@codeguru.com">webmaster@codeguru.com</A> </FONT></DIV>
</TD>
</TR>
</TABLE>
<SCRIPT LANGUAGE="JavaScript" ><!--
var adurl = "/cgi-bin/doubleclick.cgi?";
if( self.adcategory )
adurl += adcategory;
else
adurl += "mfc";
if( self.parent.norefreshad )
parent.norefreshad = false;
else if( validframes )
parent.frames['ad'].location = adurl;
if( !validframes && nfrm == -1)
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
// var random = Math.random();
document.write('<nolayer><center>');
document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
+ random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
+ 'frameborder=0 scrolling=no bordercolor="#000000">');
document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
+ random + '">');
document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
+ random + '" height=60 width=468>' + '</a>');
document.write('</iframe>');
document.write('</center></nolayer>');
document.write('<layer src="http://ad.doubleclick.net/adl/' + dclkPage +
';ord=' + random + '"></layer>');
document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}
// -->
</SCRIPT>
<!-- SCRIPT LANGUAGE="JavaScript" SRC="/global/fscript.js">
//
</SCRIPT -->
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=NupaIdFCY34AAHYpGVs">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaIdFCY34AAHYpGVs"></a>
</p>
</noscript>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -