Qt implementation of Perfect Hash as described @ http://www.drdobbs.com/architecture-and-design/generating-perfect-hash-functions/184404506

benchmark.cpp

#include <QtTest/QtTest>
#include <qmath.h>
// #include <QHash>

#include "perfecthash.h"

class PerfectHashBench : public QObject
{
    Q_OBJECT

    PerfectHash<int,int, -1, -1, 10000> hash;
//    QHash<int, int> qhash;

    private slots:
    void initTestCase();
    void searching();
    void searching_data();
};


void PerfectHashBench::initTestCase()
{
    QVector< QPair<int,int> > items;

    for(int i = 0; i < 1000; i++)
    {
        items.push_back({i*i, i});
//        qhash[i*i] = i;
    }

    qDebug() << "Inserting" << items.count() << "items...";

    hash = PerfectHash<int,int, -1, -1, 10000>(items);

    qDebug() << "Inserted" << hash.count() << "items.";
    qDebug() << "Hash capacity" << hash.capacity() << "items.";
    qDebug() << "Hash utilization" << (double)hash.count()/hash.capacity()*100 << "%";

    QCOMPARE(hash.count(),1000);
}

void PerfectHashBench::searching()
{
    QFETCH(int, key);
    QFETCH(int, value);
    QFETCH(bool, exists);

    QBENCHMARK{
        QCOMPARE( hash.contains(key) , exists);
        QCOMPARE( hash.value(key), value );
    }

//    QBENCHMARK{
//        QCOMPARE( qhash.contains(key) , exists);
//        QCOMPARE( qhash.value(key), exists? value : 0);
//    }
}

void PerfectHashBench::searching_data()
{
    QTest::addColumn<int>("key");
    QTest::addColumn<int>("value");
    QTest::addColumn<bool>("exists");

    for(int i = 0; i < 100; i++)
    {
        int s = qSqrt(i);
        bool exists = s*s == i;
        int value = exists? s : -1;
        QTest::newRow(QString::number(i).toLatin1().data()) << i << value << exists;
    }

}

QTEST_MAIN(PerfectHashBench)
#include "benchmark.moc"

perfecthash.h

#ifndef PERFECTHASH_H
#define PERFECTHASH_H

#include <QDebug>
#include <QVector>
#include <QPair>
#include <qmath.h>
#include <utility>
#include <algorithm>
#include <initializer_list>


template <typename K, typename V,
          const K invalid_key, const V invalid_value,
          const int n = 1000> // maximum allowed number of buckets
class PerfectHash {
public:
    PerfectHash():
        m_count(0),
        m_rows(0)
    {
    }

    PerfectHash( std::initializer_list< std::pair<K,V> > data )
    {
        if(!initializeData(data))
        {
            m_count = 0;
            m_rows = 0;
        }
    }

    PerfectHash( const QVector< QPair <K,V> >& data )
    {
        if(!initializeData(data))
        {
            m_count = 0;
            m_rows = 0;
        }
    }

    // How many (key,value) pairs could this list have taken
    inline int capacity() const { return m_data.size(); }

    // How many (key, value) pairs are present in this list
    inline int count() const { return m_count; }

    // Is there a (key,value) pair with this key?
    inline bool contains(K key) const
    {
        const auto d = std::div(key , m_rows);
        if(d.quot >= (int)m_rows)
          return false;

        const int offset = m_rowOffsets[d.quot];
        if(offset < 0)
          return false;

        const unsigned int c = offset + d.rem;
        return c < (unsigned int)m_data.size() && m_data[ c ].first == key;
    }

    // Return the value associated with this key
    // If nothing found, this returns a default value
    inline V value(K key) const
    {
        const auto d = std::div(key, m_rows);
        if(d.quot >= (int)m_rows)
          return invalid_value;

        const int offset = m_rowOffsets[d.quot];
        if(offset < 0)
          return invalid_value;

        const unsigned int c = offset + d.rem;

        if((int)c < m_data.size() && m_data[c].first == key)
          return m_data[c].second;
        return invalid_value;
    }

    void clear()
    {
        m_data.clear();
        m_count = 0;
        m_rows = 0;
    }

    //Overloading value(K key)
    inline V operator[](K key) const { return value(key); }

private:
    typedef QVector< QVector<K> > ScratchPad;
    struct RowInfo { int index, count; };

    bool initializeData(const QVector< QPair<K,V> >& rawData)
    {
        K kMax = std::max_element(rawData.begin(), rawData.end())->first;
        m_rows = qSqrt(kMax) + 1;

        //The 2D array for inserting the keys into
        ScratchPad scratchpad(m_rows, QVector<K>(m_rows, invalid_key) );
        QVector<RowInfo> rowInfo;

        //No row is shifted at all
        for(unsigned int r = 0; r < m_rows; r++)
        {
            m_rowOffsets.push_back(-1);
            rowInfo.push_back({r,0}); // Assume that each row has 0 keys
        }

        //Insert the keys into the Key Array
        for(const auto element : rawData)
        {
            K k = element.first;
            int r = k/m_rows;
            int c = k%m_rows;
            if(scratchpad[r][c] == invalid_key)
            {
                scratchpad[r][c] = k;
                rowInfo[r].count++;
            }
        }

        // Process the keys and populate the hashmap
        return firstFitDescending(rawData, scratchpad, rowInfo);
    }

    bool firstFitDescending( const QVector< QPair<K,V> >& rawData,
                             ScratchPad& scratchPad,
                             QVector<RowInfo> &rowInfo )
    {
        // A temporary large array to hold all the keys being hashed
        QVector<K> keys = QVector<K>(n, invalid_key);

        // 0. Sort the Rows based on the number of elements they contain
        std::sort(rowInfo.begin(), rowInfo.end(),
                  [](const RowInfo& A, const RowInfo& B){ return A.count > B.count; });

        // For each non-empty row:
        for(int r = 0; r < rowInfo.count() && rowInfo[r].count > 0; r++)
        {
            unsigned int row = rowInfo[r].index;
            // 1. Shift the row right until none of its items collide with
            // any of the items in previous rows.
            for(unsigned int offset = 0; offset < n - m_rows - 1; offset++)
            {
                unsigned int y = 0;

                for(y = 0; y < m_rows; y++)
                {
                    if( (keys[offset + y] != invalid_key) && (scratchPad[row][y] != invalid_key) )
                        break;
                }

                if( y == m_rows )
                {
                    // 2. Record the shift amount in m_rowOffsets
                    //qDebug() << row << "--->" << offset << endl;
                    m_rowOffsets[row] = offset;

                    // 3. Copy the keys from this row into the keys already hashed
                    for(unsigned int x = 0; x < m_rows; x++)
                    {
                        if(scratchPad[row][x] != invalid_key)
                        {
                            keys[offset + x] = scratchPad[row][x];
                            //qDebug() << "Keys[" << offset + x << "] = " << keys[offset+x] <<endl;
                        }
                    }

                    //Move on to the next row
                    break;
                }

                if(offset == n - m_rows - 1)
                {
                    qDebug() << "Error::Failed to fit the Row " << row << " in hash table." << endl;
                    return false;
                }
            }
        }

        // Now copy the elements of rawData into their appropriate buckets
        int capacity = 0;
        for(int i = 0; i < n; i++)
            if(keys[i] != invalid_key) capacity = i + 1;


        m_data = QVector< QPair<K,V> >(capacity, { invalid_key, invalid_value} );
        m_count = 0;

        for(unsigned int i = 0; i < (unsigned int)m_data.size(); i++)
        {
            const auto currentKey = keys[i];
            //Bother only if currentKey is a valid key
            if( currentKey == invalid_key) continue;

            for(const auto element : rawData)
            {
                if(element.first == currentKey)
                {
                    //qDebug() << "Bucket " << offset + x << " :: " << element.first << "," << element.second << endl;
                    m_data[i] = element;
                    break;
                }
            }
            //qDebug() << i << "::" << m_data[i].first << "," << m_data[i].second << endl;
            m_count++;
        }

        return true;
    }

    unsigned int m_count; // Total number of keys hashed into m_data
    QVector< QPair<K,V> > m_data; // Actual data

    unsigned int m_rows; // Number of rows in the scratchPad
    QVector<int> m_rowOffsets; // Offset of each row in m_data

};

#endif //PERFECTHASH_H

QPerfectHash.pro

######################################################################
# Automatically generated by qmake (3.0) Sat Jan 24 06:11:57 2015
######################################################################

TEMPLATE = app
TARGET = benchmark
INCLUDEPATH += .
CONFIG += c++11
QT += testlib
QT -= gui quick qml

# Input
HEADERS += perfecthash.h
SOURCES += benchmark.cpp