# Hash Table and finding its elements

Page 1 of 1

## 1 Replies - 1008 Views - Last Post: 11 October 2015 - 08:00 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=382851&amp;s=1f9dd234498e0176175c9fa84c8b0a63&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 bs319

Reputation: 1
• Posts: 45
• Joined: 21-October 14

# Hash Table and finding its elements

Posted 10 October 2015 - 10:43 AM

I am really new to hashing and need some help.
We were given the hash class, and a file which contains thousands of words we need to figure out:
a)total number of elements in the table
/> the size of table
c)the total number of collisions.
``` template <typename HashedObj>
class HashTable
{
public:
explicit HashTable( int size = 101 ) : array( nextPrime( size ) )
{ makeEmpty( ); }

bool contains( const HashedObj & x ) const
{
return isActive( findPos( x ) );
}

void makeEmpty( )
{
currentSize = 0;
for( auto & entry : array )
entry.info = EMPTY;
}

bool insert( const HashedObj & x )
{
// Insert x as active
int currentPos = findPos( x );
if( isActive( currentPos ) )
return false;

if( array[ currentPos ].info != DELETED )
++currentSize;

array[ currentPos ].element = x;
array[ currentPos ].info = ACTIVE;

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

return true;
}

bool insert( HashedObj && x )
{
// Insert x as active
int currentPos = findPos( x );
if( isActive( currentPos ) )
return false;

if( array[ currentPos ].info != DELETED )
++currentSize;

array[ currentPos ] = std::move( x );
array[ currentPos ].info = ACTIVE;

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

return true;
}

bool remove( const HashedObj & x )
{
int currentPos = findPos( x );
if( !isActive( currentPos ) )
return false;

array[ currentPos ].info = DELETED;
return true;
}

enum EntryType { ACTIVE, EMPTY, DELETED };

private:
struct HashEntry
{
HashedObj element;
EntryType info;

HashEntry( const HashedObj & e = HashedObj{ }, EntryType i = EMPTY )
: element{ e }, info{ i } { }

HashEntry( HashedObj && e, EntryType i = EMPTY )
: element{ std::move( e ) }, info{ i } { }
};

vector<HashEntry> array;
int currentSize;

bool isActive( int currentPos ) const
{ return array[ currentPos ].info == ACTIVE; }

int findPos( const HashedObj & x ) const
{
int offset = 1;
int currentPos = myhash( x );

while( array[ currentPos ].info != EMPTY &&
array[ currentPos ].element != x )
{
currentPos += offset;  // Compute ith probe
offset += 2;
if( currentPos >= array.size( ) )
currentPos -= array.size( );
}

return currentPos;
}

void rehash( )
{
vector<HashEntry> oldArray = array;

// Create new double-sized, empty table
array.resize( nextPrime( 2 * oldArray.size( ) ) );
for( auto & entry : array )
entry.info = EMPTY;

// Copy table over
currentSize = 0;
for( auto & entry : oldArray )
if( entry.info == ACTIVE )
insert( std::move( entry.element ) );
}

size_t myhash( const HashedObj & x ) const
{
static hash<HashedObj> hf;
return hf( x ) % array.size( );
}
};

```

from cpp
```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;
}

```

Is This A Good Question/Topic? 0

## Replies To: Hash Table and finding its elements

### #2 Skydiver

• Code herder

Reputation: 5927
• Posts: 20,263
• Joined: 05-May 12

## Re: Hash Table and finding its elements

Posted 11 October 2015 - 08:00 PM

So what have you done to try to solve your problem? We can't do the thinking for you. (Well, actually we could, but you wouldn't be learning anything and so you would be wasting the money and/or time you are investing into your education.) Tell us how you would tackle the first question, and we can try to guide you in the right direction. Once we solve that we can move on to the succeeding questions.