... | ... | @@ -5,8 +5,9 @@ |
|
|
|
|
|
***We are happy to incorporate content from volunteers!!***
|
|
|
|
|
|
## Coding Patterns - HashTable
|
|
|
|
|
|
## Coding Patterns
|
|
|
[[_TOC_]]
|
|
|
|
|
|
### HashSet iteration
|
|
|
|
... | ... | @@ -118,8 +119,89 @@ else |
|
|
}
|
|
|
```
|
|
|
|
|
|
|
|
|
### 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);
|
|
|
```
|
|
|
|
|
|
0. original integer
|
|
|
1. implicitly construct string with a single character (eg, 65 = "A")
|
|
|
2. 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 OpenCFD Ltd.
|
|
|
Copyright (C) 2019-2020 OpenCFD Ltd.
|
|
|
|
|
|
[code-patterns]: /coding/patterns/patterns |