← Back to team overview

linuxdcpp-team team mailing list archive

[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