hashing method and coilition

[psyche08]

can u help me how to create a folding method with separate cahining coilition of hashing?
thank you

[Unit]

cahining? coilition?

coilition i assume was collision. Elaborate your question.

If your question is to create a folding hash method that chains collisions, then you can consider this example.

Have a hash table of size n.

Split the key into several peices and fold two of them(concatenate, XOR, your pick) to get your hash. For example, you can hash the number 123456789 to a hash of 19 by concatenating first and last digits. The choice of the hash function is entirely on you.

Now fill the record/pointer to record in the hash table based on hash. If there is a collision, add it to a linked list starting at that hash location. All locations in the hash tables are linked lists in this method. When there are no collisions, only one node exists in the linked list at that location. When there are collisions, you will see a chain of records attached to a hash location as a linked list.

[psyche08]

thank you..can u teach me how to code the problem?

[Unit]

Attempt it yourself based on what you understood. We can help you debug it if you run into problems.

[psyche08]

#include "SeparateChaining.h"
#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 ), theLists( nextPrime( size ) )
{
}

/**
* 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 )
{
List<HashedObj> & whichList = theLists[ hash( x, theLists.size( ) ) ];
ListItr<HashedObj> itr = whichList.find( x );

if( itr.isPastEnd( ) )
whichList.insert( x, whichList.zeroth( ) );
}

/**
* Remove item x from the hash table.
*/
template <class HashedObj>
void HashTable<HashedObj>::remove( const HashedObj & x )
{
theLists[ hash( x, theLists.size( ) ) ].remove( x );
}

/**
* Find item x in the hash table.
* Return the matching item or ITEM_NOT_FOUND if not found
*/
template <class HashedObj>
const HashedObj & HashTable<HashedObj>::find( const HashedObj & x ) const
{
ListItr<HashedObj> itr;
itr = theLists[ hash( x, theLists.size( ) ) ].find( x );
if( itr.isPastEnd( ) )
return ITEM_NOT_FOUND;
else
return itr.retrieve( );
}

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

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


/**
* 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;


this is a separate cahining but cant create program with folding in it

[Unit]

erm.. I asked you to attempt it yourself :)

Not copy + paste from here!
http://www.cs.fiu.edu/~weiss/dsaa_c++/code/SeparateChaining.cpp

If you are going to do that, why not take the whole project from there?