Solved

# Good Hashing code for a string

Posted on 2006-04-23
297 Views
I need a basic hashing code for a string of the form '9X9XX99X9XX999999' where 9 represents any digit and X represents any letter (capitals A-Z only).

Should be a quick 75 points for someone...
0
Question by:bombboyer

LVL 53

Expert Comment

What do you mean by a basic hashing code ?

How big do you want your hash table to be ?

You could just add up all the characters (their ASCII values) ...
0

Author Comment

I'd like the hashing table to be as small as possible (ie. not a sparse array). I don't need "exact fit" small, but decently "tight"...
0

LVL 53

Expert Comment

What is the data that is gonna be put in the hash table ? What are its properties ? Anything special, or 100% probabilistic ?

Does the data need to be persistent in the hash table, or can it be erased on collision (like a cache) ?

How many entries do you foresee into the hash table ? Any clustering you think could happen ?
0

LVL 17

Accepted Solution

Java uses the following computation for hashing strings: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html#hashCode()

You might want to restrict it to a limited number of characters if its uniqueueness is liable to be at the beginning of the string.
0

LVL 22

Assisted Solution

One good hash scheme, used by Borland's compilers:

BigPrime := 1009;
Tot := 0;

for i := 1 to Length( Token )      Tot += Tot * 13 + Token[i];

Tot %=  BigPrime;

0

LVL 39

Assisted Solution

If the strings contain '9' and 'X' only you might calculate the hash by setting bit i to 1 if the key[i] == '9' or bit i to 0 if key[i] == 'X' (or vice versa).

enum {  MAX_HASH = 1023 };
unsigned int hash = 0;
for (int i = 0; i < strlen(key); ++i)
if (key[i] == '9')
hash  |= 1<<(i % 32);
hash = (hash * 13) / 7;
hash %= MAX_HASH;

The for loop calculates a unique number for any key that has a length of less than 33. By multiplying it with 13/7 we eliminate bad hashing if for example most keys would end with '9'.

Regards, Alex
0

## Featured Post

Some Windows API functions expect you to provide a pointer to a CALLBACK function that the system will need to call as part of the operation.  Such API functions as SetTimer, timeSetEvent, CreateThread, EnumWindows, LineDDA, even window message hand…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…