1

I am trying to write a function to hash strings into integers so I can use strings as keys in my hash map. I'm required to use the pseudocode written below, but I still can't get it to work without errors. The program is to enter a German word (as key) and return it's English translation (as value).

The pseudocode:

Parameters : natural numbers i, h = 0; Field s
 for i = 0 to i <length_of (s)
    h = (h * 128 + s [i]) mod M;
Result : h.

My code:

#include "pch.h"
#include <iostream>
#include <string>
#define M 661
using namespace std;

struct entry {
    string key_de, val_en;
};

int HASH(int i, int h = 0, struct entry ex_array[])
{
    for (i = 0; i < sizeof(ex_array) / sizeof(ex_array[0]); i++)
    {
        h = (h * 128) + ex_array[i] % m;
    }
    return h;
}

int main()
{

}
Omar Baz
  • 15
  • 1
  • 4
  • 1
    What errors are you getting? – Biesi Dec 11 '19 at 17:51
  • In the "int HASH" I'm getting default argument not at end of parameter list. – Omar Baz Dec 11 '19 at 17:52
  • Please post a [mcve] of your attempt. – Jesper Juhl Dec 11 '19 at 17:52
  • 4
    @OmarBaz Seems like the error you're getting is pretty descriptive of what is wrong. – Rosme Dec 11 '19 at 17:53
  • 1
    `h` must be the last parameter. Also, `sizeof(ex_array)` is not going to work well. – ChrisMM Dec 11 '19 at 17:58
  • `struct entry ex_array[]` in `c++` you don't need the `struct`. This is one difference between `c` and `c++` – drescherjm Dec 11 '19 at 18:00
  • Thank you, that solved the HASH problem but now I'm getting an error with the mod operator: no operator "%" matches these operands. Operand types are entry % int. – Omar Baz Dec 11 '19 at 18:01
  • Pass the size of the array as a parameter. You can't do `sizeof(ex_array) / sizeof(ex_array[0])` – drescherjm Dec 11 '19 at 18:02
  • 1
    It does not make sense to use the `%` operator with a struct. – drescherjm Dec 11 '19 at 18:03
  • Perhaps the `m` in `h = (h * 128) + ex_array[i] % m;` is really the `M` from `#define M 661`? Otherwise the former is undefined and the later is unused. – Paul Evans Dec 11 '19 at 18:11
  • The reason `sizeof(ex_array) / sizeof(ex_array[0])` does not work: `ex_array` [decayed to a pointer](https://stackoverflow.com/questions/1461432/what-is-array-decaying), so `sizeof(ex_array)` will always be the size of a pointer, not the size of the array used as the argument. – user4581301 Dec 11 '19 at 18:25
  • 1
    Since it's tagged C++, here is the obligatory recommendation to use vectors: Use [std::vector](https://en.cppreference.com/w/cpp/container/vector) instead of C-style arrays to make your life easier. – Lukas-T Dec 11 '19 at 18:41
  • 1
    or `std::array` if the array size is fixed at compile time. – user4581301 Dec 11 '19 at 18:41

1 Answers1

0

This would be a way you could implement that

#include <string>
#define M 661

int Hash(std::string s, int h = 0){
   for(int i = 0 ; i < s.length(); i++)
      h = (h * 128 + s [i]) % M;
   return h;
}

I have one note though. In the pseudo code you provided i'm not so sure that the "parameters" provided are talking about actual function parameters because it seems a little strange to pass in 'i' since you immediately set it to to 0 (for i = 0 ...). But if you do need to pass 'i' in then you can just add it to the beginning of the argument list and remove the 'int' from inside the for loop.

Then you can use this function to get the hash value of the German word.

Here's an example of how to use it

string arr[M]; //assuming M is size of array
std::string germanWord{"german"}; //some German word
std::string englishWord{"english"} //same word but in English
arr[Hash(germanWord)] = englishWord //adding new English word to the array
string s = arr[Hash(germanWord)] // accessing that word from the array

there are other things you might have to think about if you are going to make an actual hash map (Like how you deal with collisions) but this is enough if you just want to implement that pseudo code.

Good luck!

Tanner Lyman
  • 36
  • 2