Program Listing for File MinimalPerfectHash.h

↰ Return to documentation for file (ADS/dictionary/MinimalPerfectHash.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File MinimalPerfectHash.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_MinimalPerfectHash
 #define __ADS_MinimalPerfectHash
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/dictionary/FastHash.h"

#include <algorithm>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS MinimalPerfectHash ------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class H = DefaultHash< T > >
class MinimalPerfectHash {

/*--------------------------------------------------------------------------*/
 public:

 using Key = T;

 explicit MinimalPerfectHash( const std::vector< T > & keys ,
                              double lambda = 5 , double alpha = 0.99 ,
                              std::uint64_t seed = 1 , H h = H() );

 [[nodiscard]] std::size_t operator()( const T & k ) const;

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] std::size_t bits( void ) const;

 [[nodiscard]] std::size_t buckets( void ) const;

 [[nodiscard]] std::size_t trials( void ) const;

/*--------------------------------------------------------------------------*/
 private:

 static constexpr std::size_t kMaxTrials = 100;
 static constexpr std::uint64_t kMaxPilot = std::uint64_t( 1 ) << 24;

 [[nodiscard]] std::uint64_t base( const T & k ) const;

 [[nodiscard]] std::size_t bucket( std::uint64_t h ) const;

 [[nodiscard]] std::size_t place( std::uint64_t h2 , std::uint64_t k ) const;

 [[nodiscard]] std::uint64_t pilot( std::size_t b ) const;

 bool build( const std::vector< std::uint64_t > & B );

 std::uint64_t f_seed;
 std::size_t f_n = 0;
 std::size_t f_m = 0;
 std::size_t f_dense = 0;
 std::size_t f_sparse = 0;
 int f_w = 0;
 std::vector< std::uint64_t > f_P;
 std::vector< std::uint32_t > f_free;
 std::size_t f_trials = 0;
 H f_h;

 };  // end( class MinimalPerfectHash )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/dictionary/impl/MinimalPerfectHash.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* MinimalPerfectHash.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File MinimalPerfectHash.h ---------------------*/
/*--------------------------------------------------------------------------*/