We are happy to incorporate content from volunteers!!
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 aFoam::word
, but you can specify other types. If the key type is some type of string, the defaultHash
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);
Copyright (C) 2019-2020 OpenCFD Ltd.