LPHashTable: a HashTable implementation that uses linear probing as a collision resolution strategy. More...

#include "lphashtable.h"

Inheritance diagram for LPHashTable< K, V >:

Collaboration diagram for LPHashTable< K, V >:

Public Member Functions
	LPHashTable (size_t tsize)
	Constructs a LPHashTable of the given size. More...

virtual	~LPHashTable ()
	Destructor for the LPHashTable. More...

const LPHashTable< K, V > &	operator= (const LPHashTable< K, V > &rhs)
	Assignment operator. More...

	LPHashTable (const LPHashTable< K, V > &other)
	Copy constructor. More...

virtual void	insert (const K &key, const V &value)
	Inserts the given key, value pair into the HashTable. More...

virtual void	remove (const K &key)
	Removes the given key (and its associated data) from the HashTable. More...

virtual V	find (const K &key) const
	Finds the value associated with a given key. More...

virtual bool	keyExists (const K &key) const
	Determines if the given key exists in the HashTable. More...

virtual void	clear ()
	Empties the HashTable (that is, all keys and values are removed). More...

virtual V &	operator[] (const K &key)
	Access operator: Returns a reference to a value in the HashTable, so that it may be modified. More...

iterator	begin () const
	Returns an iterator to the beginning of the HashTable. More...

iterator	end () const
	Returns an iterator to the end of the HashTable. More...

Public Member Functions inherited from HashTable< K, V >
virtual	~HashTable ()
	Destructor for a HashTable: made virtual to allow overloading in derived classes. More...

virtual bool	isEmpty () const
	Determines if the HashTable is empty. More...

virtual size_t	tableSize () const
	Used to determine the total size of the HashTable. More...

Private Member Functions
int	findIndex (const K &key) const
	Helper function to determine the index where a given key lies in the LPHashTable. More...

virtual void	resizeTable ()
	Private helper function to resize the HashTable. More...

Private Attributes
std::pair< K, V > **	table
	Storage for our LPHashTable. More...

bool *	should_probe
	Flags for whether or not to probe forward when looking at a particular cell in the table. More...

Additional Inherited Members
Protected Member Functions inherited from HashTable< K, V >
iterator	makeIterator (HTIteratorImpl *impl) const
	Implementation for our iterator. More...

bool	shouldResize () const
	Determines if the HashTable should resize. More...

size_t	findPrime (size_t num)
	Finds the closest prime in our list to the given number. More...

Protected Attributes inherited from HashTable< K, V >
size_t	elems
	The current number of elements stored in the HashTable. More...

size_t	size
	The current size of the HashTable (total cells). More...

Static Protected Attributes inherited from HashTable< K, V >
static const size_t	primes []
	List of primes for resizing. More...

Detailed Description

template<class K, class V>
class LPHashTable< K, V >

LPHashTable: a HashTable implementation that uses linear probing as a collision resolution strategy.

Author: Chase Geigle

Date: Spring 2011; Summer 2012

Constructor & Destructor Documentation

◆ LPHashTable() [1/2]

template<class K , class V >

LPHashTable< K, V >::LPHashTable ( size_t tsize )

Constructs a LPHashTable of the given size.

Parameters

tsize The desired number of starting cells in the LPHashTable.

◆ ~LPHashTable()

template<class K , class V >

LPHashTable< K, V >::~LPHashTable ( )

virtual

Destructor for the LPHashTable.

We use dynamic memory, and thus require the big three.

◆ LPHashTable() [2/2]

template<class K, class V>

LPHashTable< K, V >::LPHashTable ( const LPHashTable< K, V > & other )

Copy constructor.

Parameters

other The LPHashTable to be copied.

Member Function Documentation

◆ operator=()

template<class K, class V>

LPHashTable< K, V > const & LPHashTable< K, V >::operator= ( const LPHashTable< K, V > & rhs )

Assignment operator.

Parameters

rhs	The LPHashTable we want to assign into the current one.

Returns: A const reference to the current LPHashTable.

◆ insert()

template<class K, class V>

void LPHashTable< K, V >::insert	(	const K &	key,
		const V &	value
	)

virtual

Inserts the given key, value pair into the HashTable.

Parameters

key	The key to be inserted.
value	The value to be inserted.

Todo:: Implement this function.

Note: Remember to resize the table when necessary (load factor >= 0.7). Do this check after increasing elems!! Also, don't forget to mark the cell for probing with should_probe!

Implements HashTable< K, V >.

◆ remove()

template<class K, class V >

void LPHashTable< K, V >::remove ( const K & key )

virtual

Removes the given key (and its associated data) from the HashTable.

Parameters

key	The key to be removed.

Implements HashTable< K, V >.

◆ find()

template<class K, class V >

V LPHashTable< K, V >::find ( const K & key ) const

virtual

Finds the value associated with a given key.

Parameters

key	The key whose data we want to find.

Returns: The value associated with this key, or the default value (V()) if it was not found.

Implements HashTable< K, V >.

◆ keyExists()

template<class K, class V >

bool LPHashTable< K, V >::keyExists ( const K & key ) const

virtual

Determines if the given key exists in the HashTable.

Parameters

key	The key we want to find.

Returns: A boolean value indicating whether the key was found in the HashTable.

Implements HashTable< K, V >.

◆ clear()

template<class K , class V >

void LPHashTable< K, V >::clear ( )

virtual

Empties the HashTable (that is, all keys and values are removed).

Implements HashTable< K, V >.

◆ operator[]()

template<class K, class V >

V & LPHashTable< K, V >::operator[] ( const K & key )

virtual

Access operator: Returns a reference to a value in the HashTable, so that it may be modified.

If the key you are searching for is not found in the table, this method inserts it with the default value V() (which you then may modify).

Examples:

hashtable["mykey"]; // returns the value for "mykey", or the
                    // default value if "mykey" is not in
                    // the table

hashtable["myOtherKey"] = "myNewValue";

Parameters

key	The key to be found in the HashTable.

Returns: A reference to the value for this key contained in the table.

Implements HashTable< K, V >.

◆ begin()

template<class K, class V>

iterator LPHashTable< K, V >::begin ( ) const

inlinevirtual

Returns an iterator to the beginning of the HashTable.

Returns: An iterator to the beginning of the HashTable.

Implements HashTable< K, V >.

◆ end()

template<class K, class V>

iterator LPHashTable< K, V >::end ( ) const

inlinevirtual

Returns an iterator to the end of the HashTable.

Note that this is essentially like returning an index to one past the final element in an array (that is, end() itself gives an iterator to one past the last thing in the HashTable).

Returns: An iterator to the end of the HashTable.

Implements HashTable< K, V >.

◆ findIndex()

template<class K, class V >

int LPHashTable< K, V >::findIndex ( const K & key ) const

private

Helper function to determine the index where a given key lies in the LPHashTable.

If the key does not exist in the table, it will return -1.

Parameters

key	The key to look for.

Returns: The index of this key, or -1 if it was not found.

◆ resizeTable()

template<class K , class V >

void LPHashTable< K, V >::resizeTable ( )

privatevirtual

Private helper function to resize the HashTable.

This should be called when the load factor is >= 0.7 (this is somewhat arbitrary, but used for grading).

Implements HashTable< K, V >.

Member Data Documentation

◆ table

template<class K, class V>

std::pair<K, V>** LPHashTable< K, V >::table

private

Storage for our LPHashTable.

With linear probing, we only need the array, not buckets for each array index. Note that we use an array of pointers to pairs in this case since the check for an "empty" slot is simply a check against NULL in that cell.

◆ should_probe

template<class K, class V>

bool* LPHashTable< K, V >::should_probe

private

Flags for whether or not to probe forward when looking at a particular cell in the table.

This is a dynamic array of booleans that represents if a slot is (or previously was) occupied. This allows us determine whether or not we need to probe forward to look for our key.

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

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class K, class V> class LPHashTable< K, V >

Constructor & Destructor Documentation

◆ LPHashTable() [1/2]

◆ ~LPHashTable()

◆ LPHashTable() [2/2]

Member Function Documentation

◆ operator=()

◆ insert()

◆ remove()

◆ find()

◆ keyExists()

◆ clear()

◆ operator[]()

◆ begin()

◆ end()

◆ findIndex()

◆ resizeTable()

Member Data Documentation

◆ table

◆ should_probe

template<class K, class V>
class LPHashTable< K, V >