-1
\$\begingroup\$

I'm studying hash tables, and wrote the following to serve as a simple example.

Does this properly demonstrate the basic concept of a hash table?

The values are int from 0 to 9; the hashing "algorithm" is simply to square the number.

#include <iostream>
#include <cmath>

const int KEY_RANGE=100;
const int VALUE_RANGE=10;

int main() {

    int a[KEY_RANGE], hashKey;
    for (int i=0; i<VALUE_RANGE; ++i) {
        hashKey = (int)pow(i,2);
        a[hashKey] = i;
    }
    std::cout << "Hash keys:" << std::endl;
    for (int i=0; i<VALUE_RANGE; ++i) {
        std::cout << (int)pow(i,2) << ' '; 
    }
    std::cout << std::endl << std::endl;
    std::cout << "Hashed values:" << std::endl;
    for (int i=0; i<VALUE_RANGE; ++i) {
        std::cout << a[(int)pow(i,2)] << ' '; 
    }
    std::cout << std::endl;
    return 0;
}

Output:

pickledEgg> g++ -std=c++11 -g -Og -o squareHash squareHash.cpp
pickledEgg> ./squareHash
Hash keys: 0 1 4 9 16 25 36 49 64 81
Hashed values: 0 1 2 3 4 5 6 7 8 9

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give a more concise example how the square hash key should improve accessing the values faster (since the values currently represent their index already). I don't think that's a good representation for a hash table, since there is a lot of unnecessary memory wasted. \$\endgroup\$ – πάντα ῥεῖ Jan 25 '17 at 19:13
  • 1
    \$\begingroup\$ Also note that the c++ standard already comes up with a good hash table implementation in the form of the std::unordered_map class. \$\endgroup\$ – πάντα ῥεῖ Jan 25 '17 at 19:18
3
\$\begingroup\$

While using the square does work (for at least some definition of the word), it's pretty close to the epitome of a poor hash function.

In particular, at least normally the intent with a hash function is to take some set of inputs and distribute them as evenly through the hash table as possible.

In this case, you're doing pretty close to the opposite of that, frequently (always) producing perfect squares and never producing any of the values in between.

To use your example of keys from 0 through 9, you need a hash table with 81 slots, but you'll only ever use 10 of those slots. That's a pretty poor percentage.

As far as the code itself goes:

Variable Definitions

I'd rather see each variable defined separately, so (for example) you'd replace this:

int a[KEY_RANGE], hashKey;

...with something like this:

int a[KEY_RANGE];
int hashKey;

Naming

An extremely short variable name like a can be handy for a variable that's itself extremely short-lived and you really just need a place-holder. For the obvious example, for (int i=0; i<10; i++) is perfectly fine.

For something like a hash table that (apparently) has a larger significance to your code, I'd prefer a more descriptive name.

Avoid std::endl

For example, you have:

std::cout << std::endl << std::endl;
std::cout << "Hashed values:" << std::endl;

I'd prefer to write this as:

std::cout << "\n\nHashed values:\n";

It's shorter, simpler, and more efficient (frequently around 8 to 10 times faster for code that needs to produce a lot of output).

Reserve all-caps for macros

I'd rather these:

const int KEY_RANGE=100;
const int VALUE_RANGE=10;

...were written as:

const int key_range = 100;
const int value_range = 10;
\$\endgroup\$
  • \$\begingroup\$ @Jerry I totally agree, especially with the 1st part of your answer. That could improved though, with some links how hash functions and hash tables typically should be designed (tries, B-trees, and such stuff). \$\endgroup\$ – πάντα ῥεῖ Jan 25 '17 at 20:12
  • \$\begingroup\$ E.g. en.wikipedia.org/wiki/Hash_array_mapped_trie \$\endgroup\$ – πάντα ῥεῖ Jan 25 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.