HashTable · Wiki · Development / openfoam

We are happy to incorporate content from volunteers!!

Coding Patterns - HashTable

Coding Patterns - HashTable

HashSet iteration

\since 1706

Use a range-for to dereference the HashSet iterators directly:

labelHashSet ids ...;

for (const label id : ids)
{
    os << id << nl;
}

Note that since label is a primitive we use it directly instead of a reference. For a wordHashSet this is slightly different:

wordHashSet identifiers ...;

for (const word& ident : identifiers)
{
    os << ident << nl;
}

Anti-pattern: using iterators:

labelHashSet ids ...;

forAllConstIters(ids, iter)
{
    os <<iter.key() << nl;
}

// Even worse - using old macros!
forAllConstIter(labelHashSet, ids, iter)
{
    os <<iter.key() << nl;
}

HashSet/HashTable/Map toc()

\since 1706

Use a range-for when using toc() or sortedToc() to access hashes. It avoids an intermediate variable, and C++ will only need to create the end-iterator once.

HashTable<Type> myHash ...;

for (const word& ident : myHash.sortedToc())
{
    os << ident << " = " << myHash[ident] << nl;
}

Anti-pattern: using an intermediate variable for storage:

HashTable<Type> myHash ...;

const wordList keys(myHash.sortedToc());

for (const word& ident : keys)
{
    os << ident << " = " << myHash[ident] << nl;
}

The compiler might be smart enough to eliminate the intermediate variable, but the code is less clear and separating the population of intermediate with its use risks potential mismatches in the future when code is modified.

HashTable, Map

\since 1706

Use lookup() to handle default values (const-access) and the operator() to create new zero-initialized entries if required:

Map<label> counter;
...

os << "hits: " << counter.lookup(i, 0) << nl;

++counter(j);

Anti-pattern: the manual equivalents:

Map<label> counter;
...

os << "hits: " << (counter.found(i) ? *(counter.cfind(i)) : 0) << nl;


Map<label>::iterator iter = counter.find(j);

if (!iter.found())
{
    counter.insert(j, 0);
}
else
{
    ++(*iter);
}

HashTable completely broken?

Some reports of "HashTable is completely broken" can be related to incorrect use of HashTable and misunderstanding its hashing function. Examining its template signature:

template<class T, class Key=word, class Hash=string::hash>
class HashTable;

In this template:

T is some arbitrary type that you want to store.
Key is how you want to look it up. By default a Foam::word, but you can specify other types. If the key type is some type of string, the default Hash parameter is already setup for you.
Hash is the hashing mechanism for converting the keys to integers for the table. The default is set for hashing strings. If your key is not derived from string, you will need to provide a different hasher.

Good examples:

HashTable<vector> hash1;
HashTable<vector, fileName> hash2;

Anti-pattern: using a non-string key:

HashTable<vector, label> badHash1;

To understand why this example is really bad (does not even compile), consider it with the default hasher:

HashTable<vector, label, string::hash> badHash1;

This means that you are trying to use a string hasher on a number!!

In older versions of OpenFOAM this actually did compile, but the result was really horrible. In the 1806 version, the string constructor (from character) was made explicit and this bad code will not compile. Before arguing that this is too pedantic, consider what it was doing:

HashTable<vector, label> badHash1;

badHash1.insert(100, vector(1,0,0);
badHash1.insert(200, vector(0,1,0);
badHash1.insert(300, vector(0,0,1);

original integer
implicitly construct string with a single character (eg, 65 = "A")
hash the byte contents of the string storage

This is not only horribly inefficient, but will provoke a large number of hash collisions (eg, 1024 wraps back to 0) that make a hashtable very, very slow.

Recommendation:

Use the special hash tables definitions for frequently encountered key types. If you have something different, you will need to provide a hasher for it. Note that FixedList and List provide predefined hashers.

Definition	Key type
EdgeMap	edge
Map	label

The proper solution for the previous example:

Map<vector> goodHash1;

goodHash1.insert(100, vector(1,0,0);
goodHash1.insert(200, vector(0,1,0);
goodHash1.insert(300, vector(0,0,1);