HashTable: a templated class that implements the Dictionary ADT by using a hash table. More...

#include <hashtable.h>

Inheritance diagram for HashTable< K, V >:

Classes
class	iterator
	Iterator for iterating over a hashtable. More...

Public Member Functions
virtual	~HashTable ()
	Destructor for a HashTable: made virtual to allow overloading in derived classes. More...

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

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

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

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

virtual void	clear ()=0
	Empties the HashTable (that is, all keys and values are removed). 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...

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

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

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

Protected Member Functions
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
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
static const size_t	primes []
	List of primes for resizing. More...

Private Member Functions
virtual void	resizeTable ()=0
	Private helper function to resize the HashTable. More...

Detailed Description

template<class K, class V>
class HashTable< K, V >

HashTable: a templated class that implements the Dictionary ADT by using a hash table.

Author: Chase Geigle

Date: Spring 2011; Summer 2012

Constructor & Destructor Documentation

template<class K , class V >

virtual HashTable< K, V >::~HashTable ( )

inlinevirtual

Destructor for a HashTable: made virtual to allow overloading in derived classes.

Member Function Documentation

template<class K , class V >

virtual iterator HashTable< K, V >::begin ( ) const

pure virtual

Returns an iterator to the beginning of the HashTable.

Returns: An iterator to the beginning of the HashTable.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

virtual void HashTable< K, V >::clear ( )

pure virtual

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

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

virtual iterator HashTable< K, V >::end ( ) const

pure virtual

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.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

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

pure 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.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

size_t HashTable< K, V >::findPrime ( size_t num )

protected

Finds the closest prime in our list to the given number.

Parameters

num	The number to find the closest prime to in our list.

Returns: The closest prime we have to num in our list of primes.

template<class K , class V >

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

pure virtual

Inserts the given key, value pair into the HashTable.

Parameters

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

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

virtual bool HashTable< K, V >::isEmpty ( ) const

inlinevirtual

Determines if the HashTable is empty.

O(1).

Note: This depends on elems being set properly in derived classes.

Returns: A boolean value indicating whether the HashTable is empty.

template<class K , class V >

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

pure 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.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

iterator HashTable< K, V >::makeIterator ( HTIteratorImpl * impl ) const

inlineprotected

Implementation for our iterator.

You don't have to worry about this. Helper function to create an iterator. You shouldn't have to invoke this: instead, use the begin() and end() functions on your particular HashTable implementation to get iterators to the beginning and ending of the HashTable, respectively.

Returns: An iterator for this HashTable.

template<class K , class V >

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

pure 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.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

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

pure virtual

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

Parameters

key	The key to be removed.

Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and DHHashTable< K, V >.

template<class K , class V >

virtual void HashTable< K, V >::resizeTable ( )

privatepure virtual

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).

Implemented in LPHashTable< K, V >, DHHashTable< K, V >, and SCHashTable< K, V >.

template<class K , class V >

bool HashTable< K, V >::shouldResize ( ) const

inlineprotected

Determines if the HashTable should resize.

Returns: Whether the HashTable should resize.

template<class K , class V >

virtual size_t HashTable< K, V >::tableSize ( ) const

inlinevirtual

Used to determine the total size of the HashTable.

Used for grading purposes.

Returns: The size of the HashTable (that is, the total number of available cells, not the number of elements the table contains).

Member Data Documentation

template<class K , class V >

size_t HashTable< K, V >::elems

protected

The current number of elements stored in the HashTable.

template<class K , class V >

const size_t HashTable< K, V >::primes

staticprotected

Initial value:

= {17ul,         29ul,         37ul,        53ul,        67ul,
       79ul,         97ul,         131ul,       193ul,       257ul,
       389ul,        521ul,        769ul,       1031ul,      1543ul,
       2053ul,       3079ul,       6151ul,      12289ul,     24593ul,
       49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
       1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
       50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
       1610612741ul, 3221225473ul, 4294967291ul}

List of primes for resizing.

"borrowed" from boost::unordered.

template<class K , class V >

size_t HashTable< K, V >::size

protected

The current size of the HashTable (total cells).

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

hashtable.h

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Member Functions

Detailed Description

template<class K, class V> class HashTable< K, V >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class K, class V>
class HashTable< K, V >