problem in creating a hash table

[bemi]

Hello all,

I'm creating a hash table ( an array of size 10 ). The array contains 10 firstnames from input. I then calculate an index for each firstname. Each index will determine firstname in the hash array. And before I locate a firstname into my hashtable, the firstname needs to check if there is a same firstname existed in the hasharray. If there is, the index is recalculated, incrementing by 1 and modulus to the size of hash table.

My problem are:

1. The value of hash index derived from hashfunction is somehow incorrect and I don't know why.

Here is an correct index correspond to its input names.

[0] Mickey
[1] Goofy
[2]
[3] Grumpy
[4]
[5] Balto
[6] Duckey
[7]
[8] Minnie
[9]

My program comes out as Goofy in index [6]; Grumpy in index [4] ...

2. the index after recalculated does not appear correctly on the ouput screen. Its value is unchanged.

Below is my program. Any help regard to my problems would be greatly appreciated.


// test string: Mickey Goofy Grumpy Balto Duckey Minnie
#include <iostream>
#include <cstring>
using namespace std;
int hashfunction(char *, int , const );
void manipulateString( char *, int) ;
void hashTable (int index, char * );
int main()
{
const inputHTsize = 10;
const size = 100;
char inputString[size];

cout << " Enter first names ( separate by a space ) \n " ;
cin.getline(inputString,size);

manipulateString(inputString, inputHTsize);

return 0;
}

void manipulateString (char *input, const htsize)
{

int firstNamelen;
int hIndex;
int totalName = 0;

char *firstname;
firstname = strtok(input, " "); // separate firstname

while (firstname != NULL)
{

firstNamelen = strlen(firstname);
//cout << "\nfirst name length is " << firstNamelen << endl;
hIndex = hashfunction(firstname,firstNamelen,htsize);


hashTable(hIndex, firstname);
cout << "\n\n ( " << firstname << " ) is stored at index [" << hIndex
<< "] of hash table " << endl;

firstname = strtok(NULL, " " ); // next first name

}
}

void hashTable(int index, char *name)
{
const s = 10; // size of hashtable

char *hashArray[s]; // same as hashArray[][]

bool found = false;

for ( int h = 0; h < s; h++)
{ // search for duplicate
if (name == hashArray[h])
found = true;
if (found) // duplicate found
index = ( index + 1 ) % s;

hashArray[index] = name;

}

}


int hashfunction (char *key, int keylength, int HTsize)
{
int sum = 0;

for (int i = 0; i <= keylength; i++)
sum += static_cast<int>(key[i]);

//cout <<" Sum of first name is " << sum;

return (sum % HTsize);
}

[highpriest]

this
for (int i = 0; i <= keylength; i++)
sum += static_cast<int>(key[i]);

expoits your integer range!

use this:

sum += ( static_cast<int>(key[i]) % HTsize);


It is better to use a prime number for HTsize.