ECET-370 Hash Table Performance The purpose of this lab is to give you an opport
ID: 3538140 • Letter: E
Question
ECET-370
Hash Table Performance
The purpose of this lab is to give you an opportunity to implement a hash table. Your hash table must use chaining as your strategy for handling collisions. You should use the STL list class to implement this hash table. Information on the STL list class is attached at the end of this write-up. You could also use the Linked List that you did in an earlier assignment instead of the STL list class.
A symbol table used by a compiler usually contains a set of information about every symbol defined in a program. You are going to implement a symbol table where each symbol has three pieces of information associated with it; a name which is a character array or a string, a location which is an address; and a size which is the number of bytes of storage allocated to a symbol. This means that a node in your list will have the following data fields: a name field ( string or character array ), a location field ( integer ), and a size field (integer).
You can implement your hash table as a class, or as a set of functions and data structures. However, you must use the STL list class or your own Linked List class to store the node structure described above. Your implementation must provide a way to dynamically specify the number of entries in the hash table. For instance, if I give you a data set which contains N symbols, you should dynamically create two hash tables where the number of entries in the two hash tables is N/4 and 1.5N respectively. The hash tables (arrays of list objects) will need to be created based on the number of table entries specified at run time.
I will provide a file of symbol information which your program will need to read as input.
The first line of the file will contain an integer which is the number of symbols contained in the file. Each remaining line of the file will contain a symbol name, a location (integer value), and a size (integer value). Your program must take each symbol from the file and insert it into the hash table in an appropriate location. Some sample code is attached at the end of this write-up illustrating how to read data from a file.
Your program should be set up to easily use 2 different hash functions, and to analyze how well each particular hash function is doing. You should implement an analysis function which takes a hash table and reports how many symbols it contains based on checking all the lists in the table and counting nodes (or asking each linked list object for its size). The analysis should also report the worst case length of a list, as well as the number of entries of the hash table which were used (ie. list size > 0), and the average length (floating point number) of the lists (# entries / # lists used). This gives an indication of how good the hash function is for a given set of data.
Since it is common for a symbol table to have symbols where the address or size information has not yet been determined, your hash function must operate on the symbol name character string. All of the symbol names input to this program will be at least 4 characters long. You must implement and test a hash function which only looks at the first 2 characters of the symbol name. You must implement and test one other hash function which attempts to improve the analysis numbers mentioned above when using the same data set.
You must complete 2 distinct tests using the same data file. Your first test should use a hash table which has 1/4 the number of elements as the number of symbols in the file, and should use the hash function which uses only the first 2 characters of the symbol field. The first test should also use the same hash function with a hash table which is 1.5 times the number of symbols in the file. The second test should be the same as the first test, but use an improved hash function of your own design.
Collect all the analysis information from the 4 test cases and write up a brief summary of this lab. Briefly describe what your data shows when you change the table size from N/4 to 1.5N. Also, briefly compare the data from running with the original hash function to running with your improved hash function. The write up does not need to be more than a page.
Turn in:
The Lab Write-Up.
Print out all your source code.
Cover Sheet with a sign off indicating someone saw your program run
and generate some test data.
Screen shot of your program generated analysis data
ECET 370
STL List Class
This is a short tutorial in STL and the STL list class. In order to use a linked list from STL, you need to include the following code at the beginning of your program%u2026.
#include <list>
using namespace std;
The header files for the Standard Template Library do not use a %u201C.h%u201D. They create all of their classes in a namespace called std. %u201Cusing namespace std%u201D simply allows us to default to that name space.
Lists in STL are implemented as templates. So, to create a list of integers, we would declare it this way:
list<int> L;
STL lists have many convenient methods defined for them. See page 330+ in the Malik text for more details. One thing that they introduce is the notion of an %u201Citerator%u201D. An iterator is an object that is used to loop through (i.e. %u201Cto iterate over%u201D) a given data structure. Iterators have some very convenient operators defined for them that make them behave much like pointers. For instance:
list<int>::interator Li;
will let us define an iterator which points to elements in a list of integers. *Li will give us the value of the list element we are currently %u201Cpointing%u201D at. Li++ will move to the next element in the list. REMEMBER: iterators are NOT pointers, even though they behave like them.
Lists also have some new methods defined for them. The methods that we are interested in are%u2026.
list::begin()
returns an iterator that points to the first element in the list.
list::end()
returns an iterator that points past the last element in the list.
So, you process the elements of a list by doing something like this:
Li = L.begin();
while(Li != L.end())
{
// do something useful here with *Li
Li++;
}
list::insert(iterator, element)
will insert %u201Celement%u201D before the current location of %u201Citerator%u201D. Notice how list just gives us a generic insert() function. It will insert any old place we tell it. If you want to, for instance, insert elements in a sorted list, you would need to loop through the list and find the proper place to insert the element. Then, use insert() to do the work.
list::erase(iterator)
will delete the element currently pointed to by the iterator.
Other methods on lists which require no iterators at all%u2026.
list::clear()
will empty the list completely.
list::push_head(element)
will insert %u201Celement%u201D at the head of the list.
list::push_tail(element)
will insert %u201Celement%u201D at the tail of the list.
list::pop_head()
will delete the element at the head of the list.
list::pop_tail()
will delete the element at the tail of the list.
list::size()
will return the number of elements in the list.
// Here is a sample program which does file I/O
// It illustrates how to setup file input and output streams
// and how to use them to read / write data from / to the streams.
// This program also illustrates how to pass a reference to a file
// stream object from one function to the next...
#include <ios>
#include <iostream>
#include <fstream>
using namespace std;
void readint(fstream &fin, int &i)
{
fin >> i;
}
void readfloat(fstream &fin, float &f)
{
fin >> f;
}
void main() {
int ivar;
char name[80];
float fvar;
fstream fin("data_file.txt",ios::in);
fstream fout("out_file.txt",ios::out);
while(!fin.eof())
{
fin >> name;
readint(fin,ivar);
readfloat(fin,fvar);
cout << name << endl << ivar << endl << fvar << endl;
fout << name << endl << ivar << endl << fvar << endl;
}
}
Explanation / Answer
Is this a Question?
I seems like answer
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.