lab_hash
Hellish Hash Tables
|
HashTable: a templated class that implements the Dictionary ADT by using a hash table. More...
#include "hashtable.h"
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... | |
HashTable: a templated class that implements the Dictionary ADT by using a hash table.
Destructor for a HashTable: made virtual to allow overloading in derived classes.
|
pure virtual |
Inserts the given key, value pair into the HashTable.
key | The key to be inserted. |
value | The value to be inserted. |
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
pure virtual |
Removes the given key (and its associated data) from the HashTable.
key | The key to be removed. |
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
pure virtual |
Finds the value associated with a given key.
key | The key whose data we want to find. |
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
pure virtual |
Determines if the given key exists in the HashTable.
key | The key we want to find. |
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
pure virtual |
Empties the HashTable (that is, all keys and values are removed).
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
inlinevirtual |
|
inlinevirtual |
|
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";
key | The key to be found in the HashTable. |
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
Returns an iterator to the beginning of the HashTable.
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
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).
Implemented in SCHashTable< K, V >, LPHashTable< K, V >, and LPHashTable< std::string, time_t >.
|
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.
|
inlineprotected |
|
protected |
Finds the closest prime in our list to the given number.
num | The number to find the closest prime to in our list. |
|
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 >, LPHashTable< std::string, time_t >, and SCHashTable< K, V >.
|
protected |
The current number of elements stored in the HashTable.
|
protected |
The current size of the HashTable (total cells).
|
staticprotected |
List of primes for resizing.
"borrowed" from boost::unordered.