hopscotch map
v2.3.1
A biblioteca hopscotch-map é uma implementação C++ de um mapa de hash rápido e um conjunto de hash usando endereçamento aberto e hash de amarelinha para resolver colisões. É uma estrutura de dados amigável ao cache que oferece melhor desempenho do que std::unordered_map na maioria dos casos e é muito semelhante a google::dense_hash_map embora use menos memória e forneça mais funcionalidades.
A biblioteca fornece as seguintes classes principais: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map e tsl::hopscotch_pg_set . Os dois primeiros são mais rápidos e usam uma política de crescimento de potência de dois, os dois últimos usam uma política de crescimento principal e são capazes de lidar melhor com uma função hash pobre. Use a versão principal se houver uma chance de padrões repetidos nos bits inferiores do seu hash (por exemplo, você está armazenando ponteiros com uma função hash de identidade). Consulte GrowthPolicy para obter detalhes.
Além dessas classes, a biblioteca também fornece tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map e tsl::bhopscotch_pg_set . Essas classes têm um requisito adicional para a chave, deve ser LessThanComparable , mas fornecem um limite superior assintótico melhor, veja detalhes no exemplo. No entanto, se você não tiver requisitos específicos (risco de ataques DoS de hash), tsl::hopscotch_map e tsl::hopscotch_set devem ser suficientes na maioria dos casos e devem ser sua escolha padrão, pois apresentam melhor desempenho em geral.
Uma visão geral do hash da amarelinha e alguns detalhes de implementação podem ser encontrados aqui.
Uma referência de tsl::hopscotch_map em relação a outros mapas hash pode ser encontrada aqui. Esta página também fornece alguns conselhos sobre qual estrutura de tabela hash você deve tentar para seu caso de uso (útil se você estiver um pouco perdido com as múltiplas implementações de tabelas hash no namespace tsl ).
tsl::hopscotch_map do CMakeLists.txt.find com um tipo diferente de Key (por exemplo, se você tiver um mapa que usa std::unique_ptr<foo> como chave, você pode usar um foo* ou um std::uintptr_t como parâmetro key para find sem construir um std::unique_ptr<foo> , veja o exemplo).precalculated_hash na API).tsl::bhopscotch_map e tsl::bhopscotch_set fornecem um pior caso de O(log n) em pesquisas e exclusões, tornando essas classes resistentes a ataques de negação de serviço (DoS) de tabela hash (veja detalhes no exemplo).-fno-exceptions no Clang e GCC, sem uma opção /EH no MSVC ou simplesmente definindo TSL_NO_EXCEPTIONS ). std::terminate é usado em substituição à instrução throw quando as exceções são desativadas.std::unordered_map e std::unordered_set .std::unordered_map tsl::hopscotch_map tenta ter uma interface semelhante a std::unordered_map , mas existem algumas diferenças.
erase , invalida todos os iteradores (consulte a API para obter detalhes).operator*() e operator->() retornam uma referência e um ponteiro para const std::pair<Key, T> em vez de std::pair<const Key, T> , tornando o valor T não modificável. Para modificar o valor você deve chamar o método value() do iterador para obter uma referência mutável. Exemplo: tsl::hopscotch_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
// it->second = 2; // Illegal
it. value () = 2 ; // Ok
}bucket_size , bucket , ...). Essas diferenças também se aplicam entre std::unordered_set e tsl::hopscotch_set .
As garantias de segurança e exceções de thread são as mesmas de std::unordered_map/set (ou seja, é possível ter vários leitores sem gravador).
A biblioteca oferece suporte a diversas políticas de crescimento por meio do parâmetro de modelo GrowthPolicy . Três políticas são fornecidas pela biblioteca, mas você pode implementar facilmente as suas próprias, se necessário.
tsl::(b)hopscotch_map/set . Esta política mantém o tamanho da matriz de buckets da tabela hash em uma potência de dois. Essa restrição permite que a política evite o uso da operação de módulo lento para mapear um hash para um bucket; em vez de hash % 2 n , ela usa hash & (2 n - 1) (consulte módulo rápido). Rápido, mas isso pode causar muitas colisões com uma função hash ruim, pois o módulo com potência de dois apenas mascara os bits mais significativos no final.tsl::(b)hopscotch_pg_map/set . A política mantém o tamanho da matriz de buckets da tabela hash em um número primo. Ao mapear um hash para um bucket, usar um número primo como módulo resultará em uma melhor distribuição dos hashes entre os buckets, mesmo com uma função de hash ruim. Para permitir que o compilador otimize a operação do módulo, a política usa uma tabela de consulta com módulos primos constantes (consulte a API para obter detalhes). Mais lento que tsl::hh::power_of_two_growth_policy , mas mais seguro. Se você encontrar um desempenho ruim, verifique overflow_size() , se não for zero, você poderá ter muitas colisões de hash. Mude a função hash para algo mais uniforme ou tente outra política de crescimento (principalmente tsl::hh::prime_growth_policy ). Infelizmente, às vezes é difícil proteger-se contra colisões (por exemplo, ataque DoS no mapa hash). Se necessário, verifique também tsl::bhopscotch_map/set que oferece o pior cenário de O(log n) em pesquisas em vez de O(n), veja detalhes no exemplo.
Para implementar sua própria política, você deve implementar a interface a seguir.
struct custom_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.
explicit custom_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_t bucket_for_hash (std:: size_t hash) const noexcept ;
// Return the number of buckets that should be used on next growth
std:: size_t next_bucket_count () const ;
// Maximum number of buckets supported by the policy
std:: size_t max_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.
void clear () noexcept ;
}Para usar o hopscotch-map, basta adicionar o diretório include ao seu caminho de inclusão. É uma biblioteca somente de cabeçalho .
Se você usar o CMake, também poderá usar o destino exportado tsl::hopscotch_map do CMakeLists.txt com target_link_libraries .
# Example where the hopscotch-map project is stored in a third-party directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map) Se o projeto foi instalado por meio de make install , você também pode usar find_package(tsl-hopscotch-map REQUIRED) em vez de add_subdirectory .
O código deve funcionar com qualquer compilador compatível com o padrão C++17.
Para executar os testes você precisará da biblioteca Boost Test e do CMake.
git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests A API pode ser encontrada aqui.
Todos os métodos ainda não estão documentados, mas replicam o comportamento daqueles em std::unordered_map e std::unordered_set , exceto se especificado de outra forma.
# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >
int main () {
tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
map[ " c " ] = 3 ;
map[ " d " ] = 4 ;
map. insert ({ " e " , 5 });
map. erase ( " b " );
for ( auto it = map. begin (); it != map. end (); ++it) {
// it->second += 2; // Not valid.
it. value () += 2 ;
}
// {d, 6} {a, 3} {e, 7} {c, 5}
for ( const auto & key_value : map) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
if (map. find ( " a " ) != map. end ()) {
std::cout << " Found " a " . " << std::endl;
}
const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
// If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
if (map. find ( " a " , precalculated_hash) != map. end ()) {
std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
}
/*
* Calculating the hash and comparing two std::string may be slow.
* We can store the hash of each std::string in the hash map to make
* the inserts and lookups faster by setting StoreHash to true.
*/
tsl::hopscotch_map<std::string, int , std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int >>,
30 , true > map2;
map2[ " a " ] = 1 ;
map2[ " b " ] = 2 ;
// {a, 1} {b, 2}
for ( const auto & key_value : map2) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
tsl::hopscotch_set< int > set;
set. insert ({ 1 , 9 , 0 });
set. insert ({ 2 , - 1 , 9 });
// {0} {1} {2} {9} {-1}
for ( const auto & key : set) {
std::cout << " { " << key << " } " << std::endl;
}
} Sobrecargas heterogêneas permitem o uso de outros tipos além de Key para operações de pesquisa e apagamento, desde que os tipos usados sejam hasháveis e comparáveis a Key .
Para ativar as sobrecargas heterogêneas em tsl::hopscotch_map/set , o ID qualificado KeyEqual::is_transparent deve ser válido. Funciona da mesma maneira que std::map::find . Você pode usar std::equal_to<> ou definir seu próprio objeto de função.
Tanto KeyEqual quanto Hash precisarão ser capazes de lidar com os diferentes tipos.
# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
struct employee {
employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
}
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator ==( const employee& empl, int empl_id) {
return empl. m_id == empl_id;
}
friend bool operator ==( int empl_id, const employee& empl) {
return empl_id == empl. m_id ;
}
friend bool operator ==( const employee& empl1, const employee& empl2) {
return empl1. m_id == empl2. m_id ;
}
int m_id;
std::string m_name;
};
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void ;
bool operator ()( const employee& empl, int empl_id) const {
return empl. m_id == empl_id;
}
bool operator ()( int empl_id, const employee& empl) const {
return empl_id == empl. m_id ;
}
bool operator ()( const employee& empl1, const employee& empl2) const {
return empl1. m_id == empl2. m_id ;
}
};
struct hash_employee {
std:: size_t operator ()( const employee& empl) const {
return std::hash< int >()(empl. m_id );
}
std:: size_t operator ()( int id) const {
return std::hash< int >()(id);
}
};
int main () {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map;
map. insert ({ employee ( 1 , " John Doe " ), 2001 });
map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
map. insert ({ employee ( 3 , " John Smith " ), 2003 });
// John Smith 2003
auto it = map. find ( 3 );
if (it != map. end ()) {
std::cout << it-> first . m_name << " " << it-> second << std::endl;
}
map. erase ( 1 );
// Use a custom KeyEqual which has an is_transparent member type
tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });
// 2004
std::cout << map2. at ( 4 ) << std::endl;
} Além de tsl::hopscotch_map e tsl::hopscotch_set , a biblioteca oferece mais duas opções "seguras": tsl::bhopscotch_map e tsl::bhopscotch_set (todas com suas contrapartes pg ).
Essas duas adições têm uma complexidade assintótica de pior caso de O(log n) para pesquisas e exclusões e um pior caso amortizado de O(log n) para inserções (amortizado devido à possibilidade de repetição que seria em O(n)) . Mesmo que a função hash mapeie todos os elementos para o mesmo intervalo, o O(log n) ainda seria válido.
Isso fornece segurança contra ataques de negação de serviço (DoS) em tabelas hash.
Para conseguir isso, as versões seguras usam uma árvore de busca binária para os elementos sobrecarregados (veja detalhes de implementação) e, portanto, precisam que os elementos sejam LessThanComparable . É necessário um parâmetro de modelo Compare adicional.
# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >
/*
* Poor hash function which always returns 1 to simulate
* a Deny of Service attack.
*/
struct dos_attack_simulation_hash {
std:: size_t operator ()( int id) const {
return 1 ;
}
};
int main () {
/*
* Slow due to the hash function, insertions are done in O(n).
*/
tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
auto start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map. insert ({i, 0 });
}
auto end = std::chrono::high_resolution_clock::now ();
// 110 ms
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
/*
* Faster. Even with the poor hash function, insertions end-up to
* be O(log n) in average (and O(n) when a rehash occurs).
*/
tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map_secure. insert ({i, 0 });
}
end = std::chrono::high_resolution_clock::now ();
// 2 ms
duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
} O código está licenciado sob a licença MIT, consulte o arquivo LICENSE para obter detalhes.
