String hashing

This is a discussion on String hashing within the C Programming forums, part of the General Programming Boards category; You could use an additive hash function, as Salem suggested....

  1. #16
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    You could use an additive hash function, as Salem suggested.

  2. #17
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Here's something else to try, given strings "abcde" and "deabc".

    Locate the position of the first element "a" in the 2nd string.
    Now walk along both strings in parallel, comparing each character.
    When 2nd string ends, "switchback" to its beginning and continue comparing chars.
    Terminate the program when the 1st string ends ie "match found" or a mismatch occurs.

  3. #18
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    what if you have more than one "a" in the string?

    "ababa"
    "babaa"

  4. #19
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The problem is that you want a crappy hash. You want collisions. Designing to purposefully have collisions is generally bad.

    I can see a way to do it, but your hash is going to be LEN^2+1 in size, and you aren't going to be able use == to compare hashes. Here's what you do:
    Code:
    char *hash( char *s )
    {
        if( s )
        {
            char *h = NULL;
            size_t len = strlen( s );
    
            if( (h = malloc( len * len + 1 )) )
            {
                size_t x;
                char **list = malloc( len * sizeof *list );
    
                for( x = 0; x < len; x++ )
                {
                    list[ x ] = shift( s, x );
                }
    
                sort( list )
    
                for( x = 0; x < len; x++ )
                {
                    strcat( h, list[ x ] );
                }
            }
            return h;
        }
        return NULL;
    }
    Now, write yourself a shift function, and a sort function, and you're done. (Edit: You might want to free list when you're done with it.)


    Quzah.
    Last edited by quzah; 09-11-2009 at 07:31 PM.
    Hope is the first step on the road to disappointment.

  5. #20
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Hmmm! in that case methinks the code needs to step thro' all occurences of "a" until either a mismatch or the 1st strings ends.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. char Handling, probably typical newbie stuff
    By Neolyth in forum C Programming
    Replies: 16
    Last Post: 06-21-2009, 04:05 AM
  2. Replies: 4
    Last Post: 03-03-2006, 01:11 AM
  3. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 02:23 PM
  4. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 01:45 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21