LPHashTable: a HashTable implementation that uses linear probing as a collision resolution strategy.
More...
#include <lphashtable.h>
template<class K, class V>
class LPHashTable< K, V >
LPHashTable: a HashTable implementation that uses linear probing as a collision resolution strategy.
- Author
- Chase Geigle
- Date
- Spring 2011
-
Summer 2012
template<class K , class V >
Constructs a LPHashTable of the given size.
- Parameters
-
| tsize | The desired number of starting cells in the LPHashTable. |
template<class K , class V >
Destructor for the LPHashTable.
We use dynamic memory, and thus require the big three.
template<class K , class V >
Copy constructor.
- Parameters
-
template<class K , class V >
template<class K , class V >
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 >.
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 >.
template<class K , class V >
| int LPHashTable< K, V >::findIndex |
( |
const K & |
key | ) |
const |
|
private |
Helper function to determine the index where a given key lies in the LPHashTable.
If the key does not exist in the table, it will return -1.
- Parameters
-
- Returns
- The index of this key, or -1 if it was not found.
- Todo:
- Implement this function
Be careful in determining when the key is not in the table!
template<class K , class V >
| void LPHashTable< 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. |
- Todo:
- Implement this function.
- Note
- Remember to resize the table when necessary (load factor >= 0.7). Do this check after increasing elems (but before inserting)!! Also, don't forget to mark the cell for probing with should_probe!
Implements HashTable< K, V >.
template<class K , class V >
| bool LPHashTable< 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 >.
template<class K , class V >
Assignment operator.
- Parameters
-
| rhs | The LPHashTable we want to assign into the current one. |
- Returns
- A const reference to the current LPHashTable.
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 >.
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
Implements HashTable< K, V >.
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
The size of the table should be the closest prime to size * 2.
Use findPrime()!
Implements HashTable< K, V >.
template<class K , class V >
Flags for whether or not to probe forward when looking at a particular cell in the table.
This is a dynamic array of booleans that represents if a slot is (or previously was) occupied. This allows us determine whether or not we need to probe forward to look for our key.
template<class K , class V >
Storage for our LPHashTable.
With linear probing, we only need the array, not buckets for each array index. Note that we use an array of pointers to pairs in this case since the check for an "empty" slot is simply a check against NULL in that cell.
The documentation for this class was generated from the following files:
Public Member Functions inherited from HashTable< K, V >
1.8.5