Hash function in C, need to port it to C++

1. You use C++ strings but did not #include <string>.
2. As pointed out earlier, you should pass key.c_str() to hash().
3. h is uninitialised in hash().

I think that if you are going to alter your original code anyway, then it makes sense to just change it to use C++ strings, e.g.,

Code:

---

unsigned int hash(const std::string& key)
{
        unsigned int h = 0;
        const unsigned char* p = reinterpret_cast<const unsigned char*>(key.c_str());

        int len = key.length();
        for(int i=0; i<len; i++)
        {
                h = 33 * h + p[i];
        }
        return h;
}

---

This way, you can just call hash(key) in your main function.

Just curious: is one better than the other as far as using the address of the first element or using the c_str() function? My answer would be that using c_str() is easier to read.

Code:

---

#include <iostream>
#include <string>

using namespace std;

unsigned hash( const void* key, int len );

int main()
{
        string text;

        cout << "String: ";
        cin >> text;
       
        cout << "Hashed: " << hash( text.c_str(), text.length() );

        cin.ignore();

        return 0;
}

unsigned hash( const void* key, int len)
{
        const unsigned char* p = (const unsigned char*)key;

        unsigned h=0;

        int i;

        for(i=0; i<len; i++)
        {
                h=33*h+p[i];
        }

        return h;
}

---

Those are minimal changes to your code, take a close look and find out what has changed and why. Changes are in the function declaration, it now takes a const pointer, because aside from the compiler error, it's the correct way of doing stuff.

>> Just curious: is one better than the other as far as using the address of the first element or using the c_str() function? My answer would be that using c_str() is easier to read.

Yes, c_str() is better. Passing an address to the first element is not guaranteed to provide a valid C style string. It is legal and possible (although somewhat unlikely) that parts of the string are stored in separate places rather than a contiguous array of characters. Only vector is guaranteed to have contiguous storage, so taking the address of the first element is valid only for vector.

The other, more practical issue is that the C++ string's internal data might not be null terminated. There are implementations that do not null terminate the string internally all the time. In those cases you will get garbage after the string until the first null is encountered in memory that doesn't belong to you.

So c_str() is easier to read, and taking the address of the first element of the string is not guaranteed to work.

Thanks nvoight your code works.

Quote:

---

So c_str() is easier to read, and taking the address of the first element of the string is not guaranteed to work.

---

Why is it possible for c_str() to be guaranteed if passing the address of the first element is not? You say that the underlying storage of a string may not be stored contiguously, so what does c_str() really do different besides return an address? Does it make sure that the characters are arranged in order and null terminated?

Yes. It is allowed for an implementation to move the string (or make a copy) to somewhere else so that c_str() returns contiguous and null terminated characters. The implementation can wait to do this until c_str() is actually called, which would be an optimization if you don't call c_str().

In practice, at least one library I've seen leaves the null-terminator off the end, and then just adds it if c_str() is called. I don't remember which one, but I've seen issues where people get garbage when they use data(), which is the same as c_str() but doesn't null terminate automatically.

Thanks Daved, that makes sense.

Could someone explain what type of data h is?

It's just declared: unsigned. What does that mean?

Thanks!

h is an unsigned int.

So the compiler just assumes an int then?

unsigned if a modifier of an integral type. If there is no length specifier (short, long, char, int) given, the compiler assumes int. So "unsigned x;" is functionally equivalent to "unsigned int x;"

Hi... does this gives the same results:

Code:

---

#include <iostream>
#include <string>

using std::cout;
using std::cin;
using std::endl;
using std::string;

int Hash(const string& key) {
        int h = 0, i = 0;
        for(i=0; i<key.size(); i++) {
                h=33*h+key.c_str()[i];
        }
        return h;
}

int main(void) {
        string data;
        cout << "String: "; cin >> data; // Joel
        cout << "Hashed: " << Hash(data) << endl; // 2783658
        return 0;
}

---

Probably not, because now the return type is signed int.

Code:

---

33*h+key.c_str()[i];

---

Because this wraps over (to negative values) if h becomes too large.

But why would you go through all the pain to get the character if [] is meant for that?