unordered_map code for http://stackoverflow.com/questions/19499719/some-hashtable-unordered-map-questions

Ouput

Map without reserve

        size: 0
bucket_count: 23
 load_factor: 0

Allocation count: 0

        size: 0
bucket_count: 23
 load_factor: 0

Reallocation:
        size: 23
bucket_count: 53
 load_factor: 0.433962

Reallocation:
        size: 53
bucket_count: 109
 load_factor: 0.486239

Reallocation:
        size: 109
bucket_count: 227
 load_factor: 0.480176

Reallocation:
        size: 227
bucket_count: 467
 load_factor: 0.486081

Reallocation:
        size: 467
bucket_count: 953
 load_factor: 0.490031

Reallocation:
        size: 953
bucket_count: 2029
 load_factor: 0.469689

Reallocation:
        size: 2029
bucket_count: 4349
 load_factor: 0.466544

Reallocation:
        size: 4349
bucket_count: 8783
 load_factor: 0.495161

Reallocation:
        size: 8783
bucket_count: 17749
 load_factor: 0.494845

Reallocation:
        size: 17749
bucket_count: 35933
 load_factor: 0.493947

Reallocation:
        size: 35933
bucket_count: 72817
 load_factor: 0.49347

Reallocation:
        size: 72817
bucket_count: 147793
 load_factor: 0.492696

Reallocation:
        size: 147793
bucket_count: 299951
 load_factor: 0.492724

Reallocation:
        size: 299951
bucket_count: 608903
 load_factor: 0.492609

Reallocation:
        size: 608903
bucket_count: 1236397
 load_factor: 0.492482

Allocation count: 1000015

        size: 1000000
bucket_count: 1236397
 load_factor: 0.808802

0: 550454
1: 445645
2: 180174
3: 48593
4: 9708
5: 1568
6: 231
7: 22
8: 2
Map with reserve

        size: 0
bucket_count: 23
 load_factor: 0

Allocation count: 1

        size: 0
bucket_count: 2144977
 load_factor: 0

Allocation count: 1000000

        size: 1000000
bucket_count: 2144977
 load_factor: 0.466205

0: 1346008
1: 626748
2: 146625
3: 22663
4: 2669
5: 248
6: 15
7: 1

unordered_map.cpp

#include <unordered_map>
#include <string>
#include <iostream>
#include <map>
#include <vector>

#include <stdlib.h>

using namespace std;

size_t allocation_count = 0;

void *operator new(size_t size)
{
    ++allocation_count;
    return malloc(size);
}

void *operator new[](size_t size)
{
    ++allocation_count;
    return malloc(size);
}

void operator delete(void *p)
{
    if (p != nullptr)
        free(p);
}

void operator delete[](void *p)
{
    if (p != nullptr)
        free(p);
}

class CountAllocations
{
public:
    CountAllocations()
    {
        allocation_count = 0;
    }

    ~CountAllocations()
    {
        cout << "Allocation count: " << allocation_count << "\n\n";
    }
};

int random(int min, int max)
{
    return rand() % (max - min + 1) + min;
}

string random_string(size_t length)
{
    static string chars{"_0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"};

    string s(length, ' ');
    for (auto &c: s)
        c = chars[random(0, chars.size() - 1)];

    return s;
}

void print_map_info(unordered_map<string, int> const &m)
{
    cout << "        size: " << m.size() << '\n'
         << "bucket_count: " << m.bucket_count() << '\n'
         << " load_factor: " << m.load_factor() << "\n\n";
}

void populate_map(vector<string> const &keys, size_t reserve)
{
    unordered_map<string, int> m;

    print_map_info(m);

    {
        CountAllocations c;

        if (reserve > 0)
            m.reserve(reserve);
    }

    print_map_info(m);

    {
        CountAllocations c;

        auto bucket_count = m.bucket_count();
        for (int i = 0; i < keys.size(); ++i)
        {
            m[keys[i]] = i;
            if (m.bucket_count() != bucket_count)
            {
                bucket_count = m.bucket_count();
                cout << "Reallocation:\n";
                print_map_info(m);
            }
        }
    }

    print_map_info(m);

    map<size_t, size_t> d;
    for (size_t i = 0; i < m.bucket_count(); ++i)
        ++d[m.bucket_size(i)];

    for (auto i: d)
        cout << i.first << ": " << i.second << '\n';
}

int main(int argc, char const *argv[])
{
    size_t const N = 1 * 1000 * 1000;

    srand(time(nullptr));

    vector<string> keys(N);
    for (auto &i: keys)
        i = random_string(random(25, 50));

    cout << "Map without reserve\n\n";
    populate_map(keys, 0);

    cout << "Map with reserve\n\n";
    populate_map(keys, N);

    return 0;
}