Download the HashCode.cpp file and implement the details of the functions called

Question

Download the HashCode.cpp file and implement the details of the functions called calculateHash() and insertTable(). The calculateHash() function takes a given string and adds the ASCII value for each character in the string to produce a hash code based on the size of the hash table. The hash code can be generated by taking the value of the sum of the characters modulo the size of the hash table (which will be 512 in our program). The insertTable() takes the given hash code and the key (or string) and inserts it into the hash table. This function should print an error message if there is a collision in the hash table. You do not have to resolve collisions.

Output: The error message may be different, but the remaining output for the program after the function is implemented should appear as follows:

Dax hashCode=285

O'Brien hashCode=102

Quark hashCode=4

Dr. Bashier hashCode=450

Kira hashCode=391

B'Elanna hashCode=184

Picard hashCode=83

Riker hashCode=509

Data hashCode=378

La Forge hashCode=192

Worf hashCode=414

Dr. Crusher hashCode=480

Dr. Pulaski hashCode=477

Wesley hashCode=121

Troi hashCode=414

Error: Troi collides at hashCode=414 not inserting

Tasha hashCode=497

Sisko hashCode=9

Odo hashCode=290

Bones hashCode=503

Scotty hashCode=134

Chekov hashCode=96

Uhura hashCode=5

Sulu hashCode=425

Nurse Chapel hashCode=122

Reed hashCode=384

Travis hashCode=121

Error: Travis collides at hashCode=121 not inserting

Hoshi hashCode=507

Dr. Phlox hashCode=271

Kirk hashCode=401

Spock hashCode=0

Hash Table: Index Key

0 Spock

4 Quark

5 Uhura

9 Sisko

83 Picard

96 Chekov

102 O'Brien

121 Wesley

122 Nurse Chapel

134 Scotty

184 B'Elanna

192 La Forge

271 Dr. Phlox

285 Dax

290 Odo

378 Data

384 Reed

391 Kira

401 Kirk

414 Worf

425 Sulu

450 Dr. Bashier

477 Dr. Pulaski

480 Dr. Crusher

497 Tasha

503 Bones

507 Hoshi

509 Riker
** Press any key to continue **

Hint: As with the other programming assignments, you only need to provide the details for the areas of the code that are marked with TODO comments. All of the other areas of code, including the data strings, and function signatures will not change. For the calculateHash() function, create a for-loop similar to the one in the displayHashTable() function, except this your function will add the value of each character in the string based on the length of the string. For example, declare an integer variable (sum) and add the ASCII value of each character to the integer:
      sum = sum + static_cast<int>(key[index])

After the loop return the modulus of the sum variable with the size of the hash table. Set the size of the hash table variable size at the top of the file to 512.
For the insertTable() function, use an if-statement to check whether or not the location in the hash table is occupied. You can use the length() or size() string function to test whether or not the string is equal to 0. This will be similar to the check that is performed in the displayHashTable() function, except you will use the hashCode variable instead of the variable i. Print an error message if the position in the hash table is occupied and do not insert the string into the hash table.

The code is below and the only part that needs editing is the part that specifies so:

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>

using namespace std;

int calculateHash(string key);
void insertTable(int hashCode, string item);
void displayHashTable();

const int TableSize = 0; // TODO: change 0 to be the size of the
// hash table here this should be set to
// value indicated in the handout.
string hashTable[TableSize];

int main(int argc, char **argv)
{
string starTrekCharacters[] = {
  "Dax", "O'Brien", "Quark", "Dr. Bashier", "Kira", "B'Elanna",
  "Picard", "Riker", "Data", "La Forge", "Worf", "Dr. Crusher",
  "Dr. Pulaski", "Wesley", "Troi", "Tasha", "Sisko", "Odo",
  "Bones", "Scotty", "Chekov", "Uhura", "Sulu", "Nurse Chapel",
  "Reed", "Travis", "Hoshi", "Dr. Phlox", "Kirk", "Spock",
};

const int numberOfCharacters = 30;
int hash = 0;

for (int i = 0; i < numberOfCharacters; i++)
{
  hash = calculateHash(starTrekCharacters[i]);
  cout << starTrekCharacters[i] << " hashCode=" << hash << endl;
  insertTable(hash, starTrekCharacters[i]);
}

displayHashTable();

cout << " ** Press any key to continue ** ";
getchar();

system("pause");
return 0;
}

int calculateHash(string key)
{
// TODO: Use a loop to add together the ASCII value of
// each character in the given string s.
//
// HINT: You can get the length of the string by calling the
// function key.size() or key.length().

return 0;
}

void insertTable(int hashCode, string item)
{
// TODO: Implement the details of the this function
// This function should insert item in the hashTable
// at the hashCode position. Print an error message
// if the position is occupied and do not insert
// the string into the hash table.
//
// HINT: the hashTable variable is an array. The
// position in the hashTable is occupied if the size()
// or length() of the position is greater than 0.

return;
}

void displayHashTable()
{
cout << " Hash Table:" << endl;
cout << "Index Key" << endl;

for (int i = 0; i < TableSize; i++)
{
  if (hashTable[i].length() > 0)
  {
   cout << i << " " << hashTable[i] << endl;
  }
}

return;
}

Explanation / Answer

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>

using namespace std;

int calculateHash(string key);
void insertTable(int hashCode, string item);
void displayHashTable();

const int TableSize = 512; // TODO: change 0 to be the size of the
// hash table here this should be set to
// value indicated in the handout.
string hashTable[TableSize];

int main(int argc, char **argv)
{
string starTrekCharacters[] = {
"Dax", "O'Brien", "Quark", "Dr. Bashier", "Kira", "B'Elanna",
"Picard", "Riker", "Data", "La Forge", "Worf", "Dr. Crusher",
"Dr. Pulaski", "Wesley", "Troi", "Tasha", "Sisko", "Odo",
"Bones", "Scotty", "Chekov", "Uhura", "Sulu", "Nurse Chapel",
"Reed", "Travis", "Hoshi", "Dr. Phlox", "Kirk", "Spock",
};

const int numberOfCharacters = 30;
int hash = 0;

for (int i = 0; i < numberOfCharacters; i++)
{
hash = calculateHash(starTrekCharacters[i]);
cout << starTrekCharacters[i] << " hashCode=" << hash << endl;
insertTable(hash, starTrekCharacters[i]);
}

displayHashTable();

cout << " ** Press any key to continue ** ";
getchar();

return 0;
}

int calculateHash(string key)
{
int sum =0;
for(int i=0;i<key.length();i++){
    sum = sum + (int)key[i];
}

return sum%512;
}

void insertTable(int hashCode, string item)
{
if(hashTable[hashCode] == ""){
   hashTable[hashCode] = item;
}else{
   cout << "Error: "<<item<<" collides at hashCode="<<hashCode<<" not inserting ";
}

return;
}

void displayHashTable()
{
cout << " Hash Table:" << endl;
cout << "Index Key" << endl;

for (int i = 0; i < TableSize; i++)
{
if (hashTable[i].length() > 0)
{
   cout << i << " " << hashTable[i] << endl;
}
}

return;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.