CuckooHashTable.cs

/***
 * Cuckoo Hash Table.
 * 
 * A hash table that implements the Cuckoo Hashing algorithm for resolving keys-collisions. 
 * This is a single-table implementation, the source behind this idea is the work of Mark Allen Weiss, 2014.
 */

usingSystem;
usingSystem.Collections.Generic;

usingDataStructures.Common;
usingDataStructures.Hashing;
usingSystem.Threading.Tasks;

namespaceDataStructures.Dictionaries
{
/// <summary>
/// THE CUCKOO HASH TABLE Data Structure.
/// </summary>
publicclassCuckooHashTable<TKey,TValue>whereTKey:IComparable<TKey>
{
/// <summary>
/// THE CUCKOO HASH TABLE ENTERY
/// </summary>
privateclassCHashEntry<TKey,TValue>whereTKey:IComparable<TKey>
{
publicTKeyKey{get;set;}
publicTValueValue{get;set;}
publicboolIsActive{get;set;}

publicCHashEntry():this(default(TKey),default(TValue),false){}

publicCHashEntry(TKeykey,TValuevalue,boolisActive)
{
Key=key;
Value=value;
IsActive=isActive;
}
}


/// <summary>
/// INSTANCE VARIABLES
/// </summary>
privateconstintDEFAULT_CAPACITY=11;
privateconstdoubleMAX_LOAD_FACTOR=0.45;
privateconstintALLOWED_REHASHES=5;
privateconstintNUMBER_OF_HASH_FUNCTIONS=7;// number of hash functions to use, selected 7 because it's prime. The choice was arbitrary.
internalreadonlyPrimesListPRIMES=PrimesList.Instance;

// Random number generator
privateRandom_randomizer;

privateint_size{get;set;}
privateint_numberOfRehashes{get;set;}
privateCHashEntry<TKey,TValue>[]_collection{get;set;}
privateUniversalHashingFamily_universalHashingFamily{get;set;}
privateEqualityComparer<TKey>_equalityComparer=EqualityComparer<TKey>.Default;

// The C# Maximum Array Length (before encountering overflow)
// Reference: http://referencesource.microsoft.com/#mscorlib/system/array.cs,2d2b551eabe74985
privateconstintMAX_ARRAY_LENGTH=0X7FEFFFFF;


/// <summary>
/// CONSTRUCTOR
/// </summary>
publicCuckooHashTable()
{
_size=0;
_numberOfRehashes=0;
_randomizer=newRandom();
_collection=newCHashEntry<TKey,TValue>[DEFAULT_CAPACITY];
_universalHashingFamily=newUniversalHashingFamily(NUMBER_OF_HASH_FUNCTIONS);
}

/// <summary>
/// Expands the size of internal collection.
/// </summary>
privatevoid_expandCapacity(intminCapacity)
{
intnewCapacity=(_collection.Length==0?DEFAULT_CAPACITY:_collection.Length*2);

// Handle overflow
if(newCapacity>=MAX_ARRAY_LENGTH)
newCapacity=MAX_ARRAY_LENGTH;
elseif(newCapacity<minCapacity)
newCapacity=minCapacity;

_rehash(Convert.ToInt32(newCapacity));
}

/// <summary>
/// Contracts the size of internal collection to half.
/// </summary>
privatevoid_contractCapacity()
{
_rehash(_size/2);
}

/// <summary>
/// Rehashes the internal internal collection.
/// Table size stays the same, but generates new hash functions.
/// </summary>
privatevoid_rehash()
{
_universalHashingFamily.GenerateNewFunctions();
_rehash(_collection.Length);
}

/// <summary>
/// Rehashes the internal collection to a new size.
/// New hash table size, but the hash functions stay the same.
/// </summary>
privatevoid_rehash(intnewCapacity)
{
intprimeCapacity=PRIMES.GetNextPrime(newCapacity);

varoldSize=_size;
varoldCollection=this._collection;

try
{
this._collection=newCHashEntry<TKey,TValue>[newCapacity];

// Reset size
_size=0;

for(inti=0;i<oldCollection.Length;++i)
{
if(oldCollection[i]!=null&&oldCollection[i].IsActive==true)
{
_insertHelper(oldCollection[i].Key,oldCollection[i].Value);
}
}
}
catch(OutOfMemoryExceptionex)
{
// In case a memory overflow happens, return the data to it's old state
// ... then throw the exception.
_collection=oldCollection;
_size=oldSize;

throwex.InnerException;
}
}

/// <summary>
/// Hashes a key, using the specified hash function number which belongs to the internal hash functions family.
/// </summary>
privateint_cuckooHash(TKeykey,intwhichHashFunction)
{
if(whichHashFunction<=0||whichHashFunction>_universalHashingFamily.NumberOfFunctions)
thrownewArgumentOutOfRangeException("Which Hash Function parameter must be betwwen 1 and "+NUMBER_OF_HASH_FUNCTIONS+".");

inthashCode=Math.Abs(_universalHashingFamily.UniversalHash(_equalityComparer.GetHashCode(key),whichHashFunction));

returnhashCode%_collection.Length;
}

/// <summary>
/// Checks whether there is an entry at the specified position and that the entry is active.
/// </summary>
privatebool_isActive(intindex)
{
if(index<0||index>_collection.Length)
thrownewIndexOutOfRangeException();

return(_collection[index]!=null&&_collection[index].IsActive==true);
}

/// <summary>
/// Returns the array position (index) of the specified key.
/// </summary>
privateint_findPosition(TKeykey)
{
// The hash functions numbers are indexed from 1 not zero
for(inti=1;i<=NUMBER_OF_HASH_FUNCTIONS;++i)
{
intindex=_cuckooHash(key,i);

if(_isActive(index)&&_collection[index].Key.IsEqualTo(key))
returnindex;
}

return-1;
}

/// <summary>
/// Inserts a key-value pair into hash table.
/// </summary>
privatevoid_insertHelper(TKeykey,TValuevalue)
{
intCOUNT_LIMIT=100;
varnewEntry=newCHashEntry<TKey,TValue>(key,value,isActive:true);

while(true)
{
intposition,lastPosition=-1;

for(intcount=0;count<COUNT_LIMIT;count++)
{
// The hash functions numbers are indexed from 1 not zero
for(inti=1;i<=NUMBER_OF_HASH_FUNCTIONS;i++)
{
position=_cuckooHash(key,i);

if(!_isActive(position))
{
_collection[position]=newEntry;

// Increment size
++_size;

return;
}
}

// Eviction strategy:
// No available spot was found. Choose a random one.
intj=0;
do
{
position=_cuckooHash(key,_randomizer.Next(1,NUMBER_OF_HASH_FUNCTIONS));
}while(position==lastPosition&&j++<NUMBER_OF_HASH_FUNCTIONS);

// SWAP ENTRY
lastPosition=position;

vartemp=_collection[position];
_collection[position]=newEntry;
newEntry=temp;

}//end-for

if(++_numberOfRehashes>ALLOWED_REHASHES)
{
// Expand the table.
_expandCapacity(_collection.Length+1);

// Reset number of rehashes.
_numberOfRehashes=0;
}
else
{
// Rehash the table with the same current size.
_rehash();
}
}//end-while
}


/// <summary>
/// Returns number of items in hash table.
/// </summary>
/// <returns></returns>
publicintCount()
{
return_size;
}

/// <summary>
/// Returns true if hash table is empty; otherwise, false.
/// </summary>
publicboolIsEmpty()
{
return(_size==0);
}

/// <summary>
/// Returns the value of the specified key, if exists; otherwise, raises an exception.
/// </summary>
publicTValuethis[TKeykey]
{
get
{
intposition=_findPosition(key);

if(position!=-1)
return_collection[position].Value;

thrownewKeyNotFoundException();
}
set
{
if(ContainsKey(key)==true)
Update(key,value);

thrownewKeyNotFoundException();
}
}

/// <summary>
/// Checks if a key exists in the hash table.
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
publicboolContainsKey(TKeykey)
{
return(_findPosition(key)!=-1);
}

/// <summary>
/// Insert key-value pair into hash table.
/// </summary>
publicvoidAdd(TKeykey,TValuevalue)
{
if(ContainsKey(key))
thrownewException("Key already exists in the hash table.");

if(_size>=_collection.Length*MAX_LOAD_FACTOR)
_expandCapacity(_collection.Length+1);

_insertHelper(key,value);
}

/// <summary>
/// Updates a key-value pair with a new value.
/// </summary>
publicvoidUpdate(TKeykey,TValuevalue)
{
intposition=_findPosition(key);

if(position==-1)
thrownewKeyNotFoundException();

_collection[position].Value=value;
}

/// <summary>
/// Remove the key-value pair specified by the given key.
/// </summary>
publicboolRemove(TKeykey)
{
intcurrentPosition=_findPosition(key);

if(!_isActive(currentPosition))
returnfalse;

// Mark the entry as not active
_collection[currentPosition].IsActive=false;

// Decrease the size
--_size;

returntrue;
}

/// <summary>
/// Clears this hash table.
/// </summary>
publicvoidClear()
{
this._size=0;

Parallel.ForEach(_collection,
(item)=>
{
if(item!=null&&item.IsActive==true)
{
item.IsActive=false;
}
});
}
}

}