Implement a hash table in C++
keyExists
,find
,remove
, andsize
should all be O(1)add
should be reasonably fast. Use linear probing to find an open slot in the hash table. This will be O(1), on average, except whengrow
is called.grow
should be O(n)- Do not leak memory
"Open Data Structures," Chapter 5, except for 5.2.3. http://opendatastructures.org/ods-cpp/5_Hash_Tables.html
1. Which of the above requirements work, and which do not? For each requirement, write a brief response.
- TODO
- TODO
- TODO
- TODO
2. I decided to use two function (keyExists
and find
) to enable lookup of keys. Another option would have been to have find
return a T*
, which would be NULL
if an item with matching key is not found. Which design do you think would be better? Explain your reasoning. You may notice that the designers of C++ made the same decision I did when they designed http://www.cplusplus.com/reference/unordered_map/unordered_map/
TODO
3. What is one question that confused you about this exercise, or one piece of advice you would share with students next semester?
TODO