CODEWITHSUNDEEP
c++optimizationhashstd
anatolyg
anatolyg

Reputation: 28241

unordered_map with forbidden collisions

I want to implement a performance-optimized variant of unordered_map that works in several phases:

  1. Initialization: Insert about 100 elements into std::map
  2. Preparation: Do some magic, converting std::map to a variant of std::unordered_map
  3. Work: Perform a large (unbounded) number of lookups; insertions/deletions are forbidden

In order to make the "work" phase as fast as possible, i would like to choose a hashing function that has no collisions for the given set of keys (gathered at initialization phase).

I would like to measure how much performance improvement i can get from this trick. So this is going to be an experiment, possibly going into production code.

Does the standard library have facilities for this implementation (e.g. finding how many collisions a given unordered_map has; or changing a hashing function)? Or should i make my own implementation instead?

Upvotes: 3

Views: 1503

Answers (3)

Howard Hinnant
Howard Hinnant

Reputation: 218720

Here is the "collision management" API:

size_type bucket_count() const;
size_type max_bucket_count() const;

size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;

local_iterator       begin(size_type n);
local_iterator       end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;

In a nutshell, bucket_size(n) gives you the number of collisions for the nth bucket. You can look up buckets with a key, and you can iterate over buckets with local_iterator.

For changing a hash function, I would assign/construct a new container, from the old hash function to the new.

Upvotes: 6

Naszta
Naszta

Reputation: 7744

If you have many reads and less writes, you could use vector as a map. It is very common, because lower_bound is more effective than map and use less space from memory:

bool your_less_function( const your_type &a, const your_type &b )
{
  // based on keys
  return ( a < b );
}
...
std::vector<your_type> ordered-vector;

When you add values:

...
// First 100 values
ordered-vector.push_back(value)
...
// Finally. The vector must be sorted before read.
std::sort( ordered-vector.begin(), ordered-vector.end(), your_less_function );

When ask for data:

std::vector<your_type>::iterator iter = std::lower_bound( ordered-vector.begin(), ordered-vector.end(), value, your_less_function );
if ( ( iter == ordered-vector.end() ) || your_less_function( *iter, value ) )
  // you did not find the value
else
  // iter contains the value

Unfortunately it is ordered, but really fast.

Upvotes: 2

amit kumar
amit kumar

Reputation: 21012

The number of collisions depends on the number of buckets. Is it useful for you to use the rehash function to set the number of buckets to 100, as per the boost documentation?

Upvotes: 0

Related Questions