Description
HOMEWORK 10
1. Implement a hash table where collisions are resolved by linear probing. You will implement the methods find, insert, and rehash for the class below. Your class will rehash when the load factor is greater or equal to 0.5. The hash function, hf, will be created when you instantiate a member of this class. But hf will return a positive integer whose range is much larger than the table size. The book says, “you will need to perform a final mod operation internally after the” hash function.
template class HashTable
{ public:
explicit HashTable( int size = 101 ):currentSize(0){ array.resize(size); } std::hash hf; // create a hash function object bool contains( const HashedObj & x ) const; void makeEmpty( ); bool insert( const HashedObj & x ); bool remove( const HashedObj & x); enum EntryType { ACTIVE, EMPTY, DELETED };
private: struct HashEntry
{
HashedObj element;
EntryType info;
HashEntry( const HashedObj & e = HashedObj(), EntryType i = EMPTY ) : element( e), info(i) {}
}; vector array; int currentSize; void rehash( );
};
2. Create an adjacency list for the graph of the NYC subway station. You will consider a subway station sa adjacent to subway station sb if there is a subway train that goes from sa directly to sb without going through any other stops, or you can transfer from sa to sb. You find what subway stations are adjacent to other subway stations by using the information in the files transfers.txt and MTA train stop data.txt. The file transfers.txt is a bit confusing! Here are some of the entries:
from_stop_id,to_stop_id,transfer_type,min_transfer_time 101,101,2,180
103,103,2,180
104,104,2,180
106,106,2,180
107,107,2,180
108,108,2,180
109,109,2,180
110,110,2,180
111,111,2,180
112,112,2,180
112,A09,2,180
113,113,2,180 …
In the file transfers.txt, observe you can transfer from subway station 112 to subway station A09. Thus A09 is adjacent to (a neighbor of ) 112.
In the file MTA train stop data.txt you can observe that subway stop 112 is one stop away from subway stop 111, and that subway stop 112 is one stop away from subway stop 113. Thus subway stops A09,111, and 113 are the stops adjacent to (neighbors of) subway stop 112.
You will create an adjacency list as an unordered map<string, list> instead of a vector<list In the next homework assignment, you will use this adjacency list in the shortest path algorithm.
Written Part
1. Using big-oh notation, what is the worst case running time for your algorithm to create the adjacency list?
2. If your hash table size, n, was equal to 20 (or 40, or 2000), why might the following hash function not be a good idea: h(k) = 4k mod n?
3. For the following questions: Let the hash function be H(x) = x mod M, where the table size (M) is initially
5.
(a) if the collision strategy was linear probing, what would the hash table look like
• after inserting 4371, 6173
• then removing 6173
• then inserting 3327 and 26
• after resizing to a table size of M = 11
• then inserting 4199, 4340, 9679, 1323
(b) if the collision strategy was separate chaining, what would the hash table look like
• after inserting 4371, 1323, 6173, 4199, 4344, 9679
• then removing 6173
• then inserting 3324
• then resizing to a table size of M = 11
• inserting 21
