libgenua
Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
PreshingTable Class Reference

Detailed Description

Integer hash table by Jeff Preshing.

Maps pointer-sized integers to pointer-sized integers, using open addressing with linear probing.

In the m_cells array, key = 0 is reserved to indicate an unused cell. Actual value for key 0 (if any) is stored in m_zeroCell. The hash table automatically doubles in size when it becomes 75% full. The hash table never shrinks in size, even after clear(), unless you explicitly call compact().

This code is in the public domain. https://github.com/preshing/CompareIntegerMaps

See Also
std::map, JudyMap

#include <preshinghashtable.h>

Classes

class  Iterator
 iterate over table More...
 

Public Member Functions

 PreshingTable (size_t initialSize=8)
 preallocate a desired size
 
 PreshingTable (PreshingTable &&t)
 move into another table
 
 ~PreshingTable ()
 deallocate
 
size_t size () const
 number of values presently stored
 
size_t capacity () const
 present container size
 
Cell * lookup (size_t key)
 lookup key
 
const Cell * clookup (size_t key) const
 lookup key
 
Cell * insert (size_t key)
 insert key
 
void erase (Cell *cell)
 erase by cell
 
void erase (size_t key)
 erase by key
 
void clear ()
 clear table
 
void compact ()
 reduce memory footprint
 

Private Member Functions

void repopulate (size_t desiredSize)
 change size
 

Private Attributes

Cell * m_cells
 linear array of cells
 
size_t m_arraySize
 size of array; must be a power of 2
 
size_t m_population
 number of items currently in array
 
Cell m_zeroCell
 the item for key 0
 
bool m_zeroUsed
 whether key 0 is used
 

The documentation for this class was generated from the following files: