1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
<HTML>
<!--
-- Copyright (c) 1996,1997
-- 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="Silicon Graphics, Inc." 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 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">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 ©
1996 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>
|
