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.

See Also
std::map, JudyMap

#include <preshinghashtable.h>


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 ()
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: