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

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

#include <hashtable.h>

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

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

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
numThe 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
keyThe key to be inserted.
valueThe 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
keyThe 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
keyThe 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
keyThe 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: