lab_hash
Hellish Hash Tables
 All Classes Namespaces Files Functions Variables Pages
SCHashTable< K, V > Class Template Reference

SCHashTable: A HashTable implementation that uses a separate chaining collision resolution strategy. More...

#include <schashtable.h>

Inheritance diagram for SCHashTable< K, V >:
[legend]
Collaboration diagram for SCHashTable< K, V >:
[legend]

Public Types

typedef HashTable< K, V >::iterator iterator
 

Public Member Functions

 SCHashTable (size_t tsize)
 Constructs a SCHashTable of the given size. More...
 
virtual ~SCHashTable ()
 Destructor for the SCHashTable. More...
 
const SCHashTable< K, V > & operator= (const SCHashTable< K, V > &rhs)
 Assignment operator. More...
 
 SCHashTable (const SCHashTable< 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

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

Private Attributes

std::list< std::pair< K, V > > * table
 Storage for our SCHashTable. 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 SCHashTable< K, V >

SCHashTable: A HashTable implementation that uses a separate chaining collision resolution strategy.

Author
Chase Geigle
Date
Spring 2011
Summer 2012

Constructor & Destructor Documentation

template<class K , class V >
SCHashTable< K, V >::SCHashTable ( size_t  tsize)

Constructs a SCHashTable of the given size.

Parameters
tsizeThe desired number of starting cells in the SCHashTable.
template<class K , class V >
SCHashTable< K, V >::~SCHashTable ( )
virtual

Destructor for the SCHashTable.

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

template<class K , class V >
SCHashTable< K, V >::SCHashTable ( const SCHashTable< K, V > &  other)

Copy constructor.

Parameters
otherThe SCHashTable to be copied.

Member Function Documentation

template<class K , class V >
iterator SCHashTable< 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 >.

template<class K , class V >
void SCHashTable< K, V >::clear ( )
virtual

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

Implements HashTable< K, V >.

template<class K , class V >
iterator SCHashTable< 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 >.

template<class K , class V >
V SCHashTable< K, V >::find ( const K &  key) const
virtual

Finds the value associated with a given key.

Parameters
keyThe key whose data we want to find.
Returns
The value associated with this key, or the default value (V()) if it was not found.
Todo:
: Implement this function.

Implements HashTable< K, V >.

template<class K , class V >
void SCHashTable< K, V >::insert ( const K &  key,
const V &  value 
)
virtual

Inserts the given key, value pair into the HashTable.

Parameters
keyThe key to be inserted.
valueThe value to be inserted.
Todo:
Implement this function.

Implements HashTable< K, V >.

template<class K , class V >
bool SCHashTable< K, V >::keyExists ( const K &  key) const
virtual

Determines if the given key exists in the HashTable.

Parameters
keyThe key we want to find.
Returns
A boolean value indicating whether the key was found in the HashTable.

Implements HashTable< K, V >.

template<class K , class V >
SCHashTable< K, V > const & SCHashTable< K, V >::operator= ( const SCHashTable< K, V > &  rhs)

Assignment operator.

Parameters
rhsThe SCHashTable we want to assign into the current one.
Returns
A const reference to the current SCHashTable.
template<class K , class V >
V & SCHashTable< 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
keyThe key to be found in the HashTable.
Returns
A reference to the value for this key contained in the table.

Implements HashTable< K, V >.

template<class K , class V >
void SCHashTable< K, V >::remove ( const K &  key)
virtual

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

Parameters
keyThe key to be removed.
Todo:
Implement this function.

Please read the note in the lab spec about list iterators and the erase() function on std::list!

Implements HashTable< K, V >.

template<class K , class V >
void SCHashTable< 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).

Todo:
Implement this function.

Please read the note in the spec about list iterators! The size of the table should be the closest prime to size * 2.

Use findPrime()!

Implements HashTable< K, V >.

Member Data Documentation

template<class K , class V >
std::list<std::pair<K, V> >* SCHashTable< K, V >::table
private

Storage for our SCHashTable.

This is slightly ugly, but this is a dynamic array of standard lists for the separate chaining strategy. The element inside each list is a standard pair of K (key) and V (value).


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