Alex Blekhman wrote:
"Sachin" wrote:
by optimized
i wanted to know if it is faster than any known Searching
algorithms like
1. linear search 2. B-tree etc
In additiona to other answers. Visual C++ provides
`stdext::hash_map' container, that provides lookups in constant
average time.
but...
If your map contains keys that are long and highly differentiated by
prefixes (i.e, they don't all start with only a few prefixes), then
std::map can actually end up being faster than a hash map, as the hash
map requires examining every character of a search string, while the
ordered map's key comparisions will be able to bail out after
examining only a few characters at the start of the key. For the
exact case the OP mentioned (20 characters, millions of records), I
would not expect hash_map to be slower.
The other case where std :: map will outperform a hashed map is when
you use an inappropriate hashing function that results in many hash
collisions.
To make a long story short, both are great containers, both will give
good performance in most cases, which one is best depends on your
application and the only way to know for sure which one is better for
your data is to time both of them with your real data.
-cd
proper hash function. The default hash functions are not always
appropriate, which is why they allow you to provide your own. For example,