A C++ implementation of a fast and memory efficient hash map/set for strings

Overview

Differences compared tostd::unordered_map

Hash function

#include<city.h>structstr_hash {    std::size_toperator()(constchar* key, std::size_t key_size)const {returnCityHash64(key, key_size);    }};tsl::array_map<char,int, str_hash> map;

Growth policy

structcustom_policy {// Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets// that the hash table needs. The policy can change it to a higher number of buckets if needed// and the hash table will use this value as bucket count. If 0 bucket is asked, then the value// must stay at 0.explicitcustom_policy(std::size_t& min_bucket_count_in_out);// Return the bucket [0, bucket_count()) to which the hash belongs.// If bucket_count() is 0, it must always return 0.    std::size_tbucket_for_hash(std::size_t hash)constnoexcept;// Return the number of buckets that should be used on next growth    std::size_tnext_bucket_count()const;// Maximum number of buckets supported by the policy    std::size_tmax_bucket_count()const;// Reset the growth policy as if the policy was created with a bucket count of 0.// After a clear, the policy must always return 0 when bucket_for_hash() is called.voidclear()noexcept;}

Installation

# Example where the array-hash project is stored in a third-party directoryadd_subdirectory(third-party/array-hash)target_link_libraries(your_targetPRIVATE tsl::array_hash)

git clone https://github.com/Tessil/array-hash.gitcd array-hash/testsmkdir buildcd buildcmake ..cmake --build../tsl_array_hash_tests

Usage

Example

#include<iostream>#include<tsl/array_map.h>#include<tsl/array_set.h>intmain() {// Map of const char* to int    tsl::array_map<char,int> map = {{"one",1}, {"two",2}};    map["three"] =3;    map["four"] =4;        map.insert("five",5);    map.insert_ks("six_with_extra_chars_we_ignore",3,6);        map.erase("two");// When template parameter StoreNullTerminator is true (default) and there is no// null character in the strings.for(auto it = map.begin(); it != map.end(); ++it) {        std::cout <<"{" << it.key() <<"," << it.value() <<"}" << std::endl;    }// If StoreNullTerminator is false for space efficiency or you are storing null characters,// you can access to the size of the key.for(auto it = map.begin(); it != map.end(); ++it) {        (std::cout <<"{").write(it.key(), it.key_size()) <<"," << it.value() <<"}" << std::endl;    }// Better, use key_sv() if you compiler provides access to std::string_view.for(auto it = map.begin(); it != map.end(); ++it) {        std::cout <<"{" << it.key_sv() <<"," << it.value() <<"}" << std::endl;    }// Or if you just want the values.for(int value: map) {        std::cout <<"{" << value <<"}" << std::endl;    }// Map of const char32_t* to int    tsl::array_map<char32_t,int> map_char32 = {{U"one",1}, {U"two",2}};    map_char32[U"three"] =3;// Set of const char*    tsl::array_set<char> set = {"one","two","three"};    set.insert({"four","five"});for(auto it = set.begin(); it != set.end(); ++it) {        std::cout <<"{" << it.key() <<"}" << std::endl;    }}

Serialization

structserializer {// Must support the following types for U: std::uint64_t, float and T if a map is used.template<typename U>voidoperator()(const U& value);voidoperator()(const CharT* value, std::size_t value_size);};

structdeserializer {// Must support the following types for U: std::uint64_t, float and T if a map is used.template<typename U>    Uoperator()();voidoperator()(CharT* value_out, std::size_t value_size);};

#include<cassert>#include<cstdint>#include<fstream>#include<type_traits>#include<tsl/array_map.h>classserializer {public:serializer(constchar* file_name) {        m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);        m_ostream.open(file_name);    }template<classT,typename std::enable_if<std::is_arithmetic<T>::value>::type* =nullptr>voidoperator()(const T& value) {        m_ostream.write(reinterpret_cast<constchar*>(&value),sizeof(T));    }voidoperator()(constchar32_t* value, std::size_t value_size) {        m_ostream.write(reinterpret_cast<constchar*>(value), value_size*sizeof(char32_t));    }private:    std::ofstream m_ostream;};classdeserializer {public:deserializer(constchar* file_name) {        m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);        m_istream.open(file_name);    }template<classT,typename std::enable_if<std::is_arithmetic<T>::value>::type* =nullptr>    Toperator()() {        T value;        m_istream.read(reinterpret_cast<char*>(&value),sizeof(T));return value;    }voidoperator()(char32_t* value_out, std::size_t value_size) {        m_istream.read(reinterpret_cast<char*>(value_out), value_size*sizeof(char32_t));    }private:    std::ifstream m_istream;};intmain() {const tsl::array_map<char32_t, std::int64_t> map = {{U"one",1}, {U"two",2},                                                         {U"three",3}, {U"four",4}};constchar* file_name ="array_map.data";    {        serializerserial(file_name);        map.serialize(serial);    }        {        deserializerdserial(file_name);auto map_deserialized = tsl::array_map<char32_t, std::int64_t>::deserialize(dserial);assert(map == map_deserialized);    }        {        deserializerdserial(file_name);/**         * If the serialized and deserialized map are hash compatibles (see conditions in API),         * setting the argument to true speed-up the deserialization process as we don't have         * to recalculate the hash of each key. We also know how much space each bucket needs.*/constbool hash_compatible =true;auto map_deserialized =             tsl::array_map<char32_t, std::int64_t>::deserialize(dserial, hash_compatible);assert(map == map_deserialized);    }}

Serialization with Boost Serialization and compression with zlib

#include<boost/archive/binary_iarchive.hpp>#include<boost/archive/binary_oarchive.hpp>#include<boost/iostreams/filter/zlib.hpp>#include<boost/iostreams/filtering_stream.hpp>#include<boost/serialization/split_free.hpp>#include<boost/serialization/utility.hpp>#include<cassert>#include<cstdint>#include<fstream>#include<tsl/array_map.h>template<typename Archive>structserializer {    Archive& ar;template<typename T>voidoperator()(const T& val) { ar & val; }template<typename CharT>voidoperator()(const CharT* val, std::size_t val_size) {        ar.save_binary(reinterpret_cast<constvoid*>(val), val_size*sizeof(CharT));    }   };template<typename Archive>structdeserializer {    Archive& ar;template<typename T>    Toperator()() { T val; ar & val;return val; }template<typename CharT>voidoperator()(CharT* val_out, std::size_t val_size) {        ar.load_binary(reinterpret_cast<void*>(val_out), val_size*sizeof(CharT));    }  };namespaceboost {namespaceserialization {template<classArchive,classCharT,classT>voidserialize(Archive & ar, tsl::array_map<CharT, T>& map,constunsignedint version) {split_free(ar, map, version); }template<classArchive,classCharT,classT>voidsave(Archive & ar,const tsl::array_map<CharT, T>& map,constunsignedint version) {    serializer<Archive> serial{ar};    map.serialize(serial);}template<classArchive,classCharT,classT>voidload(Archive & ar, tsl::array_map<CharT, T>& map,constunsignedint version) {    deserializer<Archive> deserial{ar};    map = tsl::array_map<CharT, T>::deserialize(deserial);}}}intmain() {const tsl::array_map<char32_t, std::int64_t> map = {{U"one",1}, {U"two",2},                                                         {U"three",3}, {U"four",4}};constchar* file_name ="array_map.data";    {        std::ofstream ofs;        ofs.exceptions(ofs.badbit | ofs.failbit);        ofs.open(file_name, std::ios::binary);                boost::iostreams::filtering_ostream fo;        fo.push(boost::iostreams::zlib_compressor());        fo.push(ofs);                boost::archive::binary_oarchiveoa(fo);                oa << map;    }        {        std::ifstream ifs;        ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);        ifs.open(file_name, std::ios::binary);                boost::iostreams::filtering_istream fi;        fi.push(boost::iostreams::zlib_decompressor());        fi.push(ifs);                boost::archive::binary_iarchiveia(fi);             tsl::array_map<char32_t, std::int64_t> map_deserialized;           ia >> map_deserialized;assert(map == map_deserialized);    }}

License