page206.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 69 行
HTML
69 行
<HTML>
<HEAD>
<TITLE>Keys and Hash Functions</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4458" HREF="page207.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page207.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4456" HREF="page204.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page204.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4452" HREF="page205.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page205.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4460" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4461" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION009110000000000000000">Keys and Hash Functions</A></H2>
<P>
We are designing a container which will be used
to hold some number of items of a given set <I>K</I>.
In this context,
we call the elements of the set <I>K</I> <em>keys</em><A NAME=11186> </A>.
The general approach is to store the keys in an array.
The position of a key in the array is given by a function <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59195" SRC="img264.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img264.gif" >,
called a <em>hash function</em><A NAME=11188> </A>,
which determines the position of a given key directly from that key.
<P>
In the general case,
we expect the size of the set of keys, |<I>K</I>|,
to be relatively large or even unbounded.
E.g., if the keys are 32-bit integers, then <IMG WIDTH=64 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline62174" SRC="img869.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img869.gif" >.
Similarly, if the keys are arbitrary character strings
of arbitrary length, then |<I>K</I>| is unbounded.
<P>
On the other hand, we also expect that the actual number of items
stored in the container to be significantly less than |<I>K</I>|.
I.e., if <I>n</I> is the number of items actually
stored in the container, then <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62182" SRC="img870.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img870.gif" >.
Therefore, it seems prudent to use an array of size <I>M</I>,
where <I>M</I> is as least as great as the maximum number of items to be stored
in the container.
<P>
Consequently, what we need is a function <IMG WIDTH=181 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62188" SRC="img871.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img871.gif" >.
This function maps the set of values to be stored in the container
to subscripts in an array of length <I>M</I>.
This function is called a <em>hash function</em><A NAME=11191> </A>.
<P>
In general, since <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62192" SRC="img872.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img872.gif" >,
the mapping defined by hash function will be a
<em>many-to-one mapping</em><A NAME=11193> </A>.
I.e., there will exist many pairs of distinct keys <I>x</I> and <I>y</I>,
such that <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline62198" SRC="img873.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img873.gif" >,
for which <I>h</I>(<I>x</I>)=<I>h</I>(<I>y</I>).
This situation is called a <em>collision</em>.
Several approaches for dealing with collisions are explored
in the following sections.
<P>
What are the characteristics of a good hash function?
<UL><LI>
A good hash function avoids collisions.<LI>
A good hash function tends to spread keys evenly in the array.<LI>
A good hash function is easy to compute.
</UL><BR> <HR>
<UL>
<LI> <A NAME="tex2html4462" HREF="page207.html#SECTION009111000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page207.html#SECTION009111000000000000000">Avoiding Collisions</A>
<LI> <A NAME="tex2html4463" HREF="page208.html#SECTION009112000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page208.html#SECTION009112000000000000000">Spreading Keys Evenly</A>
<LI> <A NAME="tex2html4464" HREF="page209.html#SECTION009113000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page209.html#SECTION009113000000000000000">Ease of Computation</A>
</UL>
<HR><A NAME="tex2html4458" HREF="page207.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page207.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4456" HREF="page204.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page204.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4452" HREF="page205.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page205.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4460" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4461" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?