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
– Nick Bedford, Commented Oct 1, 2009 at 6: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
– user172818, Commented Oct 1, 2009 at 19:38

Community · Accepted Answer · 2017-05-23 10:27:42Z

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, 2017 at 10:27

CommunityBot

11 silver badge

answered Oct 1, 2009 at 6:33

Nick Dandoulakis

43.3k17 gold badges106 silver badges139 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nick Bedford · Accepted Answer · 2009-10-01 06:19:24Z

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 1, 2009 at 6:19

Nick Bedford

4,44534 silver badges36 bronze badges

4 Comments

user40120 Over a year ago

I was told that using strlen(str) in a loop is bad programming practi b/c of enumerants..

mmcdole Over a year ago

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

progician Over a year ago

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.

Nick Bedford Over a year ago

@progician Yeah I was merely addressing the manual length calculation. I've suggested what you stated above in another answer anyway.

Nick Bedford · Accepted Answer · 2009-10-01 07:45:46Z

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.

Collectives™ on Stack Overflow

Getting appropriate hash index C++

3 Answers 3

Comments

4 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

Comments

Linked

Related