Getting appropriate hash index C++

Question

I've tried everything. Even java's forumla:

java.lang.String.hashCode():

s[0]*(31^(n-1)) + s[1]*(31^(n-2)) + ... + s[n-1]

I've interpretted this as a sum: Although I am not quite sure what to do with the s[n-1];

int hashmap::hashstr( const char*const str )
{
    int result = 0;
    int i = 0;
    int j = 0;
    int k = 0;
    unsigned n = 0;
    for ( ; str[n] != NULL; ++n ); // how many characters?

    while ( j != n ) // no more characters
    {
        result += str[i] * ( 31 ^ ( n - k ) );
        j++;
        i++;
        k++;
    }
    return result % maxSize;
}

where maxSize is the 10th element in my fixed array size of 11.

What am i doing wrong? SOME of my hash indicies are coming out wrong. Others, correctly. Why is this? So far everyones been like, "Who cares how it works!! Use a template!" Well, I want to understand this..

I think you need to learn a little more basic things like using strlen() before trying hashmaps. — Nick Bedford, Oct 01 '09 at 06:20
Can you explain when you say an index is "wrong" or "correct"? Any hash function works, but some are inefficient. There is no "wrong" or "right". Are you comparing your implementation with Java? — user172818, Oct 01 '09 at 19:38

score 7 · Answer 1 · edited May 23 '17 at 10:27

7

s[0](31^(n-1)) + s[1](31^(n-2)) + ... + s[n-1]

In the formula ^ indicates exponentiation, not the bitwise xor operation.
Check out this SO question.

edited May 23 '17 at 10:27

Community

1
1

answered Oct 01 '09 at 06:33

Nick Dandoulakis

42,588
16
104
136

score 3 · Answer 2 · answered Oct 01 '09 at 06:19

3

unsigned n = 0;
for ( ; str[n] != NULL; ++n ); // how many characters?

You know you could just use strlen(str), right?

And the line:

return result % maxSize;

Where's this result from? I don't see any result variable.

answered Oct 01 '09 at 06:19

Nick Bedford

4,365
30
36

I was told that using strlen(str) in a loop is bad programming practi b/c of enumerants.. – user40120 Oct 01 '09 at 06:41
1

@lampshade, What are you talking about? You don't put strlen() in a loop. You find the size of the string intially, it has nothing to do with your loop. – mmcdole Oct 01 '09 at 06:46
2

It is a bad practice using strlen() where you actually walk through the string anyway, because the strlen() function itself walks through the string once in the first place. Maybe it's not that significant in this case, but in any code where you actually go through the string anyway, generally better practice just to test the current character with '\0' to find out are you at the end. This is kinda a thumb-rule of string processing with ASCIIZ. – progician Oct 01 '09 at 09:31
@progician Yeah I was merely addressing the manual length calculation. I've suggested what you stated above in another answer anyway. – Nick Bedford Oct 01 '09 at 10:45

score 0 · Answer 3 · answered Oct 01 '09 at 07:45

Just going from this code, you could do the following:

void function (const char *str)
{
    while (*str)
    {
        /* process whatever with *str which is the same as str[i] in a for loop */
        str++;
    }
}

Also, you don't need the second const on those const char *const parameters. const char * is fine.

Getting appropriate hash index C++

3 Answers3