map::insert

вот такой код

Код (Text):

1. #include <Windows.h>
2. #include <hash_map>
3.  
4. int main()
5. {
6.     stdext::hash_map<size_t, size_t>    hm;
7.  
8.     for (int i = 0; i < 1024; ++ i)
9.     {
10.         hm.insert(stdext::hash_map<size_t, size_t>::value_type(my_rand(), i));
11.     }
12. }

даёт 330 коллизий. my_rand() - возвращает рандомное 32 битное число. на 1000 элементов 300 коллизий!

 

Коллизии вообще ни при чем, нужно смотреть среднюю длину списка. hash_map к тому же меняет свой размер при таком добавлении. А вдруг там получилось 400 списков из одного элемента и 300 списков из двух элементов, вот вам и 300 коллизий. А средняя длина списка ~1.5

P.S. Вот такой код налабал у себя:

Код (Text):

1.     stdext::hash_map<size_t, size_t> hm;
2.     for (int i = 0; i < 1024; ++i)
3.     {
4.       rnd_next();
5.       hm.insert(stdext::hash_map<size_t, size_t>::value_type(rnd_seed, i));
6.     }
7.     printf( "Buckets count: %d\r\n", hm.bucket_count() );
8.     int k = 0;
9.     int n = 0;
10.     for (int i = 0; i < hm.bucket_count(); ++i )
11.     {
12.       if (hm.bucket_size( i ) > 0)
13.       {
14.         n += hm.bucket_size( i );
15.         ++k;
16.       }
17.       printf( "Bucket %d: %d elements\r\n", i, hm.bucket_size( i ) );
18.     }
19.     printf( "Average list length: %.3f", double( n ) / k );

Получилось на 1024 элемента он сделал 256 ячеек таблицы, средняя длина списка - чуть больше 4.

P.P.S. Хотя если в самом начале добавить вызов

Код (Text):

1. hm.rehash(1024);

то средняя длина списков уменьшается до 1.5. И таблица не будет лишний раз перестраиваться при добавлении элементов.

 

в данной задаче хашмапа всё-равно не подходит, т.к. элементы должны быть отсортированы. можно, конечно, что-то напрядумывать с сортированным массивом вместо списка.. хз..