This test inserts a number of values with uniform i.i.d. integer keys into a container, then performs a series of finds using find. It measures the average time forfind as a function of the number of values inserted.
(The test was executed with random_int_find_timing_test 200 200 2100)
The test checks the effect of different underlying hash-tables (see Design::Associative Containers::Associative Containers::Hash-Based Containers), range-hashing functions, and trigger policies (see Design::Associative Containers::Hash-Based Containers::Hash Policies and Design::Associative Containers::Hash-Based Containers::Resize Policies).
Figures NCCG, NCCM, and NCCL show the results for the native and collision-chaining types in g++, MSVC++, and local, respectively; Figures NGPG, NGPM, and NGPL show the results for the native and probing types in g++, MSVC++, and local respectively.
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In this setting, the choice of underlying hash-table (see Design::Associative Containers::Hash-Based Containers ) affects performance most, then the range-hashing scheme (See Design::Associative Containers::Hash-Based Containers::Hash Policies ), and, only finally, other policies.
When comparing Figures NCCG and NCCM to NGPG and NGPM , respectively, it is apparent that the probing containers are less efficient than the collision-chaining containers (both std::tr1::unordered_map and stdext::hash_map use collision-chaining) in this case.
( Hash-Based Random-Integer Subscript Insert Timing Test shows a different case, where the situation is reversed; Observations::Hash-Based Container Types discusses some further considerations.)
Within each type of hash-table, the range-hashing scheme affects performance more than other policies; Hash-Based Text find Find Timing Test::Observations discusses this. In Figures NCCG , NCCM , NGPG , and NGPM , it should be noted that std::tr1::unordered_map and stdext::hash_map are hard-wired currently to mod-based and mask-based schemes, respectively.
Observations::Hash-Based Container Types summarizes some observations on hash-based containers; Observations::Hash-Based Containers' Policies summarizes some observations on hash-based containers' policies.