Good Hashing code for a string

Posted on 2006-04-23
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...
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) ...

    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"...
    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 ?
    LVL 17

    Accepted Solution

    Java uses the following computation for hashing strings:

    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.
    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;

    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Better Security Awareness With Threat Intelligence

    See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

    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…

    779 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

    Need Help in Real-Time?

    Connect with top rated Experts

    14 Experts available now in Live!

    Get 1:1 Help Now