Hash Tables Instructions

hash-tables-instructions

User Manual: Pdf

Open the PDF directly: View PDF PDF.
Page Count: 2

DownloadHash-tables-instructions
Open PDF In BrowserView PDF
Hash Tables
COSC2030 Lab10
April 16, 2018
Due: April 22 @ 11:59pm
In class we have been discussing hashing and the storing
of hashes. In this lab you will now implement a hash
table that uses two different methods for dealing with
collisions in that table. The two methods you will
implement, which were outlined in the slides, are Open
Addressing and Separate Chaining. Those slides have
been uploaded to WyoCourses under Files/hashinglec.pdf. Revisit them to refresh yourself about what
the structures look like.
P ROJECT S ETUP
By now you have pulled the lab repository from github.
There are a lot of files so here is a quick description:
1) modified Node and LinkedList from Lab2 - You will
use these for the Separate Chaining Method
2) GeneralHashFunctions - An Open Source Library
containing different hashing functions, see the example file marked GeneralHashTest.cpp for usage
3) HashTables - This is where you will implement your
two methods
4) main.cpp - Main driver file, read input files and
perform all your tests here
5) randoWords.txt - file containing 50 lines of 5 random
words each
6) names.txt - file containing 400 random names
7) stlHashEx.cpp - example program demonstrating the
stl::hash function
8) unordered-mapEx.cpp - example program demonstrating the stl::unordered_map data structure which
is the base structure for our HashTables
If on a Windows machine you will need to scan through
the .h files and fix any includes statement at the top that
is marked with "change to .h"
B EGIN C ODING
Now import these files into whichever editor you are
using. After looking through the code you will find
code stubs marked with a TODO which is where you
will fill in the code to perform the following steps:
1) Add functionality to the two addToTable functions in
HashTables.cpp. The key for our unordered_map will
be the hash value generated from a hashing function,
and the value will be a custom bucket struct that is
defined in HashTables.h.

2) Read in names.txt and randoWords.txt line by line
(code from lab1 comes in handy here). Each line of
the file will be hashed and used as the hash key.
3) Create a HashTables object for each input file, and use
the stl::hash function to generate a hashkey which you
will use to call HashTables::AddToTables(hashkey,
text) function for each line of each input file. At
the end of this section you should have 2 HashTables
objects.
4) Repeat Step1 but now use the WeakHash() function I
added to the GeneralHashFunctions class. At the end
of this section you should have 4 HashTables objects.
5) Repeat Step1 again but now choose any two other
hashing function you want from the GeneralHashFunctions class. At the end of this section you should
have 8 separate HashTables objects.
6) Edit the README of your repository to report the
number of collisions found using each insert method,
for each input file, for each hash function using the
following tables:
RandomWords:
Function
stl::hash
WeakHash
HashPick1
HashPick2

Open Addressing
numCollisions
numCollisions
numCollisions
numCollisions

Separate Chaining
numCollisions
numCollisions
numCollisions
numCollisions

Open Addressing
numCollisions
numCollisions
numCollisions
numCollisions

Separate Chaining
numCollisions
numCollisions
numCollisions
numCollisions

Names:
Function
stl::hash
WeakHash
HashPick1
HashPick2

G RADING
This lab is worth a total of 20 pts with the breakdown
as follows:
1) 5pts - stl::hash implemented and tested for both input
files - 5pts
2) 5pts - WeakHash implemented and tested for both
input files5pts
3) 5pts - Pick one other hash implemented and tested
for both input files
4) 5pts - Pick another hash implemented and tested for
both input files
2.5 points will be taken off per point-item if one storage
method (Open Address/Separate Chaining) is incorrect.

5 points will be taken off per point-item if both storage
methods are wrong.
5 points will be taken off if tables are not filled out.
The usual late deductions still apply. Submit all code to
be graded to the master branch of your repository. My
grading scripts will assume the same file structure as the
original repo you start with so please keep the structure
and file names consistent with the original.

2
Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : No
Page Count                      : 2
Producer                        : pdfTeX-1.40.17
Creator                         : TeX
Create Date                     : 2018:04:16 06:24:18Z
Modify Date                     : 2018:04:16 06:24:18Z
Trapped                         : False
PTEX Fullbanner                 : This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) kpathsea version 6.2.2
EXIF Metadata provided by EXIF.tools

Navigation menu