194
Hash Table with Transactions
We present an example of a hash table implemented using transactions and containers
using libpmemobj-cpp.
As a quick primer to some, and a refresher to other readers, a hash table is a data
structure that maps keys to values and guarantees O(1) lookup time. It is usually
implemented as an array of buckets (a bucket is a data structure that can hold one or
more key-value pairs). When inserting a new element to the hash table, a hash function
is applied to the element’s key. The resulting value is treated as an index of a bucket
to which the element is inserted. It is possible that the result of the hash function for
different keys will be the same; this is called a collision. One method for resolving
collisions is to use separate chaining. This approach stores multiple key-value pairs in
one bucket; the example in Listing 11-4 uses this method.
For simplicity, the hash table in Listing 11-4 only provides the const Value&
get(const std::string &key) and void put(const std::string &key, const Value
&value) methods. It also has a fixed number of buckets. Extending this data structure
to support the remove operation and to have a dynamic number of buckets is left as an
exercise to you.
Listing 11-4. Implementation of a hash table using transactions
38 #include
39 #include
40 #include
41 #include
42 #include
43 #include
44 #include
45 #include
46 #include
47
48 #include "libpmemobj++/array.hpp"
49 #include "libpmemobj++/string.hpp"
50 #include "libpmemobj++/vector.hpp"
51
Chapter 11 Designing Data struCtures for persistent MeMory