I am trying to make a very fast hash table based set of pointers. It is supposed to be as fast as possible, not conforming to standard C++ at times. This is always marked in the code. Collisions are resolved by linear probing. The maximum size is known at construction time and memory grows by multiples of 2. All memory is pre-allocated. The set should perform only insertions. No other functionality is needed.Here is my code:#ifndef HASH_TABLE_H#define HASH_TABLE_H#include <vector>#include <cstdint>#include <cstring>#include <algorithm>#include range_checking.h // contains Positive<int> a simple range checking utility//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>template <typename TItem>class HashTable{public: //---------------------------------------------------------------------    HashTable (Positive<int> maxSize, Positive<int> probableSize = 32);    void reset(Positive<int> probableSize);    bool insert(const TItem *address);    int size() const;    long nCollisions() const;private: //--------------------------------------------------------------------    typedef std::vector<const TItem*> TArray;    std::vector<TArray> arrays_;    int operatingArray_;    uintptr_t computeIndex(const TItem* address) const;    void expand();    bool performInsertion(const TItem *address);    Real maxLoadFactor_;     int currentArraySize_;     int nItems_;     int maxItems_;    long nCollisions_ = 0;};unsigned fastCeilLog2(unsigned argument);unsigned fastModuloPowerOfTwo(unsigned argument, unsigned powerOfTwo);//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//*****************************************************************************//  Implementations://*****************************************************************************//=============================================================================template <typename TItem>HashTable<TItem>::HashTable(Positive<int> maxSize, Positive<int> probableSize):    operatingArray_(0),    maxLoadFactor_(0.5),    currentArraySize_(1),    nItems_(0),    maxItems_(0){    do    {        currentArraySize_ *= 2;        arrays_.emplace_back(currentArraySize_, nullptr);    }    while (currentArraySize_ < maxSize / maxLoadFactor_);    reset(probableSize);}//=============================================================================//=============================================================================template <typename TItem>void HashTable<TItem>::reset(Positive<int> probableSize){    /// The following line is nonstandard and should be:    /// std::fill(arrays_[operatingArray_].begin(),    ///           arrays_[operatingArray_].end(), nullptr);    std::memset(&(arrays_[operatingArray_][0]),0,                  arrays_[operatingArray_].size()*sizeof(int*));    maxItems_         = probableSize / maxLoadFactor_;    operatingArray_   = fastCeilLog2(maxItems_) - 1;    currentArraySize_ = arrays_[operatingArray_].size();    nItems_           = 0;}//=============================================================================//=============================================================================template <typename TItem>bool HashTable<TItem>::insert(const TItem* address){    if (nItems_ + 1 > maxItems_)    {        expand();        return insert(address);    }    bool inserted = performInsertion(address);    if (inserted)        ++nItems_;    return inserted;}//=============================================================================//=============================================================================template <typename TItem>int HashTable<TItem>::size() const{    return nItems_;}//=============================================================================//=============================================================================template <typename TItem>long HashTable<TItem>::nCollisions() const{    return nCollisions_;}//=============================================================================//=============================================================================template <typename TItem>uintptr_t HashTable<TItem>::computeIndex(const TItem* address) const{    uintptr_t index = reinterpret_cast<uintptr_t>(address);  /// Nonstandard    index >>= 5;                                             /// Ad hoc    index = fastModuloPowerOfTwo(index, currentArraySize_);    return index;}//=============================================================================//=============================================================================template <typename TItem>void HashTable<TItem>::expand(){    TArray& lastArray = arrays_[operatingArray_];    ++operatingArray_;    currentArraySize_ = arrays_[operatingArray_].size();    maxItems_ = maxLoadFactor_ * currentArraySize_;    for (auto i : lastArray)        performInsertion(i);    /// The following line is nonstandard and should be:    /// std::fill(lastArray.begin(), lastArray.end(), nullptr);    std::memset(&lastArray[0], 0, lastArray.size()*sizeof(int*));}//=============================================================================//=============================================================================template <typename TItem>bool HashTable<TItem>::performInsertion(const TItem *address){    uintptr_t index = computeIndex(address);    const TItem* insertionSpot = arrays_[operatingArray_][index];    while (insertionSpot != nullptr)    {        ++nCollisions_;        if (insertionSpot == address)            return false;        ++index;        index = fastModuloPowerOfTwo(index, currentArraySize_);        insertionSpot = arrays_[operatingArray_][index];    }    arrays_[operatingArray_][index] = address;    return true;}//=============================================================================//=============================================================================inline unsigned fastCeilLog2(unsigned argument){    unsigned logarithm = 1;    while (argument >>= 1)        ++logarithm;    return logarithm;}//=============================================================================//=============================================================================inline unsigned fastModuloPowerOfTwo(unsigned argument, unsigned powerOfTwo){    argument &= (powerOfTwo-1);    return argument;}//=============================================================================#endif // HASH_TABLE_HI am having problems with collisions. I made a benchmark that reserves 32 items and feeds data of various sizes and overlaps into the table, letting it grow naturally. Then it is cleared, reserved again and the same data is fed into it again. The times for 10 runs are summed and the same is done with std::unordered_set of gcc 4.8. The ratios and the average number of collisions for my hashtable are presented in this document.I am concerned about:The number of collisions: Should there be so many collisions? Is it normal that to feed 1600 items with 0.3 overlap (30% of the items are duplicates) results in 16 000 collisions?The irregularity in the collision data, For example: 1600 items, 0% overlap => cca 1700 collisions3200 items, 0% overlap => cca 1 700 000 collisionsHow can I improve my hash table?Could you give me general code assesment?Could you explain the strange collision data and the great number of collisions? Is this normal?How can I reduce the number of collisions?I made this hashtable just by some ad-hoc experimentation and reading the Wikipedia article and it is the first time I made a hash table. So I am very inexperienced and humble, welcoming any advice at all.
Fast hash table based set of pointers
c++;performance;hash table
Find it hard to believe that std::fill is slower than std::memeset/// The following line is nonstandard and should be:/// std::fill(arrays_[operatingArray_].begin(),///           arrays_[operatingArray_].end(), nullptr);std::memset(&(arrays_[operatingArray_][0]),0,              arrays_[operatingArray_].size()*sizeof(int*));If you are in debug mode then you may see a difference but with optimizations ON seems unlikely. If there is a difference they you should add that as a comment to explain. Otherwise it is not non standard to use std::memset I would just add a comment on why.This seems perfectly valid to me:uintptr_t index = reinterpret_cast<uintptr_t>(address);The uintptr_t is specifically designed to hold a pointer without loss of data. Using reinterpret_cast<>() is valid to indicate the danger of the conversion. But it is a valid conversion.Again I see nothing unstandard about:/// The following line is nonstandard and should be:/// std::fill(lastArray.begin(), lastArray.end(), nullptr);std::memset(&lastArray[0], 0, lastArray.size()*sizeof(int*));But I would add a comment on why you chose std::memset().No need for the recursive call here:if (nItems_ + 1 > maxItems_){    expand();    return insert(address);}I would just let it fall through. If there is a possibility that expand() does not grow it enough then use a loop rather than recursion. That will make it easier for the compiler to unroll and do other optimizations.Now what I would consider a good hashing function:uintptr_t HashTable<TItem>::computeIndex(const TItem* address) const