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_H
I 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 collisions
3200 items, 0% overlap => cca 1 700 000 collisions
- How 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.