This project will implement a simple username/password lookup system using hash
ID: 3780234 • Letter: T
Question
This project will implement a simple username/password lookup system using hash tables. You should create the Hash Table from scratch. It may be helpful to create a separate class called HashEntry, in which you can store a String username and String password. The Hash Table will store these entries using the username as the key and the password as the value.
Create a hash code using the key to determine where the value is stored in the Hash Table. Here is a sample hash method. Feel free to borrow it for your program:
private int calcHashCode(String key) {
int mod = key.hashCode() % size;
return mod < 0 ? mod + size : mod;
}
You will be provided with a data file containing comma separated usernames and passwords. Read the data in from the file and put it into the table. Once the table is populated, ask the user to log into the system. If their username and password match the data in the table, alert the user that access has been granted:
Login: trevor
User trevor not found.
Login: mary
Password: test
Authentication Failure
Login: mary
Password: contrary
Authentication Successful
Welcome mary
Provided Data File (containing comma separated usernames and passwords):
jack,broken.crown
jill,tumblin'down
mary,contrary
bopeep,sheep!lost
Explanation / Answer
//main.cpp
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <string>
#include "HashTable.cpp"
using namespace std;
/// the struct for the login and password
struct Account
{
/// variables
string login;
string password;
/// hash function
static unsigned int hash(const string& str)
{
unsigned int val = 0;
for (int i = 0; i < str.length(); ++i) {
val += str[i];
}
return val;
}
/// get key function
string getKey() const
{
return login;
}
};
int main()
{
string loginI;
string passwordI;
string temp;
/// open file
ifstream fin ("password.dat");
fin.clear();
/// make new account to read into
Account acct;
/// make the hash table
HashTable<Account,string> data (8);
/// read in
while (fin.good())
{
fin >> acct.login >> acct.password;
//cout << acct.login << " " << acct.password << endl;
data.insert(acct);
//data.showStructure();
}
data.showStructure();
/// read in
cout << "Login: ";
cin >> loginI;
do
{
cout << "Password: ";
cin >> passwordI;
/// check for login
if (data.retrieve(loginI, acct))
{
/// check if passwords are the same
if ((acct.password == passwordI))
{
/// same password, print success
cout << "Authentication successful" << endl;
}
else
{
/// different password, print failure
cout << "Authentication failure" << endl;
}
}
else
{
/// if the data login is not saved print failure
cout << "Authentication failure" << endl;
}
cout << "Login: ";
cin >> loginI;
}
while(!cin.eof());
return 0;
}
==========================================================================
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <sys/time.h>
#include "HashTable.h"
#include "show10.cpp"
using namespace std;
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(int initTableSize)
{
/// save size
tableSize = initTableSize;
/// initialize the array
dataTable = new BSTree<DataType, KeyType>[tableSize];
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(const HashTable& other)
{
/// copy size and create new table
tableSize = other.tableSize;
dataTable = new BSTree<DataType, KeyType>[tableSize];
*this = other;
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>& HashTable<DataType, KeyType>:: operator=(const HashTable& other)
{
/// if the same return
if (this = &other)
return *this;
/// clear
clear();
/// copy the size and create new table
tableSize = other.tableSize;
dataTable = new BSTree<DataType, KeyType>[tableSize];
/// go through tables and copy the trees
for (int i = 0; i < tableSize; ++i)
{
dataTable[i] = other.dataTable[i];
}
return *this;
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::~HashTable()
{
clear();
delete[] dataTable;
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::insert(const DataType& newDataItem)
{
/// get hash
int location = newDataItem.hash(newDataItem.getKey()) % tableSize;
/// insert into tree
dataTable[location].insert(newDataItem);
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>:: remove(const KeyType& deleteKey)
{
/// get its location in the array
int location = DataType::hash(deleteKey) % tableSize;
/// check to delete it
return dataTable[location].remove(deleteKey);
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>:: retrieve(const KeyType& searchKey, DataType& returnItem) const
{
/// find location in the array
int location = DataType::hash(searchKey) % tableSize;
/// check if the item is there
return dataTable[location].retrieve(searchKey, returnItem);
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>:: clear()
{
/// iterate through the complete hash table
for (int i = 0; i < tableSize; ++i)
{
dataTable[i].clear();
}
}
/**
* Not Used
*/
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>:: isEmpty() const
{
bool flag = true;
for (int i = 0; i < tableSize; ++i)
{
/// check to see if each tree insdie the table is empty
flag = dataTable[i].isEmpty();
/// if flag is ever turned into false, then return false
if (flag == false)
return false;
}
return true;
}
template <typename DataType, typename KeyType>
double HashTable<DataType, KeyType>:: standardDeviation() const
{
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>:: copyTable(const HashTable& source)
{
*this = source;
}
==================================================
// HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdexcept>
#include <iostream>
using namespace std;
#include "BSTree.cpp"
template <typename DataType, typename KeyType>
class HashTable {
public:
HashTable(int initTableSize);
HashTable(const HashTable& other);
HashTable& operator=(const HashTable& other);
~HashTable();
void insert(const DataType& newDataItem);
bool remove(const KeyType& deleteKey);
bool retrieve(const KeyType& searchKey, DataType& returnItem) const;
void clear();
bool isEmpty() const;
void showStructure() const;
double standardDeviation() const;
private:
void copyTable(const HashTable& source);
int tableSize;
BSTree<DataType, KeyType>* dataTable;
};
#endif // ifndef HASHTABLE_H
====================================================================
//BSTree.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <sys/time.h>
#include "BSTree.h"
#include "show9.cpp"
using namespace std;
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode( const DataType& nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
: dataItem(nodeDataItem), left(leftPtr), right (rightPtr)
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree()
{
root = NULL;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree(const BSTree<DataType,KeyType>& source)
{
root=NULL;
*this = source;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>::operator=(const BSTree<DataType, KeyType>& source)
{
if (this == &source)
return *this;
clear();
copyHelp(root, source.root);
return *this;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::copyHelp( BSTreeNode*& home, BSTreeNode* RHS )
{
/// Stopping condition, end of tree
if (RHS == NULL)
{
home = NULL;
return;
}
/// Create node
home = new BSTreeNode (RHS->dataItem, NULL, NULL);
/// Recall with the other parts of the tree
copyHelp(home->left, RHS->left);
copyHelp(home->right, RHS->right);
return;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{
clear();
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert(const DataType& newDataItem)
{
insertHelper(root, newDataItem);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insertHelper(BSTreeNode* & location, const DataType& newDataItem)
{
/// if reached location, create the new node
if (location==NULL)
location = new BSTreeNode(newDataItem, NULL, NULL);
/// if the current location is larger than data go left
if (location->dataItem.getKey() > newDataItem.getKey())
insertHelper(location->left, newDataItem);
/// if the current location is smaller than data, go right
if (location->dataItem.getKey() < newDataItem.getKey())
insertHelper(location->right, newDataItem);
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve(const KeyType& searchKey, DataType& searchDataItem) const
{
return retrieveHelper(root, searchKey, searchDataItem);
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieveHelper(BSTreeNode* location, const KeyType& searchKey, DataType& searchDataItem) const
{
/// if checked the complete tree, return false
if (location == NULL)
return false;
/// if found, return true
if (location->dataItem.getKey() == searchKey)
{
searchDataItem = location->dataItem;
return true;
}
/// if what were are looking for is smaller go left else go right
if (location->dataItem.getKey() > searchKey)
{
return retrieveHelper(location->left, searchKey, searchDataItem);
}
else
{
return retrieveHelper(location->right, searchKey, searchDataItem);
}
}
template < typename DataType, class KeyType >
bool BSTree<DataType,KeyType>:: remove ( const KeyType& deleteKey )
{
return removeHelper(root, deleteKey);
}
template < typename DataType, class KeyType >
bool BSTree<DataType,KeyType>:: removeHelper ( BSTreeNode* & location, const KeyType& deleteKey )
{
/// if at the end and not found, return false
if (location == NULL)
return false;
/// if found, delete
if (location->dataItem.getKey() == deleteKey)
{
/// if no children
if ((location->left == NULL) && (location->right == NULL))
{
delete location;
location = NULL;
return true;
}
/// if one child
/// left child, no right
if ((location->left != NULL) && (location->right == NULL))
{
BSTreeNode* temp;
temp = location;
location = location->left;
delete temp;
return true;
}
/// no left, right child
if ((location->left == NULL) && (location->right != NULL))
{
BSTreeNode* temp;
temp = location;
location = location->right;
delete temp;
return true;
}
/// if two children
if ((location->left != NULL) && (location->right != NULL))
{
BSTreeNode* temp;
temp = location;
/// get predecessor
temp = temp->left;
while (temp->right != NULL)
temp = temp->right;
/// overwrite the value to delete with the predecessor
location->dataItem = temp->dataItem;
/// delete the node with the value just written to the new location
return removeHelper(location->left, temp->dataItem.getKey());
}
}
/// keep searching
if (location->dataItem.getKey() > deleteKey)
return removeHelper(location->left, deleteKey);
else
return removeHelper(location->right, deleteKey);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>:: writeKeys () const
{
writeKeysHelper(root);
cout << endl;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>:: writeKeysHelper (BSTreeNode* location) const
{
if (!isEmpty())
{
/// go all the way to the left
if (location->left != NULL)
{
writeKeysHelper(location->left);
}
/// once all the way to the left print out the current
cout << location->dataItem.getKey() << " ";
/// check for the children to the right of the most left node
if (location->right != NULL)
{
writeKeysHelper(location->right);
}
}
}
template < typename DataType, class KeyType >
void BSTree<DataType,KeyType>:: clear()
{
clearHelper(root);
root = NULL;
}
template < typename DataType, class KeyType >
void BSTree<DataType,KeyType>:: clearHelper( BSTreeNode* & location )
{
if(!isEmpty())
{
/// if there is more to the left recall with child
if (location->left != NULL)
clearHelper(location->left);
/// if leftmost has a right child repeat process with the right child
if (location->right != NULL)
clearHelper(location->right);
/// deallocate
delete location;
}
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>:: isEmpty () const
{
return (root == NULL);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>:: getHeight () const
{
if (isEmpty())
return 0;
heightHelper(root);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>:: heightHelper ( BSTreeNode* location) const
{
/// if we reached a null spot, return 0 since nothing is added
if (location == NULL)
return 0;
/// get the size of the left and right by recalling and going to the left and right
int leftTree = heightHelper(location->left);
int rightTree = heightHelper(location->right);
/// return which ever is larger plus one since the current node is part of the height
if (leftTree > rightTree)
return leftTree+1;
else
return rightTree+1;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>:: getCount () const
{
return countHelper(root);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>:: countHelper (BSTreeNode* location) const
{
if (location == NULL)
return 0;
else
return (countHelper(location->left)+countHelper(location->right)+1);
}
/**
* NOT USED
*/
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>:: writeLessThan ( const KeyType& searchKey ) const
{
}
==================================================================
//BSTree.h
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template < typename DataType, class KeyType > // DataType : tree data item
class BSTree // KeyType : key field
{
public:
// Constructor
BSTree (); // Default constructor
BSTree ( const BSTree<DataType,KeyType>& other ); // Copy constructor
BSTree& operator= ( const BSTree<DataType,KeyType>& other );
// Overloaded assignment operator
// Destructor
~BSTree ();
// Binary search tree manipulation operations
void insert ( const DataType& newDataItem ); // Insert data item
bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;
// Retrieve data item
bool remove ( const KeyType& deleteKey ); // Remove data item
void writeKeys () const; // Output keys
void clear (); // Clear tree
// Binary search tree status operations
bool isEmpty () const; // Tree is empty
// !! isFull() has been retired. Not very useful in a linked structure.
// Output the tree structure -- used in testing/debugging
void showStructure () const;
// In-lab operations
int getHeight () const; // Height of tree
int getCount () const; // Number of nodes in tree
void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey
protected:
class BSTreeNode // Inner class: facilitator for the BSTree class
{
public:
// Constructor
BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );
// Data members
DataType dataItem; // Binary search tree data item
BSTreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
};
// Recursive helpers for the public member functions -- insert
// prototypes of these functions here.
void showHelper ( BSTreeNode *p, int level ) const;
void insertHelper(BSTreeNode* & location, const DataType& newDataItem);
bool retrieveHelper(BSTreeNode* location, const KeyType& searchKey, DataType& searchDataItem) const;
bool removeHelper ( BSTreeNode* & location, const KeyType& deleteKey );
void writeKeysHelper (BSTreeNode* location) const;
void clearHelper( BSTreeNode* & location );
int heightHelper ( BSTreeNode* location) const;
int countHelper (BSTreeNode* location) const;
void copyHelp( BSTreeNode*& home, BSTreeNode* RHS );
// Data member
BSTreeNode *root; // Pointer to the root node
};
#endif // define BSTREE_H
======================================================================
//show9.cpp
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showStructure () const
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showHelper ( BSTreeNode *p,
int level ) const
{
int j; // Loop counter
if ( p != 0 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem.getKey(); // Output key
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
======================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.