Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Good Hashing code for a string

Posted on 2006-04-23
8
Medium Priority
?
336 Views
Last Modified: 2010-08-05
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
Comment
Question by:bombboyer
6 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 16522731
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

by:bombboyer
ID: 16522739
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

by:Infinity08
ID: 16522823
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 17

Accepted Solution

by:
rstaveley earned 100 total points
ID: 16523492
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

by:grg99
grg99 earned 100 total points
ID: 16523640
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

by:itsmeandnobodyelse
itsmeandnobodyelse earned 100 total points
ID: 16524720
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

[Webinar] Database Backup and Recovery

Does your company store data on premises, off site, in the cloud, or a combination of these? If you answered “yes”, you need a data backup recovery plan that fits each and every platform. Watch now as as Percona teaches us how to build agile data backup recovery plan.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

571 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question