Hashing a string to an integer in c++

Question

I am trying to figure out the conversion process for strings to ints. We are doing a program with hashing, in which the key value to be hashed is the name of a state. From my research, it seems like atoi() will not work.

Do I need to break each letter of the word down and individually convert? Do I use ASCII? Am I completely going in the wrong direction?

I am very lost, so ANY information would be fantastic. Thanks!

Solution 1

C++11 introduces an implementation defined hashing function called std::hash in header <functional> which has speciality for the string classes std::string, std::wstring, etc.

It's as simple as doing this:

#include <iostream>
#include <functional> //for std::hash
#include <string>

int main() {
    std::string str = "Hello World";
    std::hash<std::string> hasher;
    auto hashed = hasher(str); //returns std::size_t
    std::cout << hashed << '\n'; //outputs 2146989006636459346 on my machine
}

Specializing std::hash for your user defined types isn't very complex either. Do note however that there is no std::hash specialization for const char* or any of the C-strings.

Solution 2

You need a hash function to turn your string into a more or less arbitrary integer. There are many to choose from, and yes they typically use the ASCII values of the string. Here's one called djb2

unsigned long hash(const std::string& str)
{
    unsigned long hash = 5381;
    for (size_t i = 0; i < str.size(); ++i)
        hash = 33 * hash + (unsigned char)str[i];
    return hash;
}

Please don't take this as a recommendation that this is a good hash function, that's a whole different topic.

Solution 3

From here, there are two function to convert string to uint32_t or uint64_t, convert to uint32_t:

inline uint32_t hash_str_uint32(const std::string& str) {

    uint32_t hash = 0x811c9dc5;
    uint32_t prime = 0x1000193;

    for(int i = 0; i < str.size(); ++i) {
        uint8_t value = str[i];
        hash = hash ^ value;
        hash *= prime;
    }

    return hash;

}

Test:

Comments

[Rapptz]

I don't think OP is asking about a string of digits to an integer.

[user2109706]

Yes, I need to convert a word, like "Alaska" or "Illinois" to an int, so then I can hash it.

[user2109706]

Would I be able to do this if the string I am trying to convert is a state name, say "Alaska" or "Illinois" ?

[john]

@user2109706 Yes, this function will convert any string into a hash code. The important point is that "Alaska" and "Illinois" will be converted into different hash codes (I hope).

[cHao]

@user2109706: The very process of turning a (non-numeric) string into an int is hashing it.

[user2109706]

Ah, I see. Thank you John, I will give it a try.