hashing template class cuckoohashfamily publicsize_t hashconst anytype xint which constint getnumberoffunctions)void generatenewfunctions)}figure generic hashfamily interface for cuckoo hashing figure provides the class interface for cuckoo hashing we will code variant that will allow an arbitrary number of hash functions (specified by the hashfamily template parameter typewhich uses single array that is addressed by all the hash functions thus our implementation differs from the classic notion of two separately addressable hash tables we can implement the classic version by making relatively minor changes to the codehoweverthe version provided in this section seems to perform better in tests using simple hash functions in figure we specify that the maximum load for the table is if the load factor of the table is about to exceed this limitan automatic table expansion is performed we also define allowed_rehasheswhich specifies how many rehashes we will perform if evictions take too long in theoryallowed_rehashes can be infinitesince we expect only small constant number of rehashes are neededin practicedepending on several factors such as the number of hash functionsthe quality of the hash functionsand the load factorthe rehashes could significantly slow things downand it might be worthwhile to expand the tableeven though this will cost space the data representation for the cuckoo hash table is straightforwardwe store simple arraythe current sizeand the collections of hash functionsrepresented in hashfamily instance we also maintain the number of hash functionseven though that is always obtainable from the hashfamily instance figure shows the constructor and makeempty methodsand these are straightforward figure shows pair of private methods the firstmyhashis used to select the appropriate hash function and then scale it into valid array index the secondfindposconsults all the hash functions to return the index containing item xor - if is not found findpos is then used by contains and remove in figures and respectivelyand we can see that those methods are easy to implement the difficult routine is insertion in figure we can see that the basic plan is to check to see if the item is already presentreturning if so otherwisewe check to see if the table is fully loadedand if sowe expand it finally we call helper routine to do all the dirty work the helper routine for insertion is shown in figure we declare variable rehashes to keep track of how many attempts have been made to rehash in this insertion our insertion routine is mutually recursiveif neededinsert eventually calls rehashwhich eventually calls back into insert thus rehashes is declared in an outer scope for code simplicity