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:

• preshinghashtable.h
• preshinghashtable.cpp