?? hashfunction.html
字號:
<HTML><!-- -- Copyright (c) 1996-1999 -- Silicon Graphics Computer Systems, Inc. -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Silicon Graphics makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- -- Copyright (c) 1994 -- Hewlett-Packard Company -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Hewlett-Packard Company makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- --><Head><Title>Hash Function</Title><!-- Generated by htmldoc --></HEAD><BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="CorpID.gif" ALT="SGI" HEIGHT="43" WIDTH="151"> <!--end header--><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 aresult of type <tt>size_t</tt>. A Hash Function must be deterministicand 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> dependscrucially on its hash function. It is important for a Hash Functionto minimize collisions, where a collision is defined as two differentarguments that hash to the same value. It is also important that thedistribution of hash values be uniform; that is, the probability thata Hash Function returns any particular value of type <tt>size_t</tt> shouldbe roughly the same as the probability that it returns any othervalue. <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 thecontext of some specific distribution of input values. To take asimple example, suppose that the values being hashed are the sixstrings "aardvark", "trombone", "history", "diamond", "forthright",and "solitude". In this case, one reasonable (and efficient) hashfunction would simply be the first character of each string. On theother hand, suppose that the values being hashed are "aaa0001","aaa0010", "aaa0011", "aaa0100", "aaa0101", and "aaa0110". In thatcase, a different hash function would be more appropriate. This iswhy <A href="HashedAssociativeContainer.html">Hashed Associative Containers</A> are parameterized by the hashfunction: 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">hash</A></tt><!--start footer--> <HR SIZE="6"><A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" ALT="[Silicon Surf]"></A><A HREF="index.html"><IMG SRC="stl_home.gif" HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A><BR><FONT SIZE="-2"><A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright © 1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT><FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A></FONT><P></BODY></HTML> ?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -