linuxdcpp-team team mailing list archive
-
linuxdcpp-team team
-
Mailing list archive
-
Message #07062
[Bug 1193899] Re: Incorrect hasher for class CID.
i was doubtful 4/8 bytes generated from calculations could be any more
unique than just taking the first 4/8 bytes of the CID, so i tried a
basic test:
size_t buckets = onlineUsers.bucket_count();
size_t collisions = 0;
size_t coll_buckets = 0;
for(size_t i = 0; i < buckets; ++i) {
auto items = onlineUsers.bucket_size(i);
if(items > 1) { collisions += items - 1; ++coll_buckets; }
}
printf("%d users - %d buckets in total - %d collisions in %d buckets\n", onlineUsers.size(), buckets, collisions, coll_buckets);
the results confirmed my intuition:
before the patch: 18825 users - 30727 buckets in total - 4755 collisions in 3850 buckets
after the patch: 17756 users - 30727 buckets in total - 4229 collisions in 3482 buckets
if you can find evidence that this change does reduce collisions, please
provide it; for now, this is nonsense to me.
unrelated point: the change from CID to CID* as key in hashed containers
in rev 14282 seems very strange, especially the custom hasher (the STL
should already know how to hash pointers...).
** Changed in: dcplusplus
Status: New => Incomplete
--
You received this bug notification because you are a member of
Dcplusplus-team, which is subscribed to DC++.
https://bugs.launchpad.net/bugs/1193899
Title:
Incorrect hasher for class CID.
Status in DC++:
Incomplete
Bug description:
Please replace the incorrect class hasher CID, on hasher, taking into
account all the data, and as a consequence. eliminating collisions.
This change will increase the efficiency of search hashing.
#include <boost/functional/hash.hpp>
class CID
{
...
size_t toHash() const
{
return boost::hash<uint8_t[SIZE]>()(cid);
}
...
};
namespace std
{
template<>
struct hash<CID>
{
size_t operator()(const CID& rhs) const
{
return rhs.toHash();
}
};
template<>
struct hash<CID*>
{
size_t operator()(const CID* rhs) const
{
return rhs->toHash();
}
};
...
}
Original commit from FlylinkDC++:
https://code.google.com/p/flylinkdc/source/detail?r=14282 and
https://code.google.com/p/flylinkdc/source/detail?r=14283
To manage notifications about this bug go to:
https://bugs.launchpad.net/dcplusplus/+bug/1193899/+subscriptions
References