EECE 352: PS10

Due: 16 November 1999

Problem 0 (0%): The first part of the problem set is for you to become fully acquainted with the hash table implementation shown below. Notice that it uses quadratic probing. Pay close attention to the way nodes are added and deleted from the table. Finally, notice that it only works for strings, why? what would you need to do to make it work for other object types? can you see how you might implement a hash for ints? doubles? is this the kind of question I can ask in the final?

Problem 1 (40%): You will now modify the given hash table so that it reports:

  1. The number of non-empty entries in it.
  2. The total capacity.
  3. Lambda.
  4. The total number of lookups that have been performed. When an new entry is added to the first possible bucket that counts as one lookup. When that bucket is full and we insert it on the next one, that counts as two lookups, and so on.
Finally, notice how the hash table rehashes when lambda is bigger than .5. This value (.5) is fixed. You will make it one of the arguments in the constructor for the hashTable.

Problem 2 (30%): You will implement another hashTable which has all the functionality of the current hashTable but uses linear probing instead. HINT: inheritance is a good thing. Remember that the new hash table needs to maintain all the functionality you achieved in Problem 1.

Problem 3 (30%): You will read the file //Engr_asu/Ece352/words and generate a table comparing the Linear and Quadratic hash tables for different values of the rehashing cutoff. That is, you will write a main program that outputs, or writes to a file, all the values for the following table. You will hand a printout of your results when you hand in your program hardcopy. The table should be the first sheet, after the coversheet. In the table below LH refers to the Linear hash table and QH refers to the quadratic, "zoom" refers to the position of the word "zoom" in your table. Is the number of lookups behaving as you would expect? why not? You need to undestand the significance of these numbers when building applications.

Rehash cutoff QH size QH capacity QH lambda QH lookups QH zoom LH size LH capacity LH lambda LH lookups LH zoom
.1                    
.2                    
.3                    
.4                    
.5                    
.6                    
.7                    
.8                    
.9                    

The main.cpp.

#include<iostream>
#include<string>
#include<fstream>

#include"HashTable.h"

using namespace std;

int main() {

  ifstream ifs("//Engr_asu/Ece352/words");
  string word;
  string zoom = "zoom";
  
  for (double d = .1; d< .99; d+= .1){
    //read and print the appropiate information
    
    //when you are done reading , you will want to reset the file with:
    ifs.clear();
    ifs.seekg(0);
  }
  
  return 0;
}
The HashTable.h.
#pragma warning(disable:4786) 

#ifndef HashTable_H
#define HashTable_H

#include <string>
#include <vector>
using std::vector;
using std::string;


// QuadraticProbing Hash table class.
// Object must have operator!= and global function
//    unsigned int hash( const Object & x );
// CONSTRUCTION: with no parameters or another hash table.
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Object find( x )       --> Return item that matches x
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws exceptions as warranted

template <class Object>
class HashTable
{
 public:
  HashTable();
  
  int findPos( const Object & x );
  void makeEmpty( );
  void insert( const Object & x );
  void remove( const Object & x );
  Object * find( const Object & x );
  enum EntryType { ACTIVE, EMPTY, DELETED };
 private:
  struct HashEntry
  {
    Object    element;
    EntryType info;
    
    HashEntry( const Object & e = Object( ), EntryType i = EMPTY )
      : element( e ), info( i ) { }
  };
  
  int occupied;
  bool isActive( int currentPos ) const;
  void rehash( );
  bool isPrime( int n ) const;
  int nextPrime( int n ) const;

 protected:
  unsigned int hash( const string & key ) const;
  vector<HashEntry> array;
};

#include "HashTable.cpp"

#endif
The HashTable.cpp
#ifndef HashTable_cpp
#define HashTable_cpp

#include "HashTable.h"

bool isPrime( int n );
int nextPrime( int n );

// Construct the hash table.
template <class Object>
HashTable<Object>::
HashTable()
  : array( nextPrime( 101 ) )
{
    makeEmpty( );
}

// Insert item x into the hash table. If the item is
// already present, do nothing
template <class Object>
void HashTable<Object>::
insert( const Object & x )
{
      // Insert x as active
    int currentPos = findPos( x );
    if( isActive( currentPos ) )
		return;
    array[ currentPos ] = HashEntry( x, ACTIVE );
    if( ++occupied > array.size( ) / 2 )
        rehash( );
}

// Expand the hash table.
template <class Object>
void HashTable<Object>::
rehash( )
{
    vector<HashEntry> oldArray = array;

      // Create new double-sized, empty table
    array.resize( nextPrime( 2 * oldArray.size( ) ) );
    for( int j = 0; j < array.size( ); j++ )
        array[ j ].info = EMPTY;

      // Copy table over
    makeEmpty( );
    for( int i = 0; i < oldArray.size( ); i++ )
        if( oldArray[ i ].info == ACTIVE )
            insert( oldArray[ i ].element );
}

// Hash function, can only handle strings.
// If you want to hash other objects you will have to 
// create a hash table for them
template <class Object>
unsigned int HashTable<Object>::
hash( const string & key ) const
{
    unsigned int hashVal = 0;
//	cout << key << "%";
    for( size_t i = 0; i < key.size(); i++ )
        hashVal =  ( hashVal << 5 ) ^ key[ i ] ^ hashVal;
    return hashVal;
}

// Method that performs quadratic probing resolution.
// Return the position where the search for x terminates.
template <class Object>
int HashTable<Object>::
findPos( const Object & x )
{
    int collisionNum = 0;
    int currentPos = hash( x ) % array.size( );
    while( array[ currentPos ].info != EMPTY &&
           array[ currentPos ].element != x )
    {
        currentPos += 2 * ++collisionNum - 1;  // Compute ith probe
        if( currentPos >= array.size( ) )
            currentPos -= array.size( );
    }
//	cout << currentPos << " ";
    return currentPos;
}

// Remove item x from the hash table.
template <class Object>
void HashTable<Object>::
remove( const Object & x )
{
    int currentPos = findPos( x );
    if( isActive( currentPos ) )
        array[ currentPos ].info = DELETED;
}

// Find item x in the hash table.
// Return a pointer to the matching item or 0 if not found
template <class Object>
Object * HashTable<Object>::
find( const Object & x )
{
    int currentPos = findPos( x );
    if( isActive( currentPos ) )
        return & (array[ currentPos ].element);
    else
        return 0;
}

// Make the hash table logically empty.
template <class Object>
void HashTable<Object>::
makeEmpty( )
{
    occupied = 0;
    for( int i = 0; i < array.size( ); i++ )
        array[ i ].info = EMPTY;
}

// Return true if currentPos exists and is active.
template <class Object>
bool HashTable<Object>::
isActive( int currentPos ) const
{
    return array[ currentPos ].info == ACTIVE;
}


// Internal method to test if a positive number is prime.
// Not an efficient algorithm.
template <class Object>
bool HashTable<Object>::
isPrime( int n ) const 
{
    if( n == 2 || n == 3 )
        return true;

    if( n == 1 || n % 2 == 0 )
        return false;

    for( int i = 3; i * i <= n; i += 2 )
        if( n % i == 0 )
            return false;

    return true;
}

// Internal method to return a prime number at least as large as n.
// Assumes n > 0.
template <class Object>
int HashTable<Object>::
nextPrime( int n ) const
{
    if( n % 2 == 0 )
        n++;

    for( ; !isPrime( n ); n += 2 )
        ;

    return n;
}

#endif


Jose M. Vidal
Last modified: Thu Nov 11 11:48:07 EST 1999