hash map for small number of items

Question

I have a scenario where I need 0-10000 objects that are clearly associated with the numbers of 0-10000. These objects should be stored efficiently and have a fast lookup time. However, some container that manages them would be rather sparsely filled.

For example, I might have 100 objects with the corresponding associated numbers of 0-99 and some other 150 objects with the corresponding associated numbers of 650-799.

My first thought here would be some hash map: The hash functions is perfectly easy to calculate. A bare vector would need a binary search for finding elements, which seems slower than a table lookup. I could also use an array with pointers, but I would have the pointer overhead.

Now, if I would like to use a hashmap, which one? I have recently read that unorderd_map would have quite some overhead. But another requirement here is that the map should also be memory efficient.

So I am wondering which is the best container for my purpose. I would like to use some std container or a boost container but am also open to other third-party containers if they are available under LGPL or other free closed-source and commercially usable licenses.

The requirements again:

• I need an (associative) container that maps a number (int) against an object
• lookup time should be as fast as possible
• the container will have up to 10000 elements, so the container should also be performance- and memory-efficient for a small number of entries
• (added after reading comments): the container should be fast to copy. The container is used in some other class, lets call it HoldingClass, which I have thousands of instances of. All of those instances are copied from time to time, which should be as fast as possible. That's also where the memory overhead should be low because the copies are stored in my application
• (added after reading comments): inserting and removing from the container apart from copying the entire container is infrequent and not performance-critical

So, what seems to be the best possible container for this specific case?

Answer 1

boost::flat_map is an associative container that is basicly implemented using a vector. This makes it cache-friendly (node-based implementation is the thing that decreases performance of std::unordered_map).

But you should probably measure both flat_map and unordered_map on some actual data to see which is more performant.

Answer 2

I don't know where you read that a std::unordered_map would be "inefficient" for this use case, but in the case where there are zero collisions on indices as you describe, it's very hard to do better than a std::unordered_map. In particular, since you know the structure of the indices well, you want to take a look at std::unordered_map::reserve, which permits you to decide how many buckets the hash table should use in advance of putting items into the unordered_map.

If you call std::unordered_map::reserve( 10001 ) on the unordered_map prior to the first insertion, I would expect all lookup and insertion times on the unordered_map to be O(1). You could call std::unordered_map::reserve with a lower number to trade off insertion complexity for memory size (and hence time to copy).

However, I've gotta say that this question smells strongly of premature optimization. How do you know this data structure must be optimized? Do you care more about memory or CPU? How much difference does this choice make on actual program performance? Have you benchmarked a trivial unordered_map or vector implementation? If you're dealing with <10000 items in any bucket or red-black container, nearly all operations on that container will be reasonably fast.

And while we're at it: why not just use a simple C-style array of 10000 pointers to your objects? That's going to be only 78 KB in size, even on a 64-bit machine, and you can't beat it for speed.

There's no substitute for understanding your own data and understanding the underlying algorithms in the STL. In particular, don't try to substitute the advice of experts who aren't speaking directly to your use case, don't optimize prematurely, and don't be afraid of digging into the STL internals.

Answer 3

What comes into my mind is that if you have same object for 0-99 index range - may be some sort of hashing function and then associative container. For example

int readdress( int index )
{
    if( index < 100 ) return 0;
    ...
} 

and then map to map 0 index to actual object.

However - I suspect that function readress cannot be determined as a function (address range changes all the time)

What I've could propose - is one custom class which I have made once upon a time for managing index ranges - however - that class has some limitations - I only need to specify whether given index is 'free' or 'allocated' type - but may be type could be replaced with some sort of index and them mapped to object itself (so replace char type with your own type pointer).

I suspect that my class might not be best alternative, so please don't be to rough on conclusion, this might be useful by someone else then.

FreeSpace.h:

#pragma once
#include <vector>
using std::vector;

typedef __int64 int64;

typedef struct Slice_
{
    Slice_( char t, int64 p, int64 s ) : type(t), pos(p), size(s) { }

    int64 size;
    int64 pos;
    char  type;        //'f' - for free, 'a' - for allocated.
}Slice;


class FreeSpace
{
public:
    FreeSpace();

    void specifySlice(char type, int64 pos, int64 size);
    void _specifySlice(char type, int64& pos, int64& size, int& i);
    int64 getTotalSlicesSize( char type );
    void printMap(void);
    void Clear(void);

    void RunTest(const char* name, Slice* ptests, int nTests);
    void CheckMap(const char* name, Slice* ptests, int nTests, int* testCounters );
    bool RunSelfTest(void);

    vector<Slice> slices;
    int64 fileSize;
    int64 lastAllocEndPos;
    bool bDoDebug;
}; //class FreeSpace

FreeSpace.cpp:

#include <afx.h>
#include <afxstr.h>                 //CString
#include <Windows.h>
#include "FreeSpace.h"
#include <assert.h>



FreeSpace::FreeSpace() :
    bDoDebug ( false )
{

}


void FreeSpace::specifySlice( char type, int64 ipos, int64 isize )
{
    Slice* nextSlice;
    Slice* prevSlice;
    int i;

    if( bDoDebug )
        printf("- %s storage from pos %lld, by size %lld\n", (type == 'f') ? "Freeing" : "Allocating", ipos, isize);

    _specifySlice(type, ipos, isize, i);

    ipos = slices[i].pos;
    isize = slices[i].size;
    assert( type == slices[i].type );

    // Checks if slices can be recombined.
    if( i + 1 != slices.size() )    nextSlice = &slices[i+1];
    else                            nextSlice = 0;

    if( i != 0 )    prevSlice = &slices[i-1];
    else            prevSlice = 0;

    // Can we recombine with previous allocation
    if( prevSlice != 0 && prevSlice->pos + prevSlice->size == ipos && prevSlice->type == type )
    {
        // Can combine with previous allocation.
        slices.erase(slices.begin() + i);
        prevSlice->size += isize;
        i--;
    }

    // ---[# 1 #][# 2 #]-------
    // Can we recombine with next allocation
    if( nextSlice != 0 && nextSlice->pos == ipos + isize && nextSlice->type == type )
    {
        // Can combine with next allocation.
        slices[i].size += nextSlice->size;
        slices.erase(slices.begin() + i + 1);
    }
}


void FreeSpace::_specifySlice( char type, int64& ipos, int64& isize, int& i )
{
    int64 last = ipos + isize;
    Slice* nextSlice;
    Slice* prevSlice;

    for( i = 0; i < slices.size(); i++)
    {
        Slice& slice = slices[i];

        if( i + 1 != slices.size() )    nextSlice = &slices[i+1];
        else                            nextSlice = 0;

        if( i != 0 )    prevSlice = &slices[i-1];
        else            prevSlice = 0;


        // ---[######]----------------
        //    ^------^
        // Our allocation starts from same place as current allocation
        if( ipos == slice.pos )
        {
            // Our allocation is the same size.
            if( isize == slice.size )
            {
                if( type == slice.type )    // Nothing changed                                              test1
                    return;

                // Type changed.
                slice.type = type;                                                                      //  test1
                return;
            }

            // ---[######]----------------
            //    ^----------^
            if( last > slice.pos + slice.size )
            {
                slices.erase(slices.begin() + i );  // Covered by our allocation -                          test2
                i--;
                continue;
            }

            // ---[##############]--------
            //    ^----------^
            if( type == slice.type )
                return;                                                                                 //  test3

            slice.size = slice.pos + slice.size - last;                                                 //  test3
            slice.pos = last;
            break;  // Insert our slice
        }

        // ----------------------[#######]----
        //        ^----------^
        // Our allocation comes before this allocation
        if( last <= slice.pos )  // And will not reach this allocation.
        {
            // ------------------[#######]----
            //        ^----------^
            if( last == slice.pos )
                break;                                                                                  //  test13

            // ------------------[#######]----                                                              test5
            //        ^------^
            if( slice.pos > last )
                break;                                                                                  //  test16
        }

        // ---------------[#######]----
        //        ^----------^
        // Our allocation comes before this allocation
        if( ipos < slice.pos )
        {
            // ---------------[#######]----
            //        ^----------^
            if( last < slice.pos + slice.size )
            {
                if( type != slice.type )
                {
                    // Shrink current allocation.                                                           test7
                    slice.size = slice.pos + slice.size - last;
                    slice.pos = last;
                    break;  // Insert our slice
                } else {
                    // Glow current allocation.                                                             test8
                    slice.size = slice.pos + slice.size - last + isize;
                    slice.pos = ipos;
                    return;
                } //if-else
            } //if

            // ---------------[#######]----
            //        ^---------------^
            if( last >= slice.pos + slice.size )
            {
                // ---------------[#######]----
                //        ^---------------^
                if( last == slice.pos + slice.size )
                {
                    slices.erase( slices.begin() + i ); // Covered by our allocation                    -   test6
                    break;  // Insert our slice
                }

                // ---------------[#######]----                                                         -   test9, test10
                //        ^------------------^
                slices.erase( slices.begin() + i ); // Covered by our allocation.
                i--;
                continue;
            } //if
        } //if


        // ---[######]----------------
        //           ^----^
        // Our allocation passed completely previous allocation
        if( ipos >= slice.pos + slice.size )
            // Slice is not affected by our allocation, continue search next slice.
            continue;                                                                                   //  test1

        // ---[#######]--------------------
        //        ^----------^
        // Our allocation passed partially previous allocation
        if( ipos > slice.pos )
        {
            // ---[############]-----------
            //        ^--------^
            // Our allocation ends with current allocation in same place
            if( last == slice.pos + slice.size )
            {
                if( type == slice.type )
                    return;     // Nothing changed.                                                         test12

                slice.size = ipos - slice.pos;                                                          //  test4
                i++;
                break;  // Insert our slice
            } //if

            // ---[############]-----------
            //        ^-----^
            // Our allocation is completely within current allocation
            if( last < slice.pos + slice.size )
            {
                if( type == slice.type )
                    return;     // Same kind, nothing new.                                              -   test11

                // We have some chopped one slice into two                                              -   test1
                slices.insert(slices.begin() + i, Slice(slice.type,slice.pos, ipos - slice.pos ));
                i++;
                Slice& slice = slices[i];
                slice.size = slice.pos + slice.size - last;
                slice.pos = last;
                break;  // Insert our slice
            } //if


            // ---[############]-----------
            //        ^---------------^
            // Our allocation goes beyond current allocation
            if( type == slice.type )
            {
                isize += (ipos - slice.pos);                                                            //  test7
                ipos = slice.pos;               // Will recombine our slice into bigger slice.
                slices.erase(slices.begin() + i);
                i--;
                continue;
            }

            // Different type.
            slice.size = (ipos - slice.pos);    // Make current slice smaller one, continue scan            test6
            continue;
        }
    } //for

    // Simply add slice at that area range.
    slices.insert( slices.begin() + i, Slice(type, ipos, isize) );
} //addSlice


int64 FreeSpace::getTotalSlicesSize( char type )
{
    int64 total = 0;

    for( int i = 0; i < slices.size(); i++)
    {
        Slice& slice = slices[i];
        if( slice.type == type )
            total += slice.size;
    }

    return total;
}


void FreeSpace::printMap(void)
{
    int64 totsize = 0;
    printf("Type   Start addr   End addr     Size\n");

    for( int i = 0; i < slices.size(); i++)
    {
        Slice& slice = slices[i];

        totsize += slice.size;

        printf("%c      %08lld     %08lld     %08lld", slice.type, slice.pos, slice.pos + slice.size - 1, slice.size);

        if( i+1 == slices.size() )
            printf("    (%lld)", totsize );

        printf("\n");
    }

}

void FreeSpace::Clear(void)
{
    slices.clear();
}

void FreeSpace::RunTest(const char* name, Slice* ptests, int nTests)
{
    Clear();

    if( bDoDebug )
        printf("****************** %s ******************\n", name );

    for( int i = 0 ; i < nTests; i++ )
    {
        specifySlice(ptests[i].type, ptests[i].pos, ptests[i].size);
        if( bDoDebug )
            printMap();
    }
}

void FreeSpace::CheckMap(const char* name, Slice* ptests, int nTests, int* testCounters )
{
    bool bPassed = true;

    if( slices.size() != nTests )
        bPassed = false;
    else
        for( int i = 0 ; i < nTests; i++ )
        {
            if( 
                ptests[i].pos != slices[i].pos ||
                ptests[i].size != slices[i].size ||
                ptests[i].type != slices[i].type )
            {
                bPassed = false;
                break;
            }
        }

    testCounters[ bPassed ? 0: 1 ]++;

    if( bPassed ) 
        return;

    CStringA found;
    CStringA expected;

    for( int i = 0 ; i < slices.size(); i++ )
    {
        found.AppendFormat("Slice('%c', %lld, %lld)", slices[i].type, slices[i].pos, slices[i].size );

        if( i+1 != slices.size() )
            found += ",";
    }

    for( int i = 0 ; i < nTests; i++ )
    {
        expected.AppendFormat("Slice('%c', %lld, %lld)", ptests[i].type, ptests[i].pos, ptests[i].size );

        if( i+1 != slices.size() )
            expected += ",";
    }

    if( bDoDebug )
    {
        printf("Test '%s' failed - expected:\n", name);
        printf("     %s\n", expected.GetBuffer() );
        printf("found:\n" );
        printf("     %s\n", found.GetBuffer() );
    }
}


#define RUNTEST( testid, ... ) \
    Slice testid[] = {  ##__VA_ARGS__ }; \
    RunTest( #testid, testid, sizeof(testid) / sizeof(testid[0]) );

#define CHECKTEST( testid, ... ) \
    Slice chk##testid[] = {  ##__VA_ARGS__ }; \
    CheckMap( #testid, chk##testid, sizeof(chk##testid) / sizeof(chk##testid[0]), testCounters );


//
//  Runs class self test, returns false if fails.
//
bool FreeSpace::RunSelfTest(void)
{
    int nTestPassed = 0;
    int testCounters[3] = { 0, 0, 0 };
/*
    Slice test1[] = {
        Slice('f', 0, 10000),
        Slice('a', 0, 10000),
        Slice('f', 900, 100)
    };
    RunTest( "test1", test1, sizeof(test1) / sizeof(test1[0]) );
*/

    RUNTEST( test1, Slice('f', 0, 10000), Slice('a', 1000, 1000),   Slice('a', 1000, 1000), Slice('f', 1000, 1000) );
    CHECKTEST(test1, Slice('f', 0, 10000));

    RUNTEST( test2, Slice('f', 0, 10000), Slice('a', 1000, 1000),   Slice('f', 1000, 2000) );
    CHECKTEST(test2, Slice('f', 0, 10000));

    RUNTEST( test3, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 1000, 100),   Slice('f', 1000, 500) );
    CHECKTEST( test3, Slice('f', 0, 1500),  Slice('a', 1500, 500),   Slice('f', 2000, 8000) );

    RUNTEST( test4, Slice('f', 0, 10000), Slice('a', 1000, 1000),   Slice('a', 500, 500) );
    CHECKTEST(test4, Slice('f', 0, 500),Slice('a', 500, 1500),Slice('f', 2000, 8000));

    RUNTEST( test5, Slice('f', 0, 10000), Slice('a', 1000, 1000),   Slice('a', 500, 100) );
    CHECKTEST(test5, Slice('f', 0, 500),Slice('a', 500, 100),Slice('f', 600, 400),Slice('a', 1000, 1000),Slice('f', 2000, 8000) );

    RUNTEST( test6, Slice('f', 0, 10000), Slice('a', 1000, 1000),   Slice('a', 500, 1500) );
    CHECKTEST(test6, Slice('f', 0, 500),Slice('a', 500, 1500),Slice('f', 2000, 8000));

    RUNTEST( test7, Slice('f', 0, 10000), Slice('a', 1000, 2000),   Slice('f', 500, 1000) );
    CHECKTEST(test7, Slice('f', 0, 1500),Slice('a', 1500, 1500),Slice('f', 3000, 7000) );

    RUNTEST( test8, Slice('f', 0, 10000), Slice('a', 1000, 2000),   Slice('a', 500, 1000) );
    CHECKTEST(test8, Slice('f', 0, 500),Slice('a', 500, 2500),Slice('f', 3000, 7000) );

    RUNTEST( test9, Slice('f', 0, 10000), Slice('a', 1000, 2000),   Slice('a', 500, 4000) );
    CHECKTEST(test9, Slice('f', 0, 500),Slice('a', 500, 4000),Slice('f', 4500, 5500) );

    RUNTEST( test10, Slice('f', 0, 10000), Slice('a', 1000, 2000),   Slice('f', 500, 4000) );
    CHECKTEST(test10, Slice('f', 0, 10000) );

    RUNTEST( test11, Slice('f', 0, 10000), Slice('f', 1000, 1000) );
    CHECKTEST(test11, Slice('f', 0, 10000) );

    RUNTEST( test12, Slice('f', 0, 10000), Slice('f', 9000, 1000) );
    CHECKTEST(test12, Slice('f', 0, 10000) );

    RUNTEST( test13, Slice('f', 1000, 1000), Slice('f', 500, 500) );
    CHECKTEST(test13, Slice('f', 500, 1500) );

    RUNTEST( test14, Slice('f', 1000, 1000), Slice('a', 500, 500) );
    CHECKTEST(test14, Slice('a', 500, 500),Slice('f', 1000, 1000) );

    RUNTEST( test15, Slice('f', 1000, 1000), Slice('f', 100, 100) );
    CHECKTEST(test15, Slice('f', 100, 100),Slice('f', 1000, 1000) );

    RUNTEST( test16, Slice('f', 1000, 1000), Slice('a', 100, 100) );
    CHECKTEST(test16, Slice('a', 100, 100),Slice('f', 1000, 1000) );


    if( bDoDebug )
    {
        if( testCounters[1] == 0 )
            printf("\n     Success: All %d tests passed\n\n", testCounters[0] );
        else
            printf("\n     %d test(s) passed, %d test(s) FAILED\n\n", testCounters[0], testCounters[1] );
    }

    return testCounters[1] == 0;
} //RunSelfTest

This class however has dependency on MFC, it can be cut off if necessary. (E.g. replace CStringA with std::string.

This class will most probably has lowest memory consumption, since it operates with index ranges.

What is most probably missing here is mapping from index to actual object ( or type in my case ) - but that function can be easily made by for loop on slices. Somehow like this:

int indexRemain = index;

FreeSpace& freespace = ...;
for( size_t i = 0; i < freespace.slices.size(); i++ )
{
    if( freespace.slices[i].size > indexRemain )
        return freespace.slices[i].type;

    indexRemain -= freespace.slices[i].size;
}

Answer 4

A sketch of two vectors representing the indices and values:

#include <algorithm>
#include <vector>

template <typename KeyType, typename ValueType>
class vector_map
{
    private:
    typedef std::vector<KeyType> index_vector;
    typedef std::vector<ValueType> value_vector;

    public:
    typedef KeyType key_type;
    typedef ValueType value_type;
    typedef typename value_vector::size_type size_type;
    typedef typename value_vector::iterator iterator;
    typedef typename value_vector::const_iterator const_iterator;

    vector_map() {}
    vector_map(size_type capacity)
    {
        indices.reserve(capacity);
        values.reserve(capacity);
    }

    iterator begin() { return values.begin(); }
    iterator end() { return values.end(); }
    iterator insert(const key_type key, const value_type& value) {
        iterator pos = std::lower_bound(indices.begin(), indices.end(), key);
        size_type i = pos - indices.begin();
        indices.insert(pos, key);
        return values.insert(values.begin() + i, value);
    }

    iterator erase(const key_type key) {
        iterator pos = std::lower_bound(indices.begin(), indices.end(), key);
        if(pos != indices.end() && ! (*pos < key)) {
            size_type i = pos - indices.begin();
            indices.erase(pos);
            return values.erase(values.begin() + i);
        }
        return values.end();
    }

    iterator erase(const_iterator position) {
        if(position == end())
            return end();
        else {
            size_type i = position - values.begin();
            indices.erase(indices.begin() + i);
            return values.erase(values.begin() + i);
        }
    }

    iterator find(const key_type key) {
        iterator pos = std::lower_bound(indices.begin(), indices.end(), key);
        if(pos != indices.end() && ! (*pos < key)) {
            size_type i = pos - indices.begin();
            return values.begin() + i;
        }
        return values.end();
    }

    private:
    index_vector indices;
    value_vector values;
};

You might consider a std::unordered_map with a custom allocator, too. Anyway, you should measure (profile) different solutions and choose accordingly.

Answer 5

std::map<int, MyClass> should be used instead of std::unordered_map<int, MyClass>.

Rationale:

• The lookup complexity for map is 

Logarithmic in size

http://www.cplusplus.com/reference/map/map/at/

• The lookup complexity for unordered map is 

Average case: constant. Worst case: linear in container size

http://www.cplusplus.com/reference/unordered_map/unordered_map/at/