A fast, memory efficient hash map for C++
I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit more memory is not acceptable. I will personally switch to using the parallel hashmap, which I believe offers a significantly better tradeoff (slightly higher memory usage, much faster).
Sparsepp is derived from Google's excellent sparsehash implementation. It aims to achieve the following objectives:
We believe Sparsepp provides an unparalleled combination of performance and memory usage, and will outperform your compiler's unordered_map on both counts. Only Google's dense_hash_map is consistently faster, at the cost of much greater memory usage (especially when the final size of the map is not known in advance, and insertions cause a resizing).
This hash map. like Google's dense_hash_map, uses open addressing (meaning that the hash table entries are conceptually stored in a big array, and collisions are not resolved using a linked list, but by probing). A big drawback of open addressing is that when the array needs to be resized larger, the high mark for memory usage is typically 3 times the current map size (as we allocate a new array twice as big as the current one, and copy from the old array to the new one). Sparsepp's implementation resolves this memory usage issue, and the memory usage high mark shows only a small bump when resizing.
For a detailed comparison of various hash implementations, including Sparsepp, please see our write-up.
#include
#include
#include
using spp::sparse_hash_map;
int main()
{
// Create an unordered_map of three strings (that map to strings)
sparse_hash_map email =
{
{ "tom", "[email protected]"},
{ "jeff", "[email protected]"},
{ "jim", "[email protected]"}
};
// Iterate and print keys and values
for (const auto& n : email)
std::cout `
This provides the implementation for the following classes:
```c++
namespace spp
{
template ,
class EqualKey = std::equal_to,
class Alloc = libc_allocator_with_realloc>>
class sparse_hash_map;
template ,
class EqualKey = std::equal_to,
class Alloc = libc_allocator_with_realloc>
class sparse_hash_set;
};These classes provide the same interface as std::unordered_map and std::unordered_set, with the following differences:
Calls to erase() may invalidate iterators. However, conformant to the C++11 standard, the position and range erase functions return an iterator pointing to the position immediately following the last of the elements erased. This makes it easy to traverse a sparse hash table and delete elements matching a condition. For example to delete odd values:
for (auto it = c.begin(); it != c.end(); )
if (it->first % 2 == 1)
it = c.erase(it);
else
++it;…c++ #include
struct Hash64 { size_t operator()(uint64_t k) const { return (k ^ 14695981039346656037ULL) * 1099511628211ULL; } };
struct Hash32 { size_t operator()(uint32_t k) const { return (k ^ 2166136261U) * 16777619UL; } };
int main() { spp::sparse_hash_map map; ... }
…c++ #include #include #include #include
using std::string;
struct Person { bool operator==(const Person &o) const { return _first == o._first && _last == o._last; }
string _first;
string _last;
};
namespace std { // inject specialization of std::hash for Person into namespace std // ---------------------------------------------------------------- template<> struct hash { std::size_t operator()(Person const &p) const { std::size_t seed = 0; spp::hash_combine(seed, p._first); spp::hash_combine(seed, p._last); return seed; } }; }
int main() { // As we have defined a specialization of std::hash() for Person, // we can now create sparse_hash_set or sparse_hash_map of Persons // ---------------------------------------------------------------- spp::sparse_hash_set persons = { { "John", "Galt" }, { "Jane", "Doe" } }; for (auto& p: persons) std::cout #include
using std::string;
struct Person { bool operator==(const Person &o) const { return _first == o._first && _last == o._last && _age == o._age; }
string _first;
string _last;
int _age;
};
namespace std { // inject specialization of std::hash for Person into namespace std // ---------------------------------------------------------------- template<> struct hash { std::size_t operator()(Person const &p) const { std::size_t seed = 0; spp::hash_combine(seed, p._first); spp::hash_combine(seed, p._last); spp::hash_combine(seed, p._age); return seed; } }; }
## Example 3 - serialization
sparse_hash_set and sparse_hash_map can easily be serialized/unserialized to a file or network connection.
This support is implemented in the following APIs:
```c++
template
bool serialize(Serializer serializer, OUTPUT *stream);
template
bool unserialize(Serializer serializer, INPUT *stream);The following example demonstrates how a simple sparse_hash_map can be written to a file, and then read back. The serializer we use read and writes to a file using the stdio APIs, but it would be equally simple to write a serialized using the stream APIS:
#include
#include
using spp::sparse_hash_map;
using namespace std;
class FileSerializer
{
public:
// serialize basic types to FILE
// -----------------------------
template
bool operator()(FILE *fp, const T& value)
{
return fwrite((const void *)&value, sizeof(value), 1, fp) == 1;
}
template
bool operator()(FILE *fp, T* value)
{
return fread((void *)value, sizeof(*value), 1, fp) == 1;
}
// serialize std::string to FILE
// -----------------------------
bool operator()(FILE *fp, const string& value)
{
const size_t size = value.size();
return (*this)(fp, size) && fwrite(value.c_str(), size, 1, fp) == 1;
}
bool operator()(FILE *fp, string* value)
{
size_t size;
if (!(*this)(fp, &size))
return false;
char* buf = new char[size];
if (fread(buf, size, 1, fp) != 1)
{
delete [] buf;
return false;
}
new (value) string(buf, (size_t)size);
delete[] buf;
return true;
}
// serialize std::pair to FILE - needed for maps
// ---------------------------------------------------------
template
bool operator()(FILE *fp, const std::pair& value)
{
return (*this)(fp, value.first) && (*this)(fp, value.second);
}
template
bool operator()(FILE *fp, std::pair *value)
{
return (*this)(fp, (A *)&value->first) && (*this)(fp, &value->second);
}
};
int main(int argc, char* argv[])
{
sparse_hash_map age{ { "John", 12 }, {"Jane", 13 }, { "Fred", 8 } };
// serialize age hash_map to "ages.dmp" file
FILE *out = fopen("ages.dmp", "wb");
age.serialize(FileSerializer(), out);
fclose(out);
sparse_hash_map age_read;
// read from "ages.dmp" file into age_read hash_map
FILE *input = fopen("ages.dmp", "rb");
age_read.unserialize(FileSerializer(), input);
fclose(input);
// print out contents of age_read to verify correct serialization
for (auto& v : age_read)
printf("age_read: %s -> %d\n", v.first.c_str(), v.second);
}Sparsepp follows the thread safety rules of the Standard C++ library. In Particular:
A single sparsepp hash table is thread safe for reading from multiple threads. For example, given a hash table A, it is safe to read A from thread 1 and from thread 2 simultaneously.
If a single hash table is being written to by one thread, then all reads and writes to that hash table on the same or other threads must be protected. For example, given a hash table A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.
It is safe to read and write to one instance of a type even if another thread is reading or writing to a different instance of the same type. For example, given hash tables A and B of the same type, it is safe if A is being written in thread 1 and B is being read in thread 2.
No open issues yet, or sync has not completed.