Unordered (hash) map from bitset to bitset on boost

Question

Я хочу использовать кеш, реализованный unordered_map от boost, от dynamic_bitset до dynamic_bitset. Проблема, конечно, в том, что не существует хеш-функции по умолчанию из битового набора. Это не похоже на концептуальную проблему, но я не знаю, как выработать технику. Как мне это сделать?

Answer 1

я нашел неожиданное решение. Оказывается, у boost есть опция #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Когда это определено, частные члены, включая m_bits, становятся общедоступными (я думаю, что там есть дело со старыми компиляторами или чем-то еще).

Так что теперь я могу использовать @ ответ KennyTM, в видоизменилась:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

Answer 2

to_block_range Функция копирует слова, которые битовый набор состоит из некоторого буфера. Чтобы избежать фактического копирования, вы можете определить свой собственный «выходной итератор», который просто обрабатывает отдельные слова и вычисляет хэш из них. Число рейнольдса как вычислить хеш: см., например, функция хеша FNV.

К сожалению, дизайн dynamic_bitset является IMHO, braindead, потому что он не дает вам прямого доступа к базовому буферу (даже не как const).

Answer 3

Это feature request.

Можно реализовать не так эффективно уникальный хеш путем преобразования BitSet к вектору временной:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     std::vector<B, A> v; 
     boost::to_block_range(bs, std::back_inserter(v)); 
     return boost::hash_value(v); 
    } 
} 

Answer 4

Мы не можем непосредственно вычислить хэш, поскольку исходные данные в dynamic_bitset является частным (m_bits)

Но мы можем легко утонченность мимо (подрывать!) C++ спецификации системы доступа без любой

• взлома в коде или
• притворяясь ваш компилятор несоответствующего (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

Ключ шаблон функции to_block_range который является friend к dynamic_bitset. Таким образом, специализации этой функции также имеют доступ к ее личным данным (т. Е. m_bits).

Полученный код не может быть проще

namespace boost { 


// specialise dynamic bitset for size_t& to return the hash of the underlying data 
template <> 
inline void 
to_block_range(const dynamic_bitset<>& b, size_t& hash_result) 
{ 
    hash_result = boost::hash_value(bs.m_bits); 
} 

std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) 
{    
    size_t hash_result; 
    to_block_range(bs, hash_result); 
    return hash_result; 
} 
} 

Answer 5

предлагаемое решение создает тот же хэш в следующей ситуации.

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS 

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

boost::dynamic_biset<> test(1,false); 

auto hash1 = boost::hash_value(test); 

test.push_back(false); 

auto hash2 = boost::hash_value(test); 

// keep continue... 

test.push_back(false); 

auto hash31 = boost::hash_value(test); 

// magically all hash1 to hash31 are the same! 

Предлагаемое решение иногда не подходит для хэш-карты.

Я прочитал исходный код dynamic_bitset, почему это произошло и понял, что dynamic_bitset сохраняет один бит за одно значение так же, как vector<bool>. Например, вы вызываете dynamic_bitset<> test(1, false), затем dynamic_bitset изначально выделяет 4 байта со всеми нулями и содержит размер бит (в этом случае размер равен 1).Обратите внимание: если размер битов становится больше 32, он снова выделяет 4 байта и возвращает его обратно в dynamic_bitsets<>::m_bits (так что m_bits - это вектор из 4 байтовых блоков).

Если я вызываю test.push_back(x), он устанавливает второй бит в x и увеличивает размер бит до 2. Если x является ложным, то m_bits[0] не меняется вообще! Чтобы правильно вычислить хеш, нам нужно взять m_num_bits в хэш-вычислении.

Тогда вопрос в том, как?

1: Использовать boost::hash_combine Этот подход прост и прямолинейный. Я не проверял этот компилятор или нет.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     size_t tmp = 0; 
     boost::hash_combine(tmp,bs.m_num_bits);   
     boost::hash_combine(tmp,bs.m_bits); 
     return tmp; 
    } 
} 

2: flip m_num_bits% bits_per_block th бит. переверните бит в зависимости от размера бит. Я считаю, что этот подход выполняется быстрее, чем 1.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     // you may need more sophisticated bit shift approach. 
     auto bit = 1u << (bs.m_num_bits % bs.bits_per_block); 
     auto return_val = boost::hash_value(bs.m_bits); 

     // sorry this was wrong 
     //return (return_val & bit) ? return_val | bit : return_val & (~bit); 
     return (return_val & bit) ? return_val & (~bit) : return_val | bit; 
    } 
}