SCHashTable: A HashTable implementation that uses a separate chaining collision resolution strategy.
More...
#include "schashtable.h"
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
◆ SCHashTable() [1/2]
template<class K , class V >
Constructs a SCHashTable of the given size.
- Parameters
-
tsize | The desired number of starting cells in the SCHashTable. |
◆ ~SCHashTable()
template<class K , class V >
Destructor for the SCHashTable.
We use dynamic memory, and thus require the big three.
◆ SCHashTable() [2/2]
template<class K , class V >
Copy constructor.
- Parameters
-
◆ operator=()
template<class K , class V >
Assignment operator.
- Parameters
-
rhs | The SCHashTable we want to assign into the current one. |
- Returns
- A const reference to the current SCHashTable.
◆ insert()
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
-
key | The key to be inserted. |
value | The value to be inserted. |
Implements HashTable< K, V >.
◆ remove()
template<class K , class V >
Removes the given key (and its associated data) from the HashTable.
- Parameters
-
key | The 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 >.
◆ find()
template<class K , class V >
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 SCHashTable< 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 >
◆ operator[]()
template<class K , class V >
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
-
- Returns
- A reference to the value for this key contained in the table.
Implements HashTable< K, V >.
◆ begin()
template<class K , class V >
◆ end()
template<class K , class V >
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 >.
◆ resizeTable()
template<class K , class V >
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 >.
◆ table
template<class K , class V >
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: