Categories:
.NET (357)
C (330)
C++ (183)
CSS (84)
DBA (2)
General (7)
HTML (4)
Java (574)
JavaScript (106)
JSP (66)
Oracle (114)
Perl (46)
Perl (1)
PHP (1)
PL/SQL (1)
RSS (51)
Software QA (13)
SQL Server (1)
Windows (1)
XHTML (173)
Other Resources:
What is hashing?
What is hashing?
✍: Guest
Hashing is the process of mapping strings to integers, usually in a relatively small range. A ``hash function'' maps a string (or some other data structure) to a bounded number (the ``hash bucket'') which can more easily be used as an index in an array, or for performing repeated comparisons. (Obviously, a mapping from a potentially huge set of strings to a small set of integers will not be unique. Any algorithm using hashing therefore has to deal with the possibility of ``collisions.'')
Many hashing functions and related algorithms have been developed; a full treatment is beyond the scope of this list. An extremely simple hash function for strings is simply to add up the values of all the characters:
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != '\0')
h += *str++;
return h % NBUCKETS;
}
A somewhat better hash function is
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != '\0')
h = (256 * h + *str++) % NBUCKETS;
return h;
}
which actually treats the input string as a large binary number (8 * strlen(str) 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 UCHAR_MAX+1 instead of 256; the ``large binary number'' will then be CHAR_BIT * strlen(str) bits long. UCHAR_MAX and CHAR_BIT are defined in<limits.h>.)
When the set of strings is known in advance, it is also possible to devise ``perfect'' hashing functions which guarantee a collisionless, dense mapping.
2015-01-07, 1239👍, 0💬
Popular Posts:
How to create arrays in JavaScript? We can declare an array like this var scripts = new Array(); We ...
Do You Know the Book "JUnit in Action"? You should know this book. It received some good reviews. Ti...
Why is there extra white space before or after tables? This is often caused by invalid HTML syntax. ...
How To Divide Query Output into Groups? - MySQL FAQs - SQL SELECT Query Statements with GROUP BY You...
How To Merge Values of Two Arrays into a Single Array? - PHP Script Tips - PHP Built-in Functions fo...