📄 page208.html
字号:
<HTML><HEAD><TITLE>Keys and Hash Functions</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html3598" HREF="page209.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3596" HREF="page206.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3592" HREF="page207.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3600" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008110000000000000000">Keys and Hash Functions</A></H2><P>We are designing a container which will be usedto 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=10591> </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_inline58645" SRC="img261.gif" >,called a <em>hash function</em><A NAME=10593> </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.For example, if the keys are 32-bit integers, then <IMG WIDTH=64 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61547" SRC="img824.gif" >.Similarly, if the keys are arbitrary character stringsof arbitrary length, then |<I>K</I>| is unbounded.<P>On the other hand, we also expect that the actual number of itemsstored in the container to be significantly less than |<I>K</I>|.That is, if <I>n</I> is the number of items actuallystored in the container, then <IMG WIDTH=57 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61555" SRC="img825.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 storedin the container.<P>Consequently, what we need is a function <IMG WIDTH=179 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61561" SRC="img826.gif" >.This function maps the set of values to be stored in the containerto subscripts in an array of length <I>M</I>. This function is called a <em>hash function</em><A NAME=10596> </A>.<P>In general, since <IMG WIDTH=61 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61565" SRC="img827.gif" >,the mapping defined by hash function will be a<em>many-to-one mapping</em><A NAME=10598> </A>.That is, 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_inline61571" SRC="img828.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 exploredin 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="tex2html3601" HREF="page209.html#SECTION008111000000000000000">Avoiding Collisions</A><LI> <A NAME="tex2html3602" HREF="page210.html#SECTION008112000000000000000">Spreading Keys Evenly</A><LI> <A NAME="tex2html3603" HREF="page211.html#SECTION008113000000000000000">Ease of Computation</A></UL><HR><A NAME="tex2html3598" HREF="page209.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3596" HREF="page206.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3592" HREF="page207.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3600" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -