📄 hash.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!-- This collection of hypertext pages is Copyright 1995-2005 by Steve Summit. --><!-- Content from the book "C Programming FAQs: Frequently Asked Questions" --><!-- (Addison-Wesley, 1995, ISBN 0-201-84519-9) is made available here by --><!-- permission of the author and the publisher as a service to the community. --><!-- It is intended to complement the use of the published text --><!-- and is protected by international copyright laws. --><!-- The on-line content may be accessed freely for personal use --><!-- but may not be published or retransmitted without explicit permission. --><!-- --><!-- this page built Sat Dec 24 21:47:47 2005 by faqproc version 2.7 --><!-- from source file algorithms.sgml dated Sat Feb 14 14:35:07 2004 --><!-- corresponding to FAQ list version 4.0 --><html><!-- Mirrored from c-faq.com/misc/hash.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 07:59:05 GMT --><head><meta name=GENERATOR content="faqproc"><title>Question 20.29</title><link href="soundex.html" rev=precedes><link href="gaussian.html" rel=precedes><link href="index.html" rev=subdocument></head><body bgcolor="#ffffff"><a href="soundex.html" rev=precedes><img src="../images/buttonleft.gif" alt="prev"></a><a href="index.html" rev=subdocument><img src="../images/buttonup.gif" alt="up"></a><a href="gaussian.html" rel=precedes><img src="../images/buttonright.gif" alt="next"></a> <a href="../index-2.html"><img src="../images/buttontop.gif" alt="top/contents"></a><a href="../search.html"><img src="../images/buttonsrch.gif" alt="search"></a><hr><p><!-- qbegin --><h1>comp.lang.c FAQ list<font color=blue>·</font><!-- qtag -->Question 20.29</h1><p><font face=Helvetica size=8 color=blue><b>Q:</b></font>What is hashing?</p><p><hr><p><font face=Helvetica size=8 color=blue><b>A:</b></font>Hashing is the process ofmappingstringsto integers,usually in a relatively small range.A ``hash function'' maps a string(orsomeother data structure)toa bounded number(the ``hash bucket'')whichcan more easilybeusedas an index in an array,or for performing repeated comparisons.(Obviously,a mapping from a potentially huge set of stringsto a small set of integerswill not be unique.Anyalgorithm using hashingtherefore has to deal with the possibility of ``collisions.'')</p><p>Many hashing functionsand related algorithmshave been developed;a full treatment is beyond the scope of this list.An extremely simplehash functionfor stringsis simply to add up the values of all the characters:<pre>unsigned hash(char *str){ unsigned int h = 0; while(*str != '\0') h += *str++; return h % NBUCKETS;}</pre>A somewhat better hash function is<pre>unsigned hash(char *str){ unsigned int h = 0; while(*str != '\0') h = (256 * h + *str++) % NBUCKETS; return h;}</pre>which actually treats the input string as a large binary number(<TT>8 * strlen(str)</TT> bits long,assuming characters are 8 bits)and computes that number modulo NBUCKETS,by Horner's rule.(Here it is important that NBUCKETS be prime,among other things.To remove the assumption that characters are 8 bits,use <TT>UCHAR_MAX+1</TT> instead of 256;the ``large binary number'' will then be<TT>CHAR_BIT * strlen(str)</TT> bits long.<TT>UCHAR_MAX</TT> and <TT>CHAR_BIT</TT> are defined in <TT><limits.h></TT>.)</p><p>Whenthe set of strings is known in advance,it is also possible to devise ``perfect''hashing functions whichguarantee a collisionless, dense mapping.</p><p>References:K&R2 Sec. 6.6<br>Knuth Sec. 6.4 pp. 506-549 Volume 3<br>Sedgewick Sec. 16 pp. 231-244<br></p><!-- aend --><p><hr><a href="soundex.html" rev=precedes><img src="../images/buttonleft.gif" alt="prev"></a><a href="index.html" rev=subdocument><img src="../images/buttonup.gif" alt="up"></a><a href="gaussian.html" rel=precedes><img src="../images/buttonright.gif" alt="next"></a> <a href="../questions.html"><img src="../images/buttontop.gif" alt="contents"></a><a href="../search.html"><img src="../images/buttonsrch.gif" alt="search"></a><br><!-- lastfooter --><a href="../about.html">about this FAQ list</a> <a href="../eskimo.html">about eskimo</a> <a href="../search.html">search</a> <a href="../feedback.html">feedback</a> <a href="copyright.html">copyright</a><p>Hosted by<a href="http://www.eskimo.com/"><img src="../../www.eskimo.com/img/link/eskitiny.gif" alt="Eskimo North"></a></body><!-- Mirrored from c-faq.com/misc/hash.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 07:59:05 GMT --></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -