unordered_set: является ли адрес указателя хорошим хешем? - PullRequest
Новая
       40

unordered_set: является ли адрес указателя хорошим хешем?

3 голосов
/ 19 октября 2011

Я хочу сохранить набор (умных) указателей в хэш-наборе, либо <boost/unordered_set>. После 10 секунд размышлений я придумал эту хэш-функцию: 

typedef boost::shared_ptr<myType> ref_t;
struct SharedPtrHash : public std::unary_function<ref_t, std::size_t> {                        
    std::size_t operator()(ref_t const& obj) const {
      return reinterpret_cast<std::size_t>( obj.get() );
    }
};

Мой вопрос: хорошая ли эта хеш-идея? меня развлекает мысль, что этот хеш будет иметь нулевое или очень малое количество столкновений (возможно, под капотом есть какой-то модуль простых чисел, портящий все мое веселье).

Дополнительная информация о цели: Цель хэша - переработка хранилища больших объектов, поэтому мне нужен быстрый способ определить, есть ли большой объект в корзине.

в противном случае, какой будет идеальный хеш для указателей, умных или тупых?

Ответы [ 3 ]

4 голосов
/ 19 октября 2011

Если вы хотите обнаружить объекты, которые не идентичны, даже если их содержимое может быть одинаковым, у вас есть нет выбора , но вы должны использовать адрес объекта в хэше.Единственный вопрос - использовать ли адрес напрямую или запустить его через формулу.Деление на sizeof(mytype) приведет к ужесточению дыр в распределении.

Edit: Вот непроверенная реализация шаблона, которая должна работать со всеми типами shared_ptr вместе с функцией equal_toвыполнить требования для std::unordered_set.Не используйте эту универсальную реализацию, если у вас есть другие объекты, которые требуют хеш на основе значения вместо указателя. 

template<typename T>
size_t hash(const std::shared_ptr<T> & ptr)
{
    return ((size_t) ptr.get()) / sizeof(T);
}

template<typename T>
bool equal_to(const std::shared_ptr<T> & left, const std::shared_ptr<T> & right)
{
    return left.get() == right.get();
}
1 голос
/ 19 октября 2011

Следующий код отлично компилируется (GCC 4.7, Boost 1.47): 

#include <boost/unordered_set.hpp>
#include <boost/shared_ptr.hpp>

struct Foo { };

int main()
{
  boost::unordered_set<boost::shared_ptr<int>> s;
  boost::shared_ptr<int> pi(new int);
  s.insert(pi);

  boost::unordered_set<boost::shared_ptr<Foo>> t;
  boost::shared_ptr<Foo> pf(new Foo);
  t.insert(pf);
}
0 голосов
/ 19 октября 2011

Функция по умолчанию Boost.Hash hash для целочисленных типов - это функция тождества, поэтому я не думаю, что делать то же самое для указателей - плохая идея.Это будет иметь тот же коэффициент столкновения.

...