Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

Posted on 2005-03-27
Medium Priority
2,029 Views
Hi,
I am now implementing a quadratic hash table, which would use quadratic probing.

index = hash_function(key)

index + i^2, where i = 1, 2, 3, 4..... MAX

So, how do I write this in code? And how do I determine when I should stop the probing? If not, it can continue infinitely, am I right? Thanks.
0
Question by:zwinmin
1 Comment

LVL 86

Accepted Solution

jkr earned 2000 total points
ID: 13640007
Check out e.g.

for a full fledged sample:

#include "vector.h"
#include "mystring.h"

//
// CONSTRUCTION: an initialization for ITEM_NOT_FOUND
//               and an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Hashable find( x )     --> Return item that matches x
// void makeEmpty( )      --> Remove all items

template <class HashedObj>
class HashTable
{
public:
explicit HashTable( const HashedObj & notFound, int size = 101 );
HashTable( const HashTable & rhs )
: ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND ),
array( rhs.array ), currentSize( rhs.currentSize ) { }

const HashedObj & find( const HashedObj & x ) const;

void makeEmpty( );
void insert( const HashedObj & x );
void remove( const HashedObj & x );

const HashTable & operator=( const HashTable & rhs );

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<HashEntry> array;
int currentSize;
const HashedObj ITEM_NOT_FOUND;

bool isActive( int currentPos ) const;
int findPos( const HashedObj & x ) const;
void rehash( );
};

int hash( const string & key, int tableSize );
int hash( int key, int tableSize );

#endif

#include <iostream.h>

/**
* Internal method to test if a positive number is prime.
* Not an efficient algorithm.
*/
bool isPrime( int n )
{
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.
*/
int nextPrime( int n )
{
if( n % 2 == 0 )
n++;

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

return n;
}

/**
* Construct the hash table.
*/
template <class HashedObj>
HashTable<HashedObj>::HashTable( const HashedObj & notFound, int size )
: ITEM_NOT_FOUND( notFound ), array( nextPrime( size ) )
{
makeEmpty( );
}

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

// Rehash; see Section 5.5
if( ++currentSize > array.size( ) / 2 )
rehash( );
}

/**
* Expand the hash table.
*/
template <class HashedObj>
void HashTable<HashedObj>::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
currentSize = 0;
for( int i = 0; i < oldArray.size( ); i++ )
if( oldArray[ i ].info == ACTIVE )
insert( oldArray[ i ].element );
}

/**
* Method that performs quadratic probing resolution.
* Return the position where the search for x terminates.
*/
template <class HashedObj>
int HashTable<HashedObj>::findPos( const HashedObj & x ) const
{
/* 1*/      int collisionNum = 0;
/* 2*/      int currentPos = hash( x, array.size( ) );

/* 3*/      while( array[ currentPos ].info != EMPTY &&
array[ currentPos ].element != x )
{
/* 4*/          currentPos += 2 * ++collisionNum - 1;  // Compute ith probe
/* 5*/          if( currentPos >= array.size( ) )
/* 6*/              currentPos -= array.size( );
}

/* 7*/      return currentPos;
}

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

/**
* Find item x in the hash table.
*/
template <class HashedObj>
const HashedObj & HashTable<HashedObj>::find( const HashedObj & x ) const
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
return array[ currentPos ].element;
else
return ITEM_NOT_FOUND;
}

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

/**
* Deep copy.
*/
template <class HashedObj>
const HashTable<HashedObj> & HashTable<HashedObj>::
operator=( const HashTable<HashedObj> & rhs )
{
if( this != &rhs )
{
array = rhs.array;
currentSize = rhs.currentSize;
}
return *this;
}

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

/**
* A hash routine for string objects.
*/
int hash( const string & key, int tableSize )
{
int hashVal = 0;

for( int i = 0; i < key.length( ); i++ )
hashVal = 37 * hashVal + key[ i ];

hashVal %= tableSize;
if( hashVal < 0 )
hashVal += tableSize;

return hashVal;
}

/**
* A hash routine for ints.
*/
int hash( int key, int tableSize )
{
if( key < 0 ) key = -key;
return key % tableSize;
}
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
###### Suggested Courses
Course of the Month11 days, 14 hours left to enroll